Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: DDD simulated by HHH cannot possibly halt (Halting Problem)
Date: Mon, 14 Apr 2025 11:28:18 +0300
Organization: -
Lines: 121
Message-ID: <vtigv2$s7va$1@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> <vt812b$2k4l1$3@dont-email.me> <vt9k2t$2e73$3@dont-email.me> <vt9k4q$1tds$2@dont-email.me> <vth3kq$3in23$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 14 Apr 2025 10:28:19 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="392555565981b926339f9f53b30a6ad2";
	logging-data="925674"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19jf1MIrC7s+XGscUDctVMK"
User-Agent: Unison/2.2
Cancel-Lock: sha1:1UPMK4tGAHLwf/F9IyKsMBg+3aA=

On 2025-04-13 19:34:49 +0000, olcott said:

> On 4/10/2025 6:27 PM, dbush wrote:
>> On 4/10/2025 7:26 PM, olcott wrote:
>>> On 4/10/2025 3:55 AM, Fred. Zwarts wrote:
>>>> 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.
>>> 
>>> Yet again over-your-head.
>>> Unless the first HHH aborts
>> 
>> Changing the input is not allowed.
> 
> int DD()
> {
>    int Halt_Status = HHH(DD);
>    if (Halt_Status)
>      HERE: goto HERE;
>    return Halt_Status;
> }
> 
> int main()
> {
>    HHH(DD);
> }

That is changing the input. The subject line specifies DDD.

-- 
Mikko