-6
$\begingroup$

Halting problem: In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. https://en.wikipedia.org/wiki/Halting_problem

Can anyone point out any error in the following conclusion? (or affirm that it is correct)

A simulating halt decider is a UTM that has been adapted to decide whether or not its input halts. It does this on the basis of the dynamic behavior of this input. Behavior that matches a non-halting pattern is recognized. When it determines that its input would not halt it aborts the simulation of its input and reports that is input is not a halting computation.

The key notion that must be expressed is infinitely nested simulation. In the language of Turing machines this would seem quite tedious. I could use the Linz approach and express this as state transition diagrams.

Infinitely nested simulation is expressed as a cycle from qx to q0.
Figure 12.3 Turing Machine Ĥ (Linz:1990:319)

Key halt deciding criteria overcomes self-referential inputs

When-so-ever a simulating halt decider must abort the simulation of its input to prevent the infinite execution of this input, this input is always correctly decided as not a halting computation.

The simple concrete examples that can be fully understood by any expert C programmer. The x86utm operating system was created to investigate the following examples in the high-level language of C.

H examines the behavior of the x86 emulation of its input. As soon as a non-halting behavior pattern is matched H aborts the simulation of its input and decides that its input is not a halting computation.

This understanding is a mandatory prerequisite:
A bench check of the first line of main() can be understood by any expert C programmer to specify infinite recursion that never reaches the second line of H_Hat2(). If you can't see this then you will not understand the rest.

int Simulate(u32 P, u32 I) {
  ((void(*)(u32))P)(I);
  return 1; 
}

// Simplified Linz Ĥ (Linz:1990:319)
void H_Hat(u32 P) {
  // Linz H as a simulating partial halt decider
  u32 Input_Halts = H(P, P);  
  if (Input_Halts) 
    HERE: goto HERE; 
} 

void H_Hat2(u32 P) {
  u32 Input_Halts = Simulate(P, P);  
  if (Input_Halts) 
    HERE: goto HERE; 
} 

int main() {
  Simulate((u32)H_Hat2, (u32)H_Hat2);  
  H((u32)H_Hat, (u32)H_Hat);  
}

Anyone that knows C programming very well will know that line 1 of main() won't halt and line 2 of main() will only halt if simulating partial halt decider H() stops simulating H_Hat(). A simulating halt decider that never stops simulating its input is simply a simulator on this input.

When we know that the UTM simulation of TM Description P on input I would never halt we know that the execution of TM P(I) would never halt.

Conclusion: On this basis we know that any computation that must have its simulation aborted to prevent its otherwise infinite execution is not a halting computation, H stops simulating its input and reports that its input is not a halting computation.

Linz, Peter 1990. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company.

$\endgroup$
21
  • 1
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – D.W. Jun 5 at 6:38
  • 3
    $\begingroup$ I don't understand what "any computation that must have its simulation aborted to prevent its otherwise infinite execution" means. $\endgroup$ – D.W. Jun 5 at 6:39
  • 2
    $\begingroup$ If you want to prove anything in the realm of computability, don't use C. If for no other reason, it provides an unnecessarily complex model of computation that's hard to reason about. $\endgroup$ – Raphael Jun 5 at 10:44
  • 3
    $\begingroup$ " I had to use C so that key details [...] are not lost by slipping through the cracks of understanding with abstract purely mental models of machines." -- If your proof doesn't carry over to TMs (or an equivalent model), it's not a proof. Not within the framework of classical computability theory, anyway. $\endgroup$ – Raphael Jun 7 at 9:36
  • 3
    $\begingroup$ True. But if no one wants to read it, what good does it for you? That said, having skimmed your post, your main argument seems to be "trivial if you know enough C". That doesn't convince me, nor does it inspire curiosity to learn more. (Yes, that's subjective.) That being said, your opening remarks seem to be flawed: a "looping" computation need not contain the same state twice (detecting such loops is, indeed, trivial); in fact, the term is misleading: we mean "not terminating". What's more, you can never confidently say you will not see a loop. $\endgroup$ – Raphael Jun 7 at 21:01
-4
$\begingroup$

The following concrete example shows that the confounding input is aborted before it ever receives any return value from the halt decider. The simulating halt decider H aborts its input because this input specifies infinite invocations comparable to infinite recursion.

When a simulating halt decider must abort the simulation of its input to prevent the infinite execution of this input, this input is correctly decided as not a halting computation even though it has been forced to halt and thus halts.

Now Ĥ is a Turing machine, so that it will have some description in Σ*, say ŵ. This string, in addition to being the description of Ĥ can also be used as input string. We can therefore legitimately ask what would happen if Ĥ is applied to ŵ. (Linz:1990:320)

When we assume that the actual the Linz halt decider H bases its halting decision on simulating its input the same infinitely nested simulation is derived.

This provides the basis for the halt decider embedded in Ĥ to decide that its input is not a computation that halts.

Because the halt decider must abort the simulation of its input to prevent its infinite execution it correctly transitions to its final state of Ĥ.qn indicting that its input is not a computation that halts.

// Simplified Linz Ĥ (Linz:1990:319)
void H_Hat(u32 P) {
  u32 Input_Halts = H(P, P);  
  if (Input_Halts) 
    HERE: goto HERE; 
} 

