Path: news.eternal-september.org!eternal-september.org!feeder3.eternal-september.org!news.quux.org!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: Michael Sipser of MIT validates the notion of a simulating halt
 decider
Date: Fri, 16 May 2025 10:07:14 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <4baed7dfcfda7b264004e540aad20b5d58efc2c5@i2pn2.org>
References: <ti6l95$1h8qt$1@dont-email.me> <ikH1L.623536$iiS8.264549@fx17.iad>
 <ti7g4u$1jb5g$1@dont-email.me> <87bkqg4n7v.fsf@nosuchdomain.example.com>
 <4R2dnb1_sKrBsb_1nZ2dnZfqlJ-dnZ2d@giganews.com>
 <vvvj5i$1rc7v$4@dont-email.me> <1001fu2$2ckp5$1@dont-email.me>
 <1002as6$2i4bk$3@dont-email.me> <100435l$30lvi$1@dont-email.me>
 <1006917$3dmiv$6@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 14:07:45 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="604827"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
Content-Language: en-US
X-Spam-Checker-Version: SpamAssassin 4.0.0
In-Reply-To: <1006917$3dmiv$6@dont-email.me>

On 5/15/25 10:48 PM, olcott wrote:
> On 5/15/2025 1:55 AM, Mikko wrote:
>> On 2025-05-14 14:55:02 +0000, olcott said:
>>
>>> On 5/14/2025 2:15 AM, Mikko wrote:
>>>> On 2025-05-13 13:58:09 +0000, olcott said:
>>>>
>>>>> On 5/13/2025 2:46 AM, Mikko wrote:
>>>>>> On 2025-05-12 17:14:03 +0000, olcott said:
>>>>>>
>>>>>>> On 10/12/2022 6:49 PM, Keith Thompson wrote:
>>>>>>>> olcott <polcott2@gmail.com> writes:
>>>>>>>>> On 10/12/2022 5:37 PM, Richard Damon wrote:
>>>>>>>>>> On 10/12/22 11:08 AM, olcott wrote:
>>>>>>>>>>> Professor Michael Sipser of MIT said that this verbatim 
>>>>>>>>>>> paragraph
>>>>>>>>>>> looks correct:
>>>>>>>>>
>>>>>>>>> <quoted email to professor Sipser>
>>>>>>>>> Here is what I would like to say:
>>>>>>>>>
>>>>>>>>> Professor Michael Sipser of MIT said that this verbatim paragraph
>>>>>>>>> looks correct:
>>>>>>>>>
>>>>>>>>> If H does correctly determine that its correct simulation
>>>>>>>>> of D would never stop  running unless aborted, would it be
>>>>>>>>> correct for H to abort this simulation and report that D
>>>>>>>>> specifies a non-halting sequence of configurations?
>>>>>>>>>
>>>>>>>>> This validates the idea of a simulating halt decider referenced in
>>>>>>>>> this paper.
>>>>>>>>>
>>>>>>>>> Rebutting the Sipser Halting Problem Proof
>>>>>>>>> https://www.researchgate.net/ 
>>>>>>>>> publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof
>>>>>>>>>
>>>>>>>>> Professor Sipser has not had the time to carefully review this 
>>>>>>>>> paper
>>>>>>>>> presented to him.
>>>>>>>>> </quoted email to professor Sipser>
>>>>>>>>>
>>>>>>>>> <quoted reply from professor Sipser>
>>>>>>>>> Looks ok.  Thanks for checking.
>>>>>>>>> </quoted reply from professor Sipser>
>>>>>>>>>
>>>>>>>>>> IF I drop by and ask him face to face, will he confirm this?
>>>>>>>>>
>>>>>>>>> Yes.
>>>>>>>>
>>>>>>>> Would Professor Sipser agree that you have refuted his halting 
>>>>>>>> problem
>>>>>>>> proof?
>>>>>>>>
>>>>>>>> If I understand this correctly, it does not support the idea that a
>>>>>>>> general "simulating halt decider" can actually exist.
>>>>>>>>
>>>>>>>> In the above, let D be a program that may or may not halt, and 
>>>>>>>> let H be
>>>>>>>> an observer who attempts to determine whether or not D halts.
>>>>>>>> Concretely, let D be this C program or equivalent:
>>>>>>>>
>>>>>>>> int main(void) { while (1) { } }
>>>>>>>>
>>>>>>>> and I'll be H.  I can observe D.  I can simulate it until I get 
>>>>>>>> bored,
>>>>>>>> which won't take long (one iteration, two iterations, three 
>>>>>>>> iterations,
>>>>>>>> zzzzzzzzz).  I can, while simulating it, conclude that it will 
>>>>>>>> never
>>>>>>>> halt, abort the simulation, and report that it never halts.  It 
>>>>>>>> wouldn't
>>>>>>>> be difficult to automate the process in a way that works for 
>>>>>>>> this simple
>>>>>>>> case.
>>>>>>>
>>>>>>> My scope is to prove that the "impossible"
>>>>>>> input to all the halting problem proofs <is>
>>>>>>> decidable.
>>>>>>
>>>>>> As it is provably impossible it is not possible. The nearest you 
>>>>>> can hope
>>>>>> is to construct an oracle that can do what a Turing machine cannot 
>>>>>> do. It
>>>>>> would not be easy, just not yet proven imposssible.
>>>>>
>>>>> Not at all. No one ever bothered to notice that
>>>>> the contradictory part is unreachable code because
>>>>> the counter-example input gets stuck in recursive
>>>>> simulation. HHH simply sees this repeating pattern
>>>>> and rejects DD.
>>>>
>>>> As that does not identify any error in any proof it does not matter
>>>> whether that is noticed or not. What is soundly proven impossible
>>>> is impossible.
>>>
>>> It is an error in the foundational basis of the proof.
>>> When we assume that input DD can actually do the opposite
>>> of whatever value that HHH reports then no HHH can correctly
>>> report on the behavior of DD.
>>
>> No. It does not point to a wrong word or clause or sentence in the
>> founcdational basis of the proof.
>>
>>> No such DD can possibly exist.
>>
>> True but uninteresting. The important point is that no halt decider
>> exist. That a DD cannot be constructed from a non-existinghalt
>> decider is a rather obvious but not interesting.
>>
> 
> There cannot possibly be any input D to a simulating
> termination analyzer H that actually does the opposite
> of whatever value that H returns.

Sure there can, since "actually does" is defined by the exectution of 
the input, not by the analyzers partial simulation.

By your logic, EVERY program can be called non-halting,

> 
> We can't even code an incorrect H this way because
> no such D can possibly exist.

Sure we can, and I have done it.

> 
> people talk about directly executed as if
> 
> int main()
> {
>    DD();
> }
> 
> The HHH called by DD can possibly report on the
> behavior of its caller.

Well, it isn't being asked that, it is being asked to report on the 
program specified by the input.

That is like saying you can't say how far it is to El Paso if you are on 
the road to El Paso.

> 
> They never thought this through.

Because it isn't the question.

> 
> They all go by: The infallible word of textbook
> says its so therefore it is true even when it is false.
> 

And you go by the lying words of Peter Olcott.

Textbooks quoting the actual defintions are a lot better than words 
stated by a man who has declared that he didn't actually study the field 
as that might brainwash him into its false ideas.