Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: dbush <dbush.mobile@gmail.com>
Newsgroups: comp.lang.c
Subject: Re: DD simulated by HHH cannot possibly halt (Halting Problem)
Date: Sat, 5 Apr 2025 19:15:56 -0400
Organization: A noiseless patient Spider
Lines: 118
Message-ID: <vssdjb$389d8$9@dont-email.me>
References: <vsnchj$23nrb$2@dont-email.me> <vsngo6$26agq$1@dont-email.me>
 <vsnh44$26c94$3@dont-email.me> <vsnht7$26agq$2@dont-email.me>
 <vsnlvv$2h8pt$1@dont-email.me> <vsnnb5$2g4cd$2@dont-email.me>
 <vsnnug$2h8pt$2@dont-email.me> <vsnou2$2g4cd$5@dont-email.me>
 <vspqmt$o89d$1@dont-email.me> <vsq97g$19eo9$1@dont-email.me>
 <vsqhov$1hl94$1@dont-email.me> <vsqmth$1mglg$2@dont-email.me>
 <vsrk17$2le7u$1@dont-email.me> <vsrlh7$2n0kg$1@dont-email.me>
 <vsrrnl$2ssgf$3@dont-email.me> <vsrtp0$2sut0$2@dont-email.me>
 <vsrun6$2ssgf$5@dont-email.me> <vss6g0$389d8$2@dont-email.me>
 <vss818$375du$10@dont-email.me> <vss8ft$389d8$6@dont-email.me>
 <vss8v3$3aqnp$1@dont-email.me> <vss93q$389d8$7@dont-email.me>
 <vssd48$3evdr$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 06 Apr 2025 01:15:57 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="bdf677863da665303917a0e1a85da663";
	logging-data="3417512"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+aqlx1isxfIkzefOHoJ4eT"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:PHBNdWRbkiKLaNUTuvVKMYFMwfA=
In-Reply-To: <vssd48$3evdr$1@dont-email.me>
Content-Language: en-US
Bytes: 6122

On 4/5/2025 7:07 PM, olcott wrote:
> On 4/5/2025 4:59 PM, dbush wrote:
>> On 4/5/2025 5:56 PM, olcott wrote:
>>> On 4/5/2025 4:48 PM, dbush wrote:
>>>> On 4/5/2025 5:40 PM, olcott wrote:
>>>>> On 4/5/2025 4:14 PM, dbush wrote:
>>>>>> On 4/5/2025 3:01 PM, olcott wrote:
>>>>>>> On 4/5/2025 1:45 PM, Richard Heathfield wrote:
>>>>>>>> On 05/04/2025 19:11, olcott wrote:
>>>>>>>>> On 4/5/2025 11:25 AM, dbush wrote:
>>>>>>>
>>>>>>>>>> On 4/5/2025 11:59 AM, olcott wrote:>>>>
>>>>>>>>>>> Introduction to the Theory of Computation 3rd Edition
>>>>>>>>>>> by Michael Sipser (Author) (best selling textbook)
>>>>>>>>>>>
>>>>>>>>>>> <MIT Professor Sipser agreed to ONLY these verbatim words 
>>>>>>>>>>> 10/13/2022>
>>>>>>>>>>>      If simulating halt decider H correctly simulates its 
>>>>>>>>>>> input D
>>>>>>>>>>>      until H correctly determines that its simulated D would 
>>>>>>>>>>> never
>>>>>>>>>>>      stop running unless aborted then
>>>>>>>>>>>
>>>>>>>>>>>      H can abort its simulation of D and correctly report that D
>>>>>>>>>>>      specifies a non-halting sequence of configurations.
>>>>>>>>>>> </MIT Professor Sipser agreed to ONLY these verbatim words 
>>>>>>>>>>> 10/13/2022>
>>>>>>>>>>
>>>>>>>>>> But not what you think he agreed to:
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>
>>>>>>> void DDD()
>>>>>>> {
>>>>>>>    HHH(DDD);
>>>>>>>    return;
>>>>>>> }
>>>>>>>
>>>>>>>>>
>>>>>>>>> You have to show that by showing the details of how
>>>>>>>>> what he agreed to is not accurately paraphrased by
>>>>>>>>> *Simulating termination analyzer Principle*
>>>>>>>>
>>>>>>>> No, you have to show firstly that your H determines anything at 
>>>>>>>> all about D's behaviour. 
>>>>>>>
>>>>>>> First of all it is the concrete DDD and the hypothetical HHH.
>>>>>>
>>>>>> Category error.  The algorithm DDD is not fully specified if the 
>>>>>> code of the function HHH and everything it calls explicitly 
>>>>>> spelled out, as all of that is the code under test.
>>>>>
>>>>> DDD meets the spec of the
>>>>> *Simulating termination analyzer Principle*
>>>>> as long as HHH emulates enough steps of DDD
>>>>> to see that it must stop simulating DDD.
>>>>>
>>>>
>>>> And as such is unrelated to the halting problem, as the halting 
>>>> problem is about algorithms, and DDD as you've defined it is not an 
>>>> algorithm:
>>>>
>>>
>>> OK great we are making progress.
>>> You agree that the specified DDD and a
>>> hypothetical HHH could meet the
>>> *Simulating termination analyzer Principle*
>>>
>>
>> Which you will be unable to link back to the halting problem:
>>
>>
>> Given any algorithm (i.e. a fixed immutable sequence of instructions) 
>> X described as <X> with input Y:
>>
>> A solution to the halting problem is an algorithm H that computes the 
>> following mapping:
>>
>> (<X>,Y) maps to 1 if and only if X(Y) halts when executed directly
>> (<X>,Y) maps to 0 if and only if X(Y) does not halt when executed 
>> directly
>>
> 
> *Yet may be able to link back to this*
> 
> <MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022>
>      If simulating halt decider H correctly simulates its input D
>      until H correctly determines that its simulated D would never
>      stop running unless aborted then
> 
>      H can abort its simulation of D and correctly report that D
>      specifies a non-halting sequence of configurations.
> </MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022>
> 

Which is not what you think he agreed to:


On Monday, March 6, 2023 at 2:41:27 PM UTC-5, Ben Bacarisse wrote:
 > I exchanged emails with him about this. He does not agree with anything
 > substantive that PO has written. I won't quote him, as I don't have
 > permission, but he was, let's say... forthright, in his reply to me.
 >


And the way you've defined it, a simulating halt decider is not a halt 
decider because it doesn't compute the required mapping:


Given any algorithm (i.e. a fixed immutable sequence of instructions) X 
described as <X> with input Y:

A solution to the halting problem is an algorithm H that computes the 
following mapping:

(<X>,Y) maps to 1 if and only if X(Y) halts when executed directly
(<X>,Y) maps to 0 if and only if X(Y) does not halt when executed directly