Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.theory
Subject: Re: Overcoming the proof of undecidability of the Halting Problem by
 a simple example in C
Date: Fri, 16 May 2025 10:22:59 -0500
Organization: A noiseless patient Spider
Lines: 74
Message-ID: <1007l8j$3qb7l$13@dont-email.me>
References: <1005jsk$3akrk$1@dont-email.me>
 <FAsVP.790302$BFJ.344089@fx13.ams4> <1005la7$3akrk$3@dont-email.me>
 <1006nrh$3l52k$1@dont-email.me> <1007jub$3qb7l$5@dont-email.me>
 <yAIVP.1247143$4AM6.528994@fx17.ams4>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Fri, 16 May 2025 17:23:00 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="a793c50ac46b1404361ae4f1062ef558";
	logging-data="4009205"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+958KfGrI4xoG26hdx3P2A"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:ltyVmFM/QWiTklcs+iNOyRw3ySE=
X-Antivirus: Norton (VPS 250516-4, 5/16/2025), Outbound message
Content-Language: en-US
X-Antivirus-Status: Clean
In-Reply-To: <yAIVP.1247143$4AM6.528994@fx17.ams4>
Bytes: 3529

On 5/16/2025 10:11 AM, Mr Flibble wrote:
> On Fri, 16 May 2025 10:00:26 -0500, olcott wrote:
> 
>> On 5/16/2025 2:01 AM, Mikko wrote:
>>> On 2025-05-15 21:11:35 +0000, olcott said:
>>>
>>>> On 5/15/2025 3:59 PM, Mr Flibble wrote:
>>>>> On Thu, 15 May 2025 15:47:16 -0500, olcott wrote:
>>>>>
>>>>>> I overcome the proof of undecidability of the Halting Problem in
>>>>>> that the code that "does the opposite of whatever value that HHH
>>>>>> returns" becomes unreachable to DD correctly simulated by HHH.
>>>>>>
>>>>>> int DD()
>>>>>> {
>>>>>> int Halt_Status = HHH(DD);
>>>>>> if (Halt_Status)
>>>>>> HERE: goto HERE;
>>>>>> return Halt_Status;
>>>>>> }
>>>>>>
>>>>>> HHH simulates DD that calls HHH(DD) to simulate itself again over
>>>>>> and over until HHH sees this repeating pattern and aborts or both
>>>>>> HHH and DD crash due to OOM error.
>>>>>
>>>>> It is not possible for HHH to simulate DD because we are already
>>>>> inside DD when we call HHH:
>>>
>>> A partial simulation is possible. But at some point HHH discontinues
>>> the simulation and returns a guessed answer.
>>>
>>>
>> void DDD()
>> {
>>     HHH(DDD);
>>     return;
>> }
>>
>> int main()
>> {
>>     HHH(DDD);
>> }
>>
>> HHH simulates DDD the simulated DDD calls HHH(DDD)
>>
>> HHH simulates DDD the simulated DDD calls HHH(DDD)
>>
>> HHH simulates DDD the simulated DDD calls HHH(DDD)
>>
>> HHH simulates DDD the simulated DDD calls HHH(DDD)
>>
>> HHH simulates DDD the simulated DDD calls HHH(DDD)
>>
>> How many more times before the fact that DDD correctly simulated by HHH
>> cannot possibly reach its "return" statement?
> 
> How many more times before you realise that this recursion is due to the
> category error I have identified and as such it is undecidable.
> 
> /Flibble

It would be a category error for HHH to report
anything to an input DD that actually does the
opposite of whatever value that HHH returns.
No such DD can possibly exist.

int main()
{
   DD(); // HHH cannot report on its caller.
}

-- 
Copyright 2025 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer