Re: Defining a correct halt decider

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.