-3
$\begingroup$

The halting problem relies on the fluidity of Turing machines. That is, a string can represent a machine.

Can you do the same for C++ on a modern computer?

Let's see my first attempt. Let bool h(string x, string y) be the purported function that decides haltingness and always halts. You can easily turn it into a full program.

Now define a self-contradictory function f:

bool f(string x) {
    if (h(x, x))
        for (;;);
    return true;
}

int main() {
    cout << h(f, f) << endl;
}

The problem is that I can't feed the code of f into h in main().

My second attempt: Prepare 4 files: h.cpp, h.exe, f.cpp, f.exe. And suppose the call formats are

h.exe filename1 filename2
f.exe filename

My problem is that in f.cpp I need to call h.exe, which in turn has to be part of f.cpp.

What's your working scheme?

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ I'm not sure what you are trying to achieve here. Proving the halting problem is undecidable by C++ machines, I assume? $\endgroup$ – dkaeae Jul 12 '19 at 9:16
  • $\begingroup$ @dkaeae Is turning a C++ program into a Turing machine the only way to prove that this program can't solve the halting problem? I want to do the argument in C++ and hence bypassing the idea of Turing machines altogether. I don't like the idea of Turing machines. Or is it that in C++ this argument is not viable and hence Turing machines are necessary? I want to shoot down the belief that there is no halting problem in C++ programs, i.e., you can decide haltingness for the set of C++ programs. If you believe the set of Turing machines and the set of C++ programs are indeed equal, do it in C++. $\endgroup$ – Zirui Wang Jul 12 '19 at 9:52
  • $\begingroup$ Surely you can feed the code of f into h. Just write it again as a literal string. $\endgroup$ – Dmitri Urbanowicz Jul 12 '19 at 10:11
  • 1
    $\begingroup$ @ZiruiWang What do you mean by "universal"? Turing-complete? Is there a particular reason you believe C++ would not be Turing-complete? Virtually every programming language is. Almost every example of the ones that aren't were deliberately constructed to not be Turing-complete. $\endgroup$ – dkaeae Jul 12 '19 at 13:58
  • 1
    $\begingroup$ This is not a counterexample for Turing-completeness at all. The halting problem is undecidable by TMs. C++ not solving the halting problem does not contradict completeness in any way. AFAICT your only problem is figuring out how to pass C++ code to a function, which is just implementation trivia. $\endgroup$ – dkaeae Jul 13 '19 at 7:17
4
$\begingroup$

If you want to prove that the halting problem for C++ programs can't be decided by a C++ program, just copy the proof of the Halting problem but replace every use of a universal Turing machine with a C++ interpreter/compiler that's written in C++.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Yes, the translation is not as trivial as advertised in textbooks. $\endgroup$ – Zirui Wang Jul 12 '19 at 11:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.