Refuting the Peter Linz Halting Problem Proof V4

[Skepdick]

Eventually, the whole process may terminate, which we achieve in a Turing machine by putting it into a halt state. A Turing machine is said to halt whenever it reaches a configuration for which δ is not defined; this is possible because δ is a partial function. In fact, we will assume that no transitions are defined for any final state, so the Turing machine will halt whenever it enters a final state. (Linz-1990:234)

Do you understand that you, as the observer of the Turing machine cannot determine whether it halted because it reached a final state; or whether it halted because it reached an undefined state.

That's why Turing machines suck! They are terrible models of computation if you expect them to interact with the outside world.

If you want to differentiate between abort and halt you need an effect system which signals an exit status!

exit(0) -> Terminated without error (halt)
exit(1) -> Terminated with error (abort)

https://en.wikipedia.org/wiki/Exit_status

[Skepdick]

Eventually, the whole process may terminate, which we achieve in a Turing machine by putting it into a halt state. A Turing machine is said to halt whenever it reaches a configuration for which δ is not defined; this is possible because δ is a partial function. In fact, we will assume that no transitions are defined for any final state, so the Turing machine will halt whenever it enters a final state. (Linz-1990:234)

As soon as you allow for signaling you are no longer talking about computation, you are talking about process algebras. Distributed dynamic systems.

Mathematics has run out of usefulness for you.

[PeteOlcott]

Eventually, the whole process may terminate, which we achieve in a Turing machine by putting it into a halt state. A Turing machine is said to halt whenever it reaches a configuration for which δ is not defined; this is possible because δ is a partial function. In fact, we will assume that no transitions are defined for any final state, so the Turing machine will halt whenever it enters a final state. (Linz-1990:234)

Do you understand that you, as the observer of the Turing machine cannot determine whether it halted because it reached a final state; or whether it halted because it reached an undefined state.

Since I am creating a Turing machine interpreter from scratch on the basis of this system I know that your statement is ridiculously ignorant:
http://www.lns.mit.edu/~dsw/turing/turing.html

It easy for a UTM to see that its simulated slave TM reaches a point where there are no transitions out of the current state of this slave TM.

[Skepdick]

Since I am creating a Turing machine interpreter from scratch on the basis of this system I know that your statement is ridiculously ignorant:
http://www.lns.mit.edu/~dsw/turing/turing.html

It easy for one TM to see that its simulated slave TM reaches a point where there are no transitions out of its current state.

Sigh. Idiot.

There is no way for you to prove the liveness property of a process you are executing because you have the wait() operator.

So you can trivially implement a system of two processes (A and B) such that A waits until B terminates and B waits until A terminates.

https://en.wikipedia.org/wiki/Wait_(system_call)

If your interpreter solves this problem then you have solved the Dining philosophers problem.

Deadlocks in distriibuted systems are a manifestation of the halting problem!

Here is an algorithm which makes progress AND does not halt.

Code: Select all

while True:
    pass

That's the NOP operator.

https://en.wikipedia.org/wiki/NOP_(code)

[PeteOlcott]

Since I am creating a Turing machine interpreter from scratch on the basis of this system I know that your statement is ridiculously ignorant:
http://www.lns.mit.edu/~dsw/turing/turing.html

It easy for one TM to see that its simulated slave TM reaches a point where there are no transitions out of its current state.

Sigh. Idiot.

There is no way for you to prove the liveness property of a process you are executing because you have the wait() operator.

So you can trivially implement a system of two processes (A and B) such that A waits until B terminates and B waits until A terminates.

https://en.wikipedia.org/wiki/Wait_(system_call)

If your interpreter solves this problem then you have solved the Dining philosophers problem.

It is a very common practice in operating system design to make context switches between processes even when there is only one actual physical processor. I implemented this in the x86utm operating system. I had to write all of the operating system calls myself from scratch. x86utm directly executes the COFF object file output from the Microsoft C compiler.

[Skepdick]

It is a very common practice in operating system design to make context switches between processes even when there is only one actual physical processor. I implemented this in the x86utm operating system. I had to write all of the operating system calls myself from scratch. x86utm directly executes the COFF object file output from the Microsoft C compiler.