int main() {
  u32 Input_Would_Halt6 = H((u32)H_Hat, (u32)H_Hat);  
  Output("Input_Would_Halt6 = ", Input_Would_Halt6);
}

Because the input to H() on the first line of H_Hat() must be aborted to prevent its infinite execution this input is correctly decided as not a halting computation.

Linz, Peter 1990. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company.

_H_Hat()
[00000b10](01)  55              push ebp
[00000b11](02)  8bec            mov ebp,esp
[00000b13](01)  51              push ecx
[00000b14](03)  8b4508          mov eax,[ebp+08]
[00000b17](01)  50              push eax
[00000b18](03)  8b4d08          mov ecx,[ebp+08]
[00000b1b](01)  51              push ecx
[00000b1c](05)  e81ffeffff      call 00000940
[00000b21](03)  83c408          add esp,+08
[00000b24](03)  8945fc          mov [ebp-04],eax
[00000b27](04)  837dfc00        cmp dword [ebp-04],+00
[00000b2b](02)  7402            jz 00000b2f
[00000b2d](02)  ebfe            jmp 00000b2d
[00000b2f](02)  8be5            mov esp,ebp
[00000b31](01)  5d              pop ebp
[00000b32](01)  c3              ret
Size in bytes:(0035) [00000b32]

_main()
[00000b40](01)  55              push ebp
[00000b41](02)  8bec            mov ebp,esp
[00000b43](01)  51              push ecx
[00000b44](05)  68100b0000      push 00000b10
[00000b49](05)  68100b0000      push 00000b10
[00000b4e](05)  e8edfdffff      call 00000940
[00000b53](03)  83c408          add esp,+08
[00000b56](03)  8945fc          mov [ebp-04],eax
[00000b59](03)  8b45fc          mov eax,[ebp-04]
[00000b5c](01)  50              push eax
[00000b5d](05)  682b030000      push 0000032b
[00000b62](05)  e8f9f7ffff      call 00000360
[00000b67](03)  83c408          add esp,+08
[00000b6a](02)  33c0            xor eax,eax
[00000b6c](02)  8be5            mov esp,ebp
[00000b6e](01)  5d              pop ebp
[00000b6f](01)  c3              ret
Size in bytes:(0048) [00000b6f]

Columns
(1) Machine address of instruction
(2) Machine address of top of stack
(3) Value of top of stack after instruction executed
(4) Number of bytes of machine code
(5) Machine language bytes
(6) Assembly language text
===============================
...[00000b40][00101533][00000000](01)  55              push ebp
...[00000b41][00101533][00000000](02)  8bec            mov ebp,esp
...[00000b43][0010152f][00000000](01)  51              push ecx
...[00000b44][0010152b][00000b10](05)  68100b0000      push 00000b10
...[00000b49][00101527][00000b10](05)  68100b0000      push 00000b10
...[00000b4e][00101523][00000b53](05)  e8edfdffff      call 00000940
Begin Local Halt Decider Simulation at Machine Address:b10
...[00000b10][002115d3][002115d7](01)  55              push ebp
...[00000b11][002115d3][002115d7](02)  8bec            mov ebp,esp
...[00000b13][002115cf][002015a3](01)  51              push ecx
...[00000b14][002115cf][002015a3](03)  8b4508          mov eax,[ebp+08]
...[00000b17][002115cb][00000b10](01)  50              push eax
...[00000b18][002115cb][00000b10](03)  8b4d08          mov ecx,[ebp+08]
...[00000b1b][002115c7][00000b10](01)  51              push ecx
...[00000b1c][002115c3][00000b21](05)  e81ffeffff      call 00000940
...[00000b10][0025bffb][0025bfff](01)  55              push ebp
...[00000b11][0025bffb][0025bfff](02)  8bec            mov ebp,esp
...[00000b13][0025bff7][0024bfcb](01)  51              push ecx
...[00000b14][0025bff7][0024bfcb](03)  8b4508          mov eax,[ebp+08]
...[00000b17][0025bff3][00000b10](01)  50              push eax
...[00000b18][0025bff3][00000b10](03)  8b4d08          mov ecx,[ebp+08]
...[00000b1b][0025bfef][00000b10](01)  51              push ecx
...[00000b1c][0025bfeb][00000b21](05)  e81ffeffff      call 00000940
Local Halt Decider: Infinite Recursion Detected Simulation Stopped 
...[00000b53][0010152f][00000000](03)  83c408          add esp,+08
...[00000b56][0010152f][00000000](03)  8945fc          mov [ebp-04],eax
...[00000b59][0010152f][00000000](03)  8b45fc          mov eax,[ebp-04]
...[00000b5c][0010152b][00000000](01)  50              push eax
...[00000b5d][00101527][0000032b](05)  682b030000      push 0000032b
---[00000b62][00101527][0000032b](05)  e8f9f7ffff      call 00000360
Input_Would_Halt6 = 0
...[00000b67][0010152f][00000000](03)  83c408          add esp,+08
...[00000b6a][0010152f][00000000](02)  33c0            xor eax,eax
...[00000b6c][00101533][00000000](02)  8be5            mov esp,ebp
...[00000b6e][00101537][00100000](01)  5d              pop ebp
...[00000b6f][0010153b][00000080](01)  c3              ret
Number_of_User_Instructions(33)
Number of Instructions Executed(26452)
$\endgroup$

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.