Halting problem in C++

Question

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?

Answer 1

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

Answer 2

The halting problem states that there is no $h$ function that works on every input. You are missing that you need to supply a concrete implementation of a function $h$ (which is as hard as writing a compiler), and prove that it works on any input function. The latter is an impossible task, as you should feed $h$ with all valid programs.

The proof of the halting problem is not constructive, it just shows the impossibility.

Answer 3

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

This problem is solved by invoking h with the machine address of f.

Translated to C for the x86utm operating system

00 typedef int (*ptr)();
01 int h(ptr x, ptr y)
02
03 int f(ptr x) {
04   if (h(x, x))
05     for (;;);
06   return 1;
07 }
08
09 int main() 
10 {  
11  Output("Input_Halts = ", h(f, f));
12 }

When h is a simulating termination analyzer based on an x86 emulator within the x86utm operating system this is the execution trace of the above code:

Line 11: main() calls h(f,f) that simulates f(f)

keeps repeating:
Line 04: simulated f(f) calls simulated h(f,f) that simulates f(f) ...

Simulation invariant:
f correctly simulated by h never reaches its own Line 06.

This enables h to correctly report that (its input) f correctly simulated by h never halts. The above is fully operational code within the x86utm operating system

Answer 4

I contacted one of the best experts in the field of the theory computation of about my own ideas on the halting problem and he gave me permission to quote him.

MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022
If simulating halt decider H correctly simulates its input D until H correctly determines that its simulated D would never stop running unless aborted then

H can abort its simulation of D and correctly report that D specifies a non-halting sequence of configurations.
MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022

typedef void (*ptr)(); 
typedef int (*ptr2)(); 
int H0(ptr P); 
int H(ptr2 P, ptr2 I); 

void Infinite_Loop() 
{
  HERE: goto HERE;
}

void Infinite_Recursion()
{
  Infinite_Recursion(); 
}

void DDD() 
{
  H0(DDD); 
} 

int P(ptr2 x) 
{
  int Halt_Status = H(x, x); 
  if (Halt_Status)   
    HERE: goto HERE; 
  return Halt_Status; 
} 

int main() 
{ 
  H0(Infinite_Loop); 
  H0(Infinite_Recursion); 
  H0(DDD); 
  H(P,P); 
}

Every C programmer that knows what an x86 emulator is knows that when H0 emulates the machine language of Infinite_Loop, Infinite_Recursion, and DDD that it must abort these emulations so that itself can terminate normally.

When this is construed as non-halting criteria then simulating termination analyzer H0 is correct to reject these inputs as non-halting by returning 0 to its caller.

It turns out that this same reasoning equally applies to H(P,P). It is impossible for the correctly emulated call to H(P,P) to return to P correctly emulated by H.

This same issue doesn't arise with the directly executed P(P) because the directly executed P(P) is essentially the first call in a recursive chain where the second call is always aborted.

If H(P,P) did not correctly recognize that it must abort the simulation of its input to correctly prevent its own non-termination the directly executed P(P) would never halt.