Yeah.... it's a very common practice. Context switches are handled by your operating system. Without getting bogged down into the various multi-tasking strategies (cooperative vs pre-emptive etc.)

The operating system is a process which DOES NOT HALT. It loops indefinitely by design until signaled to terminate.

Literally every daemon/background process has an infinite control loop - a conditional jump!

[PeteOlcott]

It is a very common practice in operating system design to make context switches between processes even when there is only one actual physical processor. I implemented this in the x86utm operating system. I had to write all of the operating system calls myself from scratch. x86utm directly executes the COFF object file output from the Microsoft C compiler.

Yeah.... it's a very common practice. Context switches are handled by your operating system. Without getting bogged down into the various multi-tasking strategies (cooperative vs pre-emptive etc.)

The operating system is a process which DOES NOT HALT. It loops indefinitely by design. and until instructed to terminate.

Literally every daemon/background process has an infinite control loop.

x86utm executes H which invokes an excellent open source x86 emulator to emulate the input to H(P,P) in debug step mode.
https://www.researchgate.net/publicatio ... ulation_V5
Shows exactly how H(P,P) correctly determines that its input does not halt.

[Skepdick]

x86utm executes H which invokes an excellent open source x86 emulator to emulate the input to H(P,P) in debug step mode.
https://www.researchgate.net/publicatio ... ulation_V5
Shows exactly how H(P,P) correctly determines that its input does not halt.

Debug step mode

The debugger itself is subject to non-termination! Prove that the debugger will terminate!

The debugger terminates only after the program being debugged terminates.
If the program being debugged doesn't terminate then the debugger won't terminate either. Unless you force premature termination! Say ... via timeouts!

So now you need a debugger to debug the debugger to debug the debugger to debug the debugger...

Reeeeeeeeeeeeeeeeeeeeeeeeeeeeee!

[PeteOlcott]

H simulates its input one x86 instruction at a time until it correctly matches a non-halting behavior pattern, as H(P,P) correctly does. Then it aborts this simulation and rejects this input as H(P,P) correctly does.

[Skepdick]

H simulates its input one x86 instruction at a time until it correctly matches a non-halting behavior pattern, as H(P,P) correctly does. Then it aborts this simulation and rejects this input as H(P,P) correctly does.

This non-halting C program doesn't exhibit non-halting behavior!
It doesn't exhibit ANY behavior!

It just does nothing. Forever.

Code: Select all

int main() {
	for(;;){
	};
}

It's equivalent to Ruby's

Code: Select all

loop{} 

Or Python's

Code: Select all

while True:
    pass

Or Haskell

Code: Select all

main = do main

[PeteOlcott]

H simulates its input one x86 instruction at a time until it correctly matches a non-halting behavior pattern, as H(P,P) correctly does. Then it aborts this simulation and rejects this input as H(P,P) correctly does.

This non-halting C program doesn't exhibit non-halting behavior!
It doesn't exhibit ANY behavior!

It just does nothing. Forever.

Code: Select all

int main() {
	for(;;){
	};
}

Code: Select all

_main()
[000013a2](01)  55              push ebp
[000013a3](02)  8bec            mov ebp,esp
[000013a5](02)  ebfe            jmp 000013a5
[000013a7](01)  5d              pop ebp
[000013a8](01)  c3              ret
Size in bytes:(0007) [000013a8]

Wrong !

[Skepdick]

H simulates its input one x86 instruction at a time until it correctly matches a non-halting behavior pattern, as H(P,P) correctly does. Then it aborts this simulation and rejects this input as H(P,P) correctly does.

This non-halting C program doesn't exhibit non-halting behavior!
It doesn't exhibit ANY behavior!

It just does nothing. Forever.

Code: Select all

int main() {
	for(;;){
	};
}

Code: Select all

_main()
[000013a2](01)  55              push ebp
[000013a3](02)  8bec            mov ebp,esp
[000013a5](02)  ebfe            jmp 000013a5
[000013a7](01)  5d              pop ebp
[000013a8](01)  c3              ret
Size in bytes:(0007) [000013a8]

Wrong !

