Halting Problem in ordinary C ?

[polcott]

typedef void (*ptr)();
int HHH(ptr P);

void Infinite_Loop()
{
  HERE: goto HERE;
  return;
}

void Infinite_Recursion()
{
  Infinite_Recursion();
  return;
}

void DDD()
{
  HHH(DDD);
  return;
}

int DD()
{
  int Halt_Status = HHH(DD);
  if (Halt_Status)
    HERE: goto HERE;
  return Halt_Status;
}

Every sufficiently competent C programmer knows
that when HHH correctly emulates N steps of the above functions that none
of these functions can possibly reach their own "return" instruction and terminate
normally.

Since HHH does see that same pattern that competent C programmers see
it correctly aborts its emulation and rejects these inputs as non terminating.

Fully operational software system enabling any C function to emulate the x86
machine code of another C function in debug step mode.
x86utm/Halt7.c at master · plolcott/x86utm

This x86utm operating system allows the emulator to emulate itself emulating
another C function to arbitrary levels of recursive emulation. It is on this basis
that termination analyzer HHH is created.

 

[BlackCube]

What would your simulator say about the monkeys and the typewriters?

Function X creates random books until Hamlet is produced. It will halt eventually.

Function Y randomly tests Fermat's theorem until a counter-example is found. It will never halt.