-4
$\begingroup$

A possibly new idea for a halt decider is proposed:
A halt decider is defined performs a pure simulation of its inputs (as if it was a UTM) until:
(a) its input reaches its own final state or
(b) its simulated input demonstrates a recognizable behavior pattern indicating that it would never reach its final state in any finite number of steps of simulation.

What final state does simplified Linz Ĥ applied to ⟨Ĥ⟩ transition to?

computation that halts … the Turing machine will halt whenever it enters a final state. (Linz:1990:234)

According to Linz any sequence of configurations that would never reach its final state in any finite number of steps is a non halting sequence

This discussion of the Linz proof applies to the full proof and was only simplified to reduce Turing Award (1999) winner Fred Brooks inessential complexity, thus making it easier to understand.

It can be verified as a research level question only when an honest and diligent effort is made to try to answer it thus not merely dismissing out-of-hand.

When the infinite loop appended to the Ĥ.qy path is removed the halt status of the input can be determined. How it is determined derives a key new insight.

The following is the exact Linz Ĥ applied to its own Turing machine description except that the infinite loop appended to the Ĥ.qy path has been removed:

q0 Wm ⊢* Ĥq0 Wm Wm ⊢* Ĥy1 qy y2
q0 Wm ⊢* Ĥq0 Wm Wm ⊢* Ĥy1 qn y2

The above Linz syntax has been simplified:
(a) The second start state has been renamed to Ḧ.qx.
(b) Variable names: Wm have been replaced by literals: ⟨Ḧ⟩.
(c) References to tape states (y1, y2) have been removed.
(d) All states are preceded by their machine name: Ḧ.
(e) Ĥ has been renamed to Ḧ

Ḧ.q0 ⟨Ḧ⟩ ⊢* Ḧ.qx ⟨Ḧ⟩ ⟨Ḧ⟩ ⊢* Ḧ.qy
Ḧ.q0 ⟨Ḧ⟩ ⊢* Ḧ.qx ⟨Ḧ⟩ ⟨Ḧ⟩ ⊢* Ḧ.qn

As the Linz text says a copy of the Linz H is at Ḧ.qx above. We will refer to this copy of H as embedded_H.

Computer scientists know that deciders compute the mapping from their inputs to a final accept or reject state. On this basis we know that embedded_H must compute the mapping from its input: ⟨Ḧ⟩ ⟨Ḧ⟩ to Ḧ.qy or Ḧ.qn.

Furthermore embedded_H must compute this mapping on the basis of the actual behavior specified by its input: ⟨Ḧ⟩ ⟨Ḧ⟩.

It is known that the UTM simulation of a Turing machine description is computationally equivalent to the direct execution of the same machine. This allows embedded_H to base its halt status decision on the behavior of the UTM simulation of its input.

H.q0 Wm W ⊢* H.qy iff UTM(Wm, W) halts
H.q0 Wm W ⊢* H.qn iff UTM(Wm, W) does not halt

computation that halts … the Turing machine will halt whenever it enters a final state. (Linz:1990:234)

The copy of H at Ḧ.qx computes the mapping from ⟨Ḧ⟩ ⟨Ḧ⟩ to final states Ḧ.qy or Ḧ.qn on the basis of the behavior of the UTM simulation of these inputs. The embedded copy of H performs a simulation of N steps of its input to determine:

If the full UTM simulation of ⟨Ḧ⟩ ⟨Ḧ⟩ would reach a final state of simulated ⟨Ḧ⟩ then embedded_H would transition to Ḧ.qy.

If the full UTM simulation of ⟨Ḧ⟩ ⟨Ḧ⟩ would never reach a final state of simulated ⟨Ḧ⟩ (an infinite execution behavior pattern has been recognized) then embedded_H would transition to Ḧ.qn.

enter image description here Linz, Peter 1990. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company. (318-320)

$\endgroup$
1
  • $\begingroup$ This can be verified as a research level question only when an honest and diligent effort is made to try to answer it. $\endgroup$
    – polcott
    Dec 26 '21 at 14:39
-2
$\begingroup$

Ḧq0 ⟨Ḧ⟩ ⊢* Ḧ.qx ⟨Ḧ⟩ ⟨Ḧ⟩ ⊢* Ḧ.qy
Ḧq0 ⟨Ḧ⟩ ⊢* Ḧ.qx ⟨Ḧ⟩ ⟨Ḧ⟩ ⊢* Ḧ.qn

Because it is known that the UTM simulation of a machine is computationally equivalent to the direct execution of this same machine H can always form its halt status decision on the basis of what the behavior of the UTM simulation of its inputs would be.

When embedded_H simulates ⟨Ḧ⟩ ⟨Ḧ⟩ these steps would keep repeating:
Ḧ copies its input ⟨Ḧ⟩ to ⟨Ḧ⟩ then embedded_H simulates ⟨Ḧ⟩ ⟨Ḧ⟩...

This shows that the input to embedded_H ⟨Ḧ⟩ ⟨Ḧ⟩ would never reach its final state thus conclusively proving that this input never halts.

This enables embedded_H to abort the simulation of its input and correctly transition to Ĥ.qn.

The above reasoning equally applies to the original Ĥ with the infinite loop appended to the Ĥ.qy state because this infinite loop path is never taken.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.