Path: ...!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: Fri, 31 May 2024 16:12:50 +0300
Organization: -
Lines: 76
Message-ID: <v3cici$284kt$1@dont-email.me>
References: <v3501h$lpnh$1@dont-email.me> <v362eu$2d367$3@i2pn2.org> <v363js$vg63$2@dont-email.me> <v36803$2d368$3@i2pn2.org> <v368je$100kd$3@dont-email.me> <v36rlr$13000$1@dont-email.me> <v37aa6$159q4$4@dont-email.me> <v38eqb$2foi0$5@i2pn2.org> <v38fl6$1bndb$2@dont-email.me> <v38g36$2foi0$12@i2pn2.org> <v38gpi$1bndb$4@dont-email.me> <v38ibi$2fohv$1@i2pn2.org> <v38ilr$1c8ir$1@dont-email.me> <v38j78$2foi0$13@i2pn2.org> <v38jqc$1c8ir$3@dont-email.me> <v38khd$2foi0$16@i2pn2.org> <v38mb0$1ggjs$2@dont-email.me> <v38o1v$2fohv$4@i2pn2.org> <v38on0$1grj4$2@dont-email.me> <v38pqr$2fohv$5@i2pn2.org> <v38suu$1hf5c$1@dont-email.me> <v39jcc$1ktqb$2@dont-email.me> <v39o5f$2h667$3@i2pn2.org> <v3c32a$25inu$1@dont-email.me> <v3c4el$25nvj$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 31 May 2024 15:12:51 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="712b1ae307b3aa2da9924d76e81b0b6d";
	logging-data="2364061"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX180pkiKXFeRFqxZVaYcpZf0"
User-Agent: Unison/2.2
Cancel-Lock: sha1:rd6+fjj8ZLpqp4K82pigNBmtW28=
Bytes: 4189

On 2024-05-31 09:15:01 +0000, immibis said:

> On 31/05/24 10:51, Mikko wrote:
>> On 2024-05-30 11:33:03 +0000, Richard Damon said:
>> 
>>> On 5/30/24 6:11 AM, immibis wrote:
>>>> On 30/05/24 05:48, olcott wrote:
>>>>> On 5/29/2024 9:55 PM, Richard Damon wrote:
>>>>>> On 5/29/24 10:36 PM, olcott wrote:
>>>>>>> On 5/29/2024 9:25 PM, Richard Damon wrote:
>>>>>>>> On 5/29/24 9:55 PM, olcott wrote:
>>>>>>>>> When the category is examined all at once then there is no need
>>>>>>>>> to look at each individual element.
>>>>>>>> 
>>>>>>>> So, which one or ones gave the correct answer for their input?
>>>>>>>> 
>>>>>>> 
>>>>>>> *Formalizing the Linz Proof structure*
>>>>>>> ∃H  ∈ Turing_Machines
>>>>>>> ∀x  ∈ *Turing_Machines_Descriptions*
>>>>>>> ∀y  ∈ Finite_Strings
>>>>>>> such that H(x,y) = Halts(x,y)
>>>>>>> 
>>>>>>> When we formalize it that way then some simulating halt deciders
>>>>>>> get the correct answer.
>>>>>>> 
>>>>>>> *Everyone else implicitly assumes this incorrect formalization*
>>>>>>> ∃H  ∈ Turing_Machines
>>>>>>> ∀x  ∈ *Turing_Machines*
>>>>>>> ∀y  ∈ Finite_Strings
>>>>>>> such that H(x,y) = Halts(x,y)
>>>>>>> 
>>>>>>> 
>>>>>> 
>>>>>> Nope.
>>>>>> 
>>>>>> You just don't understand the meaning of a "Description" in the problem.
>>>>>> 
>>>>> 
>>>>> A deciders compute the mapping FROM ITS INPUTS
>>>>> to it own accept or reject state
>>>>> Deciders cannot take ACTUAL TURING MACHINES AS INPUTS
>>>>> Deciders can only take FINITE STRINGS AS INPUTS
>>>>> 
>>>> 
>>>> If you want to be pedantic, you made the mistake.
>>>> It's actually H(DescriptionOf(x),y) = Halts(x,y)
>>>> DescriptionOf is an injective function that converts Turing machines 
>>>> into finite strings.
>>> 
>>> OR in his formal language:
>>> 
>>> 
>>> ∃H  ∈ Turing_Machines, and for
>>> ∀M  ∈ Turing_Machines, which have a description Wm, and
>>> ∀w  ∈ Finite_Strings
>>> such that H(Wm,w) = Halts(M,w)
>>> 
>>> The problem is that there doesn't exist a FUNCTION "Description" as one 
>>> machine can have an potentially infinite number of descriptions.
>> 
>> At this point we may assume the axiom of choice.
>> 
>>> It is more that there is an inverse function, Described where we could 
>>> say that M = Described(Wm)
>> 
>> 
> also the function "Description" doesn't have to 'know' all of the 
> descriptions - one per machine is enough.

OTOH, the Turing machine must answer the same way about all descriptions
that describe the same.

-- 
Mikko