Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: "Fred. Zwarts" <F.Zwarts@HetNet.nl>
Newsgroups: comp.theory
Subject: Re: DDD simulated by HHH cannot possibly halt (Halting Problem)
Date: Thu, 10 Apr 2025 10:55:38 +0200
Organization: A noiseless patient Spider
Lines: 92
Message-ID: <vt812b$2k4l1$3@dont-email.me>
References: <vsnchj$23nrb$2@dont-email.me> <vso4a5$302lq$1@dont-email.me>
 <vsqhuu$1hl94$2@dont-email.me> <vsqknb$1ldpa$1@dont-email.me>
 <vsrmn8$2o2f2$1@dont-email.me> <vstku7$p4u7$1@dont-email.me>
 <vsu95l$1c5kt$1@dont-email.me> <vt01l0$39kn7$1@dont-email.me>
 <vt28vk$1fe7a$1@dont-email.me> <vt2k6t$1onvt$1@dont-email.me>
 <vt3ef4$2flgf$1@dont-email.me> <vt3fgd$2gu7u$1@dont-email.me>
 <vt6apu$12sjs$2@dont-email.me> <vt6g1f$180qf$1@dont-email.me>
 <vt6lmk$1djk6$1@dont-email.me> <vt6mts$1c6b1$1@dont-email.me>
 <vt77vk$1t4il$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 10 Apr 2025 10:55:40 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="6b88f5c90d2054e63fc14f6dbfce082a";
	logging-data="2757281"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+uVEzg+f0Jhzvy+05/8gly"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:XHm6mhTi1THtpz9cHLhccNMdyJg=
Content-Language: nl, en-GB
In-Reply-To: <vt77vk$1t4il$1@dont-email.me>
Bytes: 5219

Op 10.apr.2025 om 03:47 schreef olcott:
> On 4/9/2025 3:56 PM, dbush wrote:
>> On 4/9/2025 4:35 PM, olcott wrote:
>>> On 4/9/2025 1:58 PM, Fred. Zwarts wrote:
>>>> Op 09.apr.2025 om 19:29 schreef olcott:
>>>>>
>>>>> On 4/8/2025 10:31 AM, Fred. Zwarts wrote:
>>>>>> Op 08.apr.2025 om 17:13 schreef olcott:
>>>>>>> On 4/8/2025 2:45 AM, Fred. Zwarts wrote:
>>>>>>>> Op 08.apr.2025 om 06:33 schreef olcott:
>>>>>>>>>
>>>>>>>>> typedef void (*ptr)();
>>>>>>>>> int HHH(ptr P);
>>>>>>>>>
>>>>>>>>> int DD()
>>>>>>>>> {
>>>>>>>>>    int Halt_Status = HHH(DD);
>>>>>>>>>    if (Halt_Status)
>>>>>>>>>      HERE: goto HERE;
>>>>>>>>>    return Halt_Status;
>>>>>>>>> }
>>>>>>>>>
>>>>>>>>> int main()
>>>>>>>>> {
>>>>>>>>>    HHH(DD);
>>>>>>>>> }
>>>>>>>>>
>>>>>>>>> *Simulating termination analyzer Principle*
>>>>>>>>> It is always correct for any simulating termination
>>>>>>>>> analyzer to stop simulating and reject any input that
>>>>>>>>> would otherwise prevent its own termination.
>>>>>>>>
>>>>>>>>
>>>>>>>> In this case there is nothing to prevent, because the finite 
>>>>>>>> string specifies a program that halts. 
>>>>>>>
>>>>>>> int DD()
>>>>>>> {
>>>>>>>    int Halt_Status = HHH(DD);
>>>>>>>    if (Halt_Status)
>>>>>>>      HERE: goto HERE;
>>>>>>>    return Halt_Status;
>>>>>>> }
>>>>>>>
>>>>>>> This stuff is simply over-your-head.
>>>>>>> HHH(DD) meets the above: *Simulating termination analyzer Principle*
>>>>>>> Anyone with sufficient competence with the C programming language
>>>>>>> will understand this.
>>>>>>>
>>>>>> Everyone with a little bit of C knowledge understands that if HHH 
>>>>>> returns with a value 0, then DDD halts. 
>>>>>
>>>>> DDD CORRECTLY SIMULATED BY HHH
>>>>> NOT ANY OTHER DAMN DDD IN THE UNIVERSE NITWIT.
>>>>>
>>>> If HHH would correctly simulate DD (and the functions called by DD) 
>>>> then the simulated HHH would return to DD and DD would halt.
>>>
>>> Simply over your level of technical competence.
>>>
>>>> But HHH failed to complete the simulation of the halting program, 
>>>
>>> HHH is only required to report on the behavior of its
>>> own correct simulation (meaning the according to the
>>> semantics of the C programming language) and would be
>>> incorrect to report on any other behavior.
>>
>> Which means HHH has conflicting requirements,
> 
> No, it just means that the ones that you have
> been saying are f-cked up and no-one noticed this before.
> 
>  > because to perform a
>  > correct simulation of its input it cannot halt itself, and therefore
>  > can't report that.
> In other words you simply "don't believe in" the variant
> form of mathematical induction that HHH uses.
> 
> A proof by induction consists of two cases. The first, the base case, 
> proves the statement for 𝑛=0 without assuming any knowledge of other 
> cases. The second case, the induction step, proves that if the statement 
> holds for any given case 𝑛=k, then it must also hold for the next case 
> 𝑛=k+1. These two steps establish that the statement holds for every 
> natural number 𝑛. The base case does not necessarily begin with 𝑛=0, but 
> often with 𝑛=1, and possibly with any fixed natural number 𝑛=𝒩, 
> establishing the truth of the statement for all natural numbers 𝑛 ≥ 𝒩. 
>   https://en.wikipedia.org/wiki/Mathematical_induction
> 
So the proof by induction shows that for any n HHH fails to complete the 
simulation. So, it has been proven that no HHH exists that is able to 
simulate correctly. It always aborts before it sees that the simulated 
HHH aborts as well.