Wrong why?

"jmp 000013a5" is an infinite loop. The "ret" is never executed. By proxy any step-debugger you run over this code doesn't halt either.

So what has your decider determined?

[Skepdick]

H simulates its input one x86 instruction at a time until it correctly matches a non-halting behavior pattern, as H(P,P) correctly does. Then it aborts this simulation and rejects this input as H(P,P) correctly does.

This non-halting C program doesn't exhibit non-halting behavior!
It doesn't exhibit ANY behavior!

It just does nothing. Forever.

Code: Select all

int main() {
	for(;;){
	};
}

Code: Select all

_main()
[000013a2](01)  55              push ebp
[000013a3](02)  8bec            mov ebp,esp
[000013a5](02)  ebfe            jmp 000013a5
[000013a7](01)  5d              pop ebp
[000013a8](01)  c3              ret
Size in bytes:(0007) [000013a8]

Wrong !

Fuck it...

Here's a loop which terminates when rand() is 1.

Prove termination; or non-termination.

Code: Select all

#include <stdio.h>
#include <stdlib.h>

int main() {
	for(;;){
		if (rand() == 1) {
			break;
		};
	};
}

[PeteOlcott]

Code: Select all

_main2()
[00001372](01)  55              push ebp
[00001373](02)  8bec            mov ebp,esp
[00001375](02)  ebfe            jmp 00001375
[00001377](01)  5d              pop ebp
[00001378](01)  c3              ret
Size in bytes:(0007) [00001378]

_main()
[00001382](01)  55              push ebp
[00001383](02)  8bec            mov ebp,esp
[00001385](05)  6872130000      push 00001372
[0000138a](05)  e823fdffff      call 000010b2
[0000138f](03)  83c404          add esp,+04
[00001392](01)  50              push eax
[00001393](05)  6823040000      push 00000423
[00001398](05)  e8d5f0ffff      call 00000472
[0000139d](03)  83c408          add esp,+08
[000013a0](02)  33c0            xor eax,eax
[000013a2](01)  5d              pop ebp
[000013a3](01)  c3              ret
Size in bytes:(0034) [000013a3]

 machine   stack     stack     machine    assembly
 address   address   data      code       language
 ========  ========  ========  =========  =============
...[00001382][001022b1][00000000] 55              push ebp
...[00001383][001022b1][00000000] 8bec            mov ebp,esp
...[00001385][001022ad][00001372] 6872130000      push 00001372
...[0000138a][001022a9][0000138f] e823fdffff      call 000010b2
--Allocation[002022c5](00000018)
--Allocation[002022e5](00000034)
--Allocation[00202321](00000034)
--Allocation[0020235d](00010000)
New slave_stack @20235d
--Allocation[00212365](0003a980)

Begin Local Halt Decider Simulation   Execution Trace Stored at:212365
H0_Root:1
...[00001372][00212355][00212359] 55              push ebp
...[00001373][00212355][00212359] 8bec            mov ebp,esp
...[00001375][00212355][00212359] ebfe            jmp 00001375
...[00001375][00212355][00212359] ebfe            jmp 00001375
Local Halt Decider: Infinite Loop Detected Simulation Stopped
 
...[0000138f][001022b1][00000000] 83c404          add esp,+04
...[00001392][001022ad][00000000] 50              push eax
...[00001393][001022a9][00000423] 6823040000      push 00000423
---[00001398][001022a9][00000423] e8d5f0ffff      call 00000472
Input_Halts = 0
...[0000139d][001022b1][00000000] 83c408          add esp,+08
...[000013a0][001022b1][00000000] 33c0            xor eax,eax
...[000013a2][001022b5][00100000] 5d              pop ebp
...[000013a3][001022b9][00000004] c3              ret
Number_of_User_Instructions(1)
Number of Instructions Executed(680)

[Skepdick]

Number of Instructions Executed(680)

Great! Now run your decider on this and watch it fail to terminate.

Of course, it might crash when you overflow the "instructions executed" counter...

Code: Select all

#include <stdio.h>
#include <stdlib.h>

int main() {
	for(;;){
		if (rand() < 0) {
			break;
		};
	};
}