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?

  • $\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 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 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 at 10:11
  • $\begingroup$ But also keep in mind, that then you either need to include the source of h into that string, or you need to be sure that h knows that "h(x,x)" means call of h itself. $\endgroup$ – Dmitri Urbanowicz Jul 12 at 10:12
  • $\begingroup$ The key problem is to solve the fluidity problem. It's easy to convert strings to Turing machines and back. But how to do that in C++? That's the main difficulty. I think it's too easy with TMs and conjecture that it's impossible with C++, under my current understanding. $\endgroup$ – Zirui Wang Jul 12 at 11:23

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++.

  • $\begingroup$ Yes, the translation is not as trivial as advertised in textbooks. $\endgroup$ – Zirui Wang Jul 12 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.