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: Defining a correct halt decider
Date: Mon, 2 Sep 2024 12:28:23 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <62213a510257d3318cc04a736793997fe19f4a64@i2pn2.org>
References: <vb4npj$1kg8k$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Mon, 2 Sep 2024 16:28:23 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="602295"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
In-Reply-To: <vb4npj$1kg8k$1@dont-email.me>
Content-Language: en-US
X-Spam-Checker-Version: SpamAssassin 4.0.0
Bytes: 3262
Lines: 51

On 9/2/24 12:06 PM, olcott wrote:
> A correct halt decider is a Turing machine T with one accept state and 
> one reject state such that:
> 
> If T is executed with initial tape contents equal to an encoding of 
> Turing machine X and its initial tape contents Y, and execution of a 
> real machine X with initial tape contents Y eventually halts, the 
> execution of T eventually ends up in the accept state and then stops.
> 
> If T is executed with initial tape contents equal to an encoding of 
> Turing machine X and its initial tape contents Y, and execution of a 
> real machine X with initial tape contents Y does not eventually halt, 
> the execution of T eventually ends up in the reject state and then stops.

Right.

And if Turing Machine X duplicates its input Y and then uses a copy of 
Turing Machine T to determine that T applied to Y Y will do, and then do 
the opposite, of that, then when Y is set to an encoding of Turing 
Machine X, then the Turing Machine T can not correctly meet its 
requirements, as since X <X> uses its copy of T to see what T <X> <X> 
will do, and does the opposite, if T <X> <X> goes to its accept state, 
then X <X> will see that it does, and goes into an infinite loop, and it 
T <X> <X> goes to its reject state, then X <X> will see that and 
immediately halt.

Thus, it is IMPOSSIBLE for a Turing machine T to exist that meets its 
requirements, as there will ALWAYS exist a machine X, based on this 
"pathological relationship" with T that T can not get right.

Said X *IS* a valid machine, as Turing Machine T *WILL* either give one 
of the required answers, or fail to meets its requirements.

If T <X> <X> accepts, then X <X> will be a non-halting machine and T was 
wrong/

If T <X> <X> rejects, then X <X> will halt.

If T <X> <X> fails to decide by looping forever, then X <X> will never 
halt, and thus the CORRECT answer exists, of reject.

If T <X> <X> fails to decide by halting in some other final state, then 
X <X> will halt in that other final state, and thus the CORRECT answer 
exist, of accept.

So NO MATTER WHAT T does, (and the above is an exhaustive list of 
possible behaviors of T) there IS a correct answer that T "could" have 
given (but can't because it wasn't programmed to give that answer) so 
the question if valid.