Halts() correctly decides the conventional counter-example of the HP proofs

olcott

unread,

Nov 20, 2020, 1:12:13 PM11/20/20

to

When-so-ever decider Halts() (adapted from a UTM) decides that:
(a) its input (,I) would never halt unless H stopped simulating it
and it is the case that
(b) its input (,I) would never halt unless H stopped simulating it
then Halts() has made a correct not-halting decision on this input.

I just finished enough of the programming of my x86utm operating system
so that it collects the actual execution trace of every line of user
code that is executed. Of the 10,671 lines that are actually executed
only 35 lines are relevant to the halt decider's halting decision. All
of these lines are shown below.

Anyone with a bachelors degree in computer science would understand that
every Turing machine that has infinite recursion would never stop
running. That I show exactly how to decide the previously undecidable
input: (H_Hat shown below) proves that I have refuted all of the
conventional halting problem proofs.

My system is based on the x86 language that is known to be
computationally equivalent to a universal Turing machine for every
computation that does not require more memory than it has available:

x86 language ≡ von Neumann architecture ≡ UTM ≡ RASP Machine

http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf

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

void H_Hat(u32 P)
{
u32 Aborted = Halts(P, P);
if (Aborted)
HALT
else
HERE: goto HERE;
}

int main()
{
u32 P = (u32)H_Hat;
Halts(P, P);
HALT;
}

_H_Hat()
[000004f7](01) 55 push ebp
[000004f8](02) 8bec mov ebp,esp
[000004fa](01) 51 push ecx
[000004fb](03) 8b4508 mov eax,[ebp+08]
[000004fe](01) 50 push eax
[000004ff](03) 8b4d08 mov ecx,[ebp+08]
[00000502](01) 51 push ecx
[00000503](05) e86ffeffff call 00000377
[00000508](03) 83c408 add esp,+08
[0000050b](03) 8945fc mov [ebp-04],eax
[0000050e](04) 837dfc00 cmp dword [ebp-04],+00
[00000512](02) 7403 jz 00000517
[00000514](01) f4 hlt
[00000515](02) eb02 jmp 00000519
[00000517](02) ebfe jmp 00000517
[00000519](02) 8be5 mov esp,ebp
[0000051b](01) 5d pop ebp
[0000051c](01) c3 ret

_main()
[00000527](01) 55 push ebp
[00000528](02) 8bec mov ebp,esp
[0000052a](01) 51 push ecx
[0000052b](07) c745fcf7040000 mov [ebp-04],000004f7
[00000532](03) 8b45fc mov eax,[ebp-04]
[00000535](01) 50 push eax
[00000536](03) 8b4dfc mov ecx,[ebp-04]
[00000539](01) 51 push ecx
[0000053a](05) e838feffff call 00000377
[0000053f](03) 83c408 add esp,+08
[00000542](01) f4 hlt
[00000543](02) 8be5 mov esp,ebp
[00000545](01) 5d pop ebp
[00000546](01) c3 ret

Execution trace seen by the global halt decider
std_vector[00010abc]-->00000527 // main()
std_vector[00010ac0]-->00000528
std_vector[00010ac4]-->0000052a
std_vector[00010ac8]-->0000052b
std_vector[00010acc]-->00000532
std_vector[00010ad0]-->00000535
std_vector[00010ad4]-->00000536
std_vector[00010ad8]-->00000539
std_vector[00010adc]-->0000053a // call to _Halts()
std_vector[00010ae0]-->000004f7 // DebugStep(_H_Hat)
std_vector[00010ae4]-->000004f8
std_vector[00010ae8]-->000004fa
std_vector[00010aec]-->000004fb
std_vector[00010af0]-->000004fe
std_vector[00010af4]-->000004ff
std_vector[00010af8]-->00000502
std_vector[00010afc]-->00000503 // call to _Halts()
std_vector[00010b00]-->000004f7 // DebugStep(_H_Hat)
std_vector[00010b04]-->000004f8
std_vector[00010b08]-->000004fa
std_vector[00010b0c]-->000004fb
std_vector[00010b10]-->000004fe
std_vector[00010b14]-->000004ff
std_vector[00010b18]-->00000502
std_vector[00010b1c]-->00000503 // call to _Halts() infinite recursion
decided

Number of Instructions Executed(10671)
--
Copyright 2020 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein

Mr Flibble

unread,

Nov 20, 2020, 7:05:48 PM11/20/20

to

On 20/11/2020 18:11, olcott wrote:
> When-so-ever decider Halts() (adapted from a UTM) decides that:
> (a) its input (,I) would never halt unless H stopped simulating it
> and it is the case that
> (b) its input (,I) would never halt unless H stopped simulating it
> then Halts() has made a correct not-halting decision on this input.
>
> I just finished enough of the programming of my x86utm operating system so that it collects the actual execution trace of every line of user code that is executed. Of the 10,671 lines that are actually executed only 35 lines are relevant to the halt decider's halting decision. All of these lines are shown below.
>
> Anyone with a bachelors degree in computer science would understand that every Turing machine that has infinite recursion would never stop running. That I show exactly how to decide the previously undecidable input: (H_Hat shown below) proves that I have refuted all of the conventional halting problem proofs.

1) Infinite recursion isn't the only cause of non-halting behaviour;
2) If your solution is based on finite RAM and register state being repeated then you are not testing a UTM as your so-called "UTM" is not an arbitrary TM nor is it acting on arbitrary input.

Still nothing to see here.

/Flibble

--
¬

olcott

unread,

Nov 20, 2020, 7:34:29 PM11/20/20

to

On 11/20/2020 6:05 PM, Mr Flibble wrote:
> On 20/11/2020 18:11, olcott wrote:
>> When-so-ever decider Halts() (adapted from a UTM) decides that:
>> (a) its input (,I) would never halt unless H stopped simulating it
>> and it is the case that
>> (b) its input (,I) would never halt unless H stopped simulating it
>> then Halts() has made a correct not-halting decision on this input.
>>
>> I just finished enough of the programming of my x86utm operating
>> system so that it collects the actual execution trace of every line of
>> user code that is executed. Of the 10,671 lines that are actually
>> executed only 35 lines are relevant to the halt decider's halting
>> decision. All of these lines are shown below.
>>
>> Anyone with a bachelors degree in computer science would understand
>> that every Turing machine that has infinite recursion would never stop
>> running. That I show exactly how to decide the previously undecidable
>> input: (H_Hat shown below) proves that I have refuted all of the
>> conventional halting problem proofs.
>
> 1) Infinite recursion isn't the only cause of non-halting behaviour;

You are correct, yet in the case at hand H_Hat() would never halt unless
the halt decider stops simulating it.

> 2) If your solution is based on finite RAM and register state being
> repeated then you are not testing a UTM as your so-called "UTM" is not
> an arbitrary TM nor is it acting on arbitrary input.

x86 language ≡ von Neumann architecture ≡ UTM ≡ RASP Machine

None-the-less the equivalence between computations under my x86utm
operating system and those of an actual UTM continues to exist for all
computations not requiring more memory than is available.

The conventional halting problem counter-example embodied by H_Hat() is
such a computation.

> Still nothing to see here.
>
> /Flibble
>

--