Path: news.eternal-september.org!eternal-september.org!feeder3.eternal-september.org!i2pn.org!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
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 11:43:29 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <e9166286602f33e9a4149fb2d45efd04a2251314@i2pn2.org>
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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 16 May 2025 15:57:26 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="617720"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
X-Spam-Checker-Version: SpamAssassin 4.0.0
In-Reply-To: <1007jub$3qb7l$5@dont-email.me>
Content-Language: en-US

On 5/16/25 11:00 AM, 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?
> 

Well, as soon as HHH is defined to not get itself stuck in the loop, and 
thus not be the correct simulator of the input, that the correct 
simulaiton of the input, that references that actual HHH will reach the 
final state.

So, how many times, FOREVER, as any less and it doesn't correct simulate 
the input.

The fact that this makes it not a decider just shows that simulating 
halt deciders can't be both a correct simulator and a correct halt 
decider for all inputs (or even this one input).

Sorry, your truth fairy can't help you with this, as you are stuck in 
reality here.