Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups: comp.theory,sci.logic
Subject: Re: Refutation of the Peter Linz Halting Problem proof 2024-03-05 --partial agreement--
Date: Thu, 07 Mar 2024 11:55:29 +0000
Organization: A noiseless patient Spider
Lines: 66
Message-ID: <87cys6i7da.fsf@bsb.me.uk>
References: <us8shn$7g2d$1@dont-email.me> <us92f0$uvql$4@i2pn2.org>
	<us931e$8gmr$1@dont-email.me> <usa4rk$10ek4$3@i2pn2.org>
	<usa5to$gp0j$1@dont-email.me> <usa8lp$10ek5$5@i2pn2.org>
	<usa9o9$ho7b$1@dont-email.me> <usag21$118jg$1@i2pn2.org>
	<usanbu$klu7$1@dont-email.me> <usas0v$11q96$2@i2pn2.org>
	<usavq1$m7mn$1@dont-email.me> <usb01q$m897$1@dont-email.me>
	<c-GcnbJk3KPt0nT4nZ2dnZfqn_GdnZ2d@brightview.co.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: dont-email.me; posting-host="b9ed4ba77ae2b0370363ae177b04bec3";
	logging-data="1096098"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/WFanMyIPOx4HCukjZtMWz3+OG4yiaqIo="
User-Agent: Gnus/5.13 (Gnus v5.13)
Cancel-Lock: sha1:JmjyRXdO5oj87pUz7NqubmgVa/I=
	sha1:Wip2qnyb81SeV7/6b37h7A+E2q4=
X-BSB-Auth: 1.b082714fdf9f4113a6da.20240307115529GMT.87cys6i7da.fsf@bsb.me.uk
Bytes: 4501

Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:

> On 06/03/2024 23:59, immibis wrote:
>> On 7/03/24 00:55, olcott wrote:
>>> Ĥ.H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.Hqn
>>> Correctly reports that Ĥ.H ⟨Ĥ⟩ ⟨Ĥ⟩ must abort its simulation.
>>>
>>> H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qy
>>> Correctly reports that H ⟨Ĥ⟩ ⟨Ĥ⟩ need not abort its simulation.
>> What are the exact steps which the exact same program with the exact same
>> input uses to get two different results?
>> I saw x86utm. In x86utm there is a mistake because Ĥ.H is not defined to
>> do exactly the same steps as H, which means you failed to do the Linz
>> procedure.
>
> Not sure if we're discussing a general H here, or PO's H/Ĥ under his
> x86utm.  (Ĥ is called D under x86utm.)
>
> Under x86utm, Ĥ.H is implemented as a call to H from D, whilst H in
> implemented as a call to H from main.  So we would expect stack addresses
> to differ, but for that not to affect the computation.
>
> In both cases, H:
> -  simulates D(D) computation
> -  spots PO's unsound "infinite recursion" pattern
> -  announces it has encountered infinite recursion
> -  returns 0  [non-halting]
>
> So Ĥ.H does exactly the same steps as H, and reports the same result, as
> required for Linz proof. And just as Linz proof proves, the result reported
> by H is incorrect, since D(D) halts.  I have compared the instructions
> executed by both H/Ĥ and THEY ARE EXACTLY THE SAME.  (In the region of 1000
> or so machine instructions, including the handful of simulated
> instructions.  Obviously stack addresses differ.  If required I could post
> the output log but its quite long.]
>
> So... in this case the exact same program is given the exact same input and
> gets the exact same result as Linz logic requires, and the outcome is
> exactly what Linz says.  There is really no mystery here that needs
> explaining by faulty coding/cheating with simulations on PO's part.

Yes, this was the crystal clear case that led PO to answer:

| do you still assert that H(P,P) == false is the "correct" answer even
| though P(P) halts?

PO: Yes that is the correct answer even though P(P) halts.

I think your analysis of the traces was a key part of getting that clear
statement from him.

> The HH/DD case is different, as that coding is completely broken by misuse
> of global variables to divert the course of the code under the simulator.
> But since EVEN WHEN THINGS WORK EXACTLY AS PO WANTS his results are in
> AGREEMENT with Linz, it seems to me that arguing that his problem is
> relating to cheating with the simulation is kind of missing the point.  Um,
> not to say there's much point arguing with PO even if making perfectly
> "on-point" arguments!  It all makes no difference to PO... :)

The irony here is that if one cheats it's possible to have H(D,D) (in
main, say) return 1 and yet have D(D) halt.  This can be done with D
constructed as usual.  It's only H that needs the cheat.  So to his
credit, he is not cheating, just totally at sea.

-- 
Ben.