Sujet : Defining a correct halt decider
De : news (at) *nospam* immibis.com (olcott)
Groupes : comp.theoryDate : 02. Sep 2024, 17:06:11
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <vb4npj$1kg8k$1@dont-email.me>
User-Agent : Mozilla Thunderbird
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.