Path: ...!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: Defining a correct halt decider
Date: Thu, 5 Sep 2024 10:39:41 +0300
Organization: -
Lines: 39
Message-ID: <vbbn7t$8ocm$1@dont-email.me>
References: <vb4npj$1kg8k$1@dont-email.me> <vb6i8p$39fhi$1@dont-email.me> <vb72a4$3b4ub$6@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 05 Sep 2024 09:39:42 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="41e98385bc3f4fa14336b6e96bd31129";
	logging-data="287126"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19ZTetpvto6XNEz2hVL65UG"
User-Agent: Unison/2.2
Cancel-Lock: sha1:+o222MZ4WIorjk528oZLqtrK6AQ=
Bytes: 2477

On 2024-09-03 13:17:56 +0000, olcott said:

> On 9/3/2024 3:44 AM, Mikko wrote:
>> On 2024-09-02 16:06:11 +0000, olcott said:
>> 
>>> 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.
>> 
>> Your "definition" fails to specify "encoding". There is no standard
>> encoding of Turing machines and tape contents.
> 
> That is why I made the isomorphic x86utm system.
> By failing to have such a concrete system all kinds
> of false assumptions cannot be refuted.

If it were isnomorphic the same false assumtipns would apply to both.

> The behavior of DDD emulated by HHH** <is> different
> than the behavior of the directly executed DDD**
> **according to the semantics of the x86 language

The halting problem is not about a string but about a behaviour.
Your decider is not a halt decider if it answers about another
behaviour.

-- 
Mikko