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,sci.logic
Subject: Re: D correctly simulated by H cannot possibly halt --- templates and
 infinite sets --- deciders
Date: Thu, 30 May 2024 17:20:12 +0200
Organization: A noiseless patient Spider
Lines: 53
Message-ID: <v3a5fc$1o4q1$2@dont-email.me>
References: <v3501h$lpnh$1@dont-email.me> <v3a3a3$1nupq$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 30 May 2024 17:20:12 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="9f8ee44a32d20ae863aaefdb80a74b69";
	logging-data="1839937"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1942SrEKnkUApfHrjOF4FKH"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:pKe9wTKENOW+NPZxpM5ECZM3tbk=
Content-Language: en-GB
In-Reply-To: <v3a3a3$1nupq$1@dont-email.me>
Bytes: 3069

Op 30.mei.2024 om 16:43 schreef olcott:
> On 5/28/2024 11:16 AM, olcott wrote:
>>
>> When Ĥ is applied to ⟨Ĥ⟩
>> Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
>> Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>>
>> *Formalizing the Linz Proof structure*
>> ∃H  ∈ Turing_Machines
>> ∀x  ∈ Turing_Machines_Descriptions
>> ∀y  ∈ Finite_Strings
>> such that H(x,y) = Halts(x,y)
>>
> 
> A decider computes the mapping from finite string inputs to
> its own accept or reject state.
> 
> A decider does not and cannot compute the mapping from
> Turing_Machine inputs to its own accept or reject state.
> 
> Halts(x,y) would report on the direct execution of x(y) thus ignores
> the pathological behavior of x correctly simulated by pure function H.
> This makes Halts(x,y) an incorrect measure of the correctness of H(x,y).

Why are you referring to the 'pathological behavior of x' if your claim 
is that the simulator does not even reach the part of DD (below) that 
contradicts the result of HH? This 'pathological behavior of x' is 
completely irrelevant. The problem is that a simulating decider is 
unable to handle the simulation of itself because it gets stuck in 
recursive simulation). That DD contradicts HH's result is completely 
irrelevant.

> 
> This is easier to see when we can see every single detail of all of
> the steps as an x86 execution trace of D correctly simulated by pure
> function H.
> 
> typedef int (*ptr)();  // ptr is pointer to int function in C
> 00       int HH(ptr p, ptr i);
> 01       int DD(ptr p)
> 02       {
> 03         int Halt_Status = HH(p, p);
> 04         if (Halt_Status)
> 05           HERE: goto HERE;
> 06         return Halt_Status;
> 07       }
> 08
> 09       int main()
> 10       {
> 11         HH(DD,DD);
> 12         return 0;
> 13       }