Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: "Fred. Zwarts" <F.Zwarts@HetNet.nl>
Newsgroups: comp.theory
Subject: Re: Rebutting the Sipser Halting Problem Proof
Date: Mon, 16 Sep 2024 13:21:29 +0200
Organization: A noiseless patient Spider
Lines: 47
Message-ID: <vc94bp$2q9hl$1@dont-email.me>
References: <vc6qlc$275or$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Mon, 16 Sep 2024 13:21:30 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="189e15fcec50cfa3d7cb755b6954aeb8";
	logging-data="2958901"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/HDFm+3+BqFapJ1RNwR5Wh"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:JREKh0v7cV9NYJ3+r0NnP3kENqI=
Content-Language: en-GB
In-Reply-To: <vc6qlc$275or$1@dont-email.me>
Bytes: 3477

Op 15.sep.2024 om 16:23 schreef olcott:
> 
> Rebutting the Sipser Halting Problem Proof
> D(D) correctly reports its own halt status
> 
> https://www.researchgate.net/ 
> publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof
> 

> We can see that the first seven instructions of D emulated by H precisely match the first seven instructions of the x86 source-code of D. This conclusively proves that these instructions were emulated correctly. 

Yes H makes a good start, but fails to complete the simulation, because 
of a bug in the code to recognise an infinite 'recursion'.

> H detects that D is calling H twice in sequence with the same aguments. H also sees that thereare no conditional branch instructions from the beginning of D to its call to H that can possibly escape the repetition of this recursive simulation. 

H fails to see that in-between the two beginnings of D, there are many 
conditional branch instructions, namely in the H called by D.
The simulation fails to properly simulate the call to H. This bug makes 
that H decides incorrectly that there is an infinite recursion.

> Anyone sufficiently technically competent in the x86 programming language will agree that the above execution trace of D emulated by H shows that D will never stop running unless H aborts its emulation of D.

Yes, and anyone sufficiently technically competent in the x86 language 
will also see that this proves that H fails to correctly complete the 
simulation.
The bug in the code decides after two cycles that there are an infinite 
number of cycles, because it misses the conditional branch instructions 
in these cycles, because of the incorrect simulation that deviates from 
the semantics of the x86 language, with an improper simulation of the H 
called by D.
So, it misses the fact that the simulated H would also (incorrectly) see 
this 'special condition', after which it would also abort, after which 
it would return to D and D would halt.

The string w describes only one program and the semantics of the x86 
language allows only one behaviour for this program.
This behaviour is 'halting', as proven by direct execution, by the 
simulation by the world class simulator and other simulations.
But H fails to reproduce this behaviour in its attempt to simulate 
itself. This proves that H deviates from the semantics of the x86 
language in its simulation.

H cannot possibly simulate itself correctly up to the end.