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 17:59:23 -0400
Organization: A noiseless patient Spider
Lines: 77
Message-ID: <vss93q$389d8$7@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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 05 Apr 2025 23:59:22 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="43eaa133a904c8986c7a0672d25633a8";
	logging-data="3417512"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/yvTyhe+3g51CjxRyWnMJw"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:KYGxZtpA9JNt7lbyxSDh9aqHoxU=
In-Reply-To: <vss8v3$3aqnp$1@dont-email.me>
Content-Language: en-US
Bytes: 4432

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