Path: ...!weretis.net!feeder9.news.weretis.net!news.nk.ca!rocksolid2!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:50:36 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <35fb05d33cc5cbccbfd05d12f71ba7589ba0590f@i2pn2.org>
References: <1005jsk$3akrk$1@dont-email.me>
 <bc6f0f045212bdfb7f7d883426873a09e37789ea@i2pn2.org>
 <1005u6v$3cpt2$1@dont-email.me>
 <28e3bf7570b704d952e814b5e8a50bb11cbb1246@i2pn2.org>
 <100676j$3dmiv$3@dont-email.me>
 <16a3b842e76f2aadf811291c75dbc9389d397257@i2pn2.org>
 <1007ktd$3qb7l$11@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:28 -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
Content-Language: en-US
In-Reply-To: <1007ktd$3qb7l$11@dont-email.me>
Bytes: 4903
Lines: 90

On 5/16/25 11:17 AM, olcott wrote:
> On 5/16/2025 8:46 AM, Richard Damon wrote:
>> On 5/15/25 10:16 PM, olcott wrote:
>>> On 5/15/2025 9:02 PM, Richard Damon wrote:
>>>> On 5/15/25 7:43 PM, olcott wrote:
>>>>> On 5/15/2025 6:18 PM, Richard Damon wrote:
>>>>>> On 5/15/25 4:47 PM, 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.
>>>>>>
>>>>>> Nope, only to youtr INCORRECTLY simuated by HHH.
>>>>>>
>>>>>
>>>>> In other words you believe that professor Sipser
>>>>> screwed up when he agreed with these exact words.
>>>>
>>>> No, you just don't know the meaning of them.
>>>>
>>>>>
>>>>> <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>
>>>>>
>>>>>
>>>>>
>>>>
>>>> Remember, he works in Computation Theory, and thus talks about 
>>>> PROGRAMS, these BY DEFINITION include all of their algrorithm/code 
>>>> as part of themselves.
>>>>
>>>> You have admitted/stipuated that YOUR "DD" and "DDD" are NOT 
>>>> program, but just (non-leaf) "C functions", and thus his statement 
>>>> just doesn't apply to your system.
>>>>
>>>> Also, "its simulated D would never stop runnign unless aborted" 
>>>> means exactly that, The D that H was given 
>>>
>>> cannot possibly ever stop running unless aborted by H
>>
>> "Aborted by H" wasn't in the quote.
>>
> 
> Mike explains all of the details of how the
> above quote does derive a correct Simulating Halt Decider.
> 
> On 5/14/2025 7:36 PM, Mike Terry wrote:
>  > There is a natural (and correct) statement that Sipser
>  > is far more likely (I'd say) to have agreed to.
>  >
>  > First you should understand the basic idea behind a
>  > "Simulating Halt Decider" (*SHD*) that /partially/
>  > simulates its input, while observing each simulation
>  > step looking for certain halting/non-halting patterns
>  > in the simulation. A simple (working) example here
>  > is an input which goes into a tight loop.
> (Mike says much more about this)
> 
> *Click here to get the whole article*
> https://al.howardknight.net/? 
> STYPE=msgid&MSGI=%3C1003cu5%242p3g1%241%40dont-email.me%3E
> 
> Message-ID: <1003cu5$2p3g1$1@dont-email.me>
> 

Where he doesn't say as your claim.

First, he begins by fixing your error of not giving all the code, and 
shows an input that a SHD could decide.

Note, it isn't that the partial simulation of the SHD doesn't reach the 
end that is the criteria, but that we can show that no complete 
simulation of that input can do so.

WHen you try to do that with DDD, since we first have to add the code of 
the HHH that is claimed to be correct, when we actually simulate that 
past the point that HHH gives up, we see that the simulated HHH will 
process its own simulation of DDD for a while, give up and return 0, and 
thus DDD will halt.

Your argument about changing HHH has the side affect of changing the 
fixed DDD that is given to it, and thus we can't just compare the 
simulations.

THat is basically like says that since 1+1 = 2, 1 + 2 should be 2 also.