Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: Final Statement on the Halting Problem
Date: Mon, 16 Jun 2025 12:58:16 +0300
Organization: -
Lines: 49
Message-ID: <102opro$1i6et$1@dont-email.me>
References: <7hA3Q.159938$vK4b.76905@fx09.ams4> <102mmiq$uef9$9@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 16 Jun 2025 11:58:17 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="3795de73c269ac0a9bf03e7bfc174b6b";
	logging-data="1645021"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18JVqo9ZD3PgSsiI4Na+xny"
User-Agent: Unison/2.2
Cancel-Lock: sha1:2CCalh7iEocXoPBlrdjxva/YcaE=

On 2025-06-15 14:50:01 +0000, olcott said:

> On 6/15/2025 8:55 AM, Mr Flibble wrote:
>> The halting problem as defined ignores recursive self reference focusing
>> on the paradox instead, I would argue the recursive self reference leads
>> to infinite regress in the definition of the problem thus creating a
>> category error making the problem definition itself ill-formed.
>> 
>> /Flibble
> 
> When we understand that all partial halt deciders are
> required to report on the behavior of the sequence of
> state transitions that its input actually specifies

That does not help much unitl it is understood how an input
defines a sequence of state transitions and how one can
find out what that sequence of state transition is, at
least to the extent that one can know whether the sequence
has an end.

> then the conventional HP proof fails.

No, it does not. Validity of the proof does not depend on
who does and who does not understand it. If the proof is
made sufficiently formal it can be werified with a proof
verifying tool that does not understand anything.

>  The counter
> example input is simply determined to be non-halting.
> 
> <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>
> 
> The criteria agreed to by the best selling author of theory
> of computation textbooks agrees.

No, they do not agree that that a H can correctly report that
D specifies a non-halting seqeunce of configurations if D
specifies a halting sequence of configurations.

-- 
Mikko