Path: ...!feeds.phibee-telecom.net!2.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: D correctly simulated by H cannot possibly halt --- templates and infinite sets
Date: Sat, 1 Jun 2024 11:20:08 +0300
Organization: -
Lines: 81
Message-ID: <v3eljo$2migl$1@dont-email.me>
References: <v3501h$lpnh$1@dont-email.me> <v3ci7v$283tt$1@dont-email.me> <v3cr8n$29gdk$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 01 Jun 2024 10:20:09 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="6553536d1ebba9134c01b65a06740e6f";
	logging-data="2837013"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/UZ3VByfOhoBaYtLigWj59"
User-Agent: Unison/2.2
Cancel-Lock: sha1:isy3CsZgY39sO8lMP++4DZavUgI=
Bytes: 3996

On 2024-05-31 15:44:22 +0000, olcott said:

> On 5/31/2024 8:10 AM, Mikko wrote:
>> On 2024-05-28 16:16:48 +0000, olcott said:
>> 
>>> typedef int (*ptr)();  // ptr is pointer to int function in C
>>> 00       int H(ptr p, ptr i);
>>> 01       int D(ptr p)
>>> 02       {
>>> 03         int Halt_Status = H(p, p);
>>> 04         if (Halt_Status)
>>> 05           HERE: goto HERE;
>>> 06         return Halt_Status;
>>> 07       }
>>> 08
>>> 09       int main()
>>> 10       {
>>> 11         H(D,D);
>>> 12         return 0;
>>> 13       }
>>> 
>>> 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,x)
>>> 
>>> *Here is the same thing applied to H/D pairs*
>>> ∃H ∈ C_Functions
>>> ∀D ∈ x86_Machine_Code_of_C_Functions
>>> such that H(D,D) = Halts(D,D)
>>> 
>>> In both cases infinite sets are examined to see
>>> if any H exists with the required properties.
>> 
>> That says nothing about correct simulation. It says
>> something abuout some D but not whether it is correctly
>> simulated. Also nothing is said about templates or
>> infinite sets. At the end is claimed that some
>> infinite sets are examined but not who examined, nor
>> how, nor what was found in the alleged examination.
>> 
> 
> *Formalizing the Linz Proof structure*
> ∃H  ∈ Turing_Machines
> ∀x  ∈ Turing_Machines_Descriptions
> ∀y  ∈ Finite_Strings
> such that H(x,y) = Halts(x,x)

The above is the counter hypothesis for the proof. Proof structore
is that a contradiction is derived from the counter hypthesis.

> The above disavows Richard's claim based on a misinterpretation of
> Linz that the Linz proof is about a single specific Turing machine.

Your ∃H declares H as a new symbol for a specific Turing machine.
Therefore everything that follows refers to that specific Turing machine.
There may be others that could be discussed the same way but they aren't.

>     The domain of this problem is to be taken as the set of
>     all Turing machines and all w; that is, we are looking
>     for a single Turing machine that, given the description
>     of an arbitrary M and w, will predict whether or not the
>     computation of M applied to w will halt.

Note the words "a single Turing machine".

> Linz <IS NOT> looking for a single machine that gets the wrong answer.
> Linz is looking for at least one Turing Machine that gets the right
> answer: ∃H ∈ Turing_Machines

Not at least one but exactly one. The Halting Problem asks for one
or a proof that there is none.

-- 
Mikko