<p>The center state is called embedded_H because the Linz text explains that that Ĥ is created entirely from prepending and appending states to the original Linz H. The Linz notation has been simplified. The notation refers to the definition of Ĥ near that bottom of the Linz proof shown above.</p>
<p>Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞<br>
Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn</p>
<p>When Ĥ is applied to ⟨Ĥ⟩ it copies its input and then transitions to the the start state of the original Linz H. Because embedded_H is a simulating partial halt decider the first thing that it does is simulate ⟨Ĥ⟩ applied to ⟨Ĥ⟩.</p>
<p>(a) Ĥ copies its input ⟨Ĥ⟩ <br>
(b) Ĥ invokes embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ <br>
(c) embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩ <br>
(d) simulated ⟨Ĥ⟩ copies its input ⟨Ĥ⟩ <br>
(e) simulated ⟨Ĥ⟩ invokes simulated<br> ----embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ <br>
(f) simulated embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩<br>
(g) goto (d) with one more level of simulation<br></p>
<p>Two complete simulations show a pair of identical TMD's are simulating a pair of identical inputs.  We can see this thus proving recursive simulation.</p>
<p>We can see that this would repeat in an endless cycle unless embedded_H (shown at qx) sees this repeating pattern and aborts its simulation.<br></p>
<p><a href="https://i.sstatic.net/liNIe.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/liNIe.png" alt="enter image description here" /></a></p>
<p>Because neither Ĥ applied to ⟨Ĥ⟩ nor ⟨Ĥ⟩ ⟨Ĥ⟩ correctly simulated by embedded_H would ever stop running unless embedded_H aborts its simulation embedded_H is necessarily correct to transition to its final reject state of Ĥ.qn.</p>
<p>Linz, Peter 1990. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company. (317-320)</p>

CC BY-SA 4.0
2021-12-25T14:38:49.463Z
2024-07-27T20:09:16.183Z
2024-07-27T20:09:16.183Z
polcott
<p>Everyone knows that it is impossible for a TM halt decider to derive the correct halt status for any input that does the opposite of whatever value it derives.</p>
<p>When we take the conventional ideas of:<br>
(a) UTM<br>
(b) TM Description<br>
(c) Decider<br>
and combine them together to become a simulating partial halt decider then we get a brand new perspective on the halting problem proofs.</p>
<p>Instead of computing the mapping from the actual Turing Machine computation that contains the partial halt decider we compute the mapping from the Turing Machine Description finite string of this machine.</p>
<p>But of course they must be the same computation, right? Everyone &quot;knows&quot; that a Turing Machine Description of a machine must have identical behavior to the machine, right?</p>
<p>When a simulating partial halt decider (based on a UTM) computes the mapping from its input Turing Machine Description (finite string) to the behavior that it specifies we see something new.</p>
<p><strong>When Ĥ is applied to ⟨Ĥ⟩</strong><br>
Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞ <br>
Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn   <br></p>
<p>The above is simplified notation for the Linz Turing machine Ĥ when it is applied to its own TM description.</p>
<p>Ĥ copies its own TM description and then invokes its embedded version of Linz H with two copies of this input. When embedded_H is based on a UTM it begins simulating ⟨Ĥ⟩ applied to ⟨Ĥ⟩.</p>
<p><a href="https://i.sstatic.net/9tpXE.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/9tpXE.png" alt="enter image description here" /></a></p>
<p><strong>Linz, Peter 1990</strong>. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company. (318-320)</p>

<turing-machines><decidability><halting-problem><undecidability><universal-turing-machines>
Does the Linz Ĥ applied to ⟨Ĥ⟩ correctly transition to its final reject state?
polcott
# Does the Linz Ĥ applied to ⟨Ĥ⟩ correctly transition to its final reject state?

(Asked by: username_0 on 2021-12-24)

Everyone knows that it is impossible for a TM halt decider to derive the correct halt status for any input that does the opposite of whatever value it derives.

When we take the conventional ideas of:  
(a) UTM  
(b) TM Description  
(c) Decider  
and combine them together to become a simulating partial halt decider then we get a brand new perspective on the halting problem proofs.

Instead of computing the mapping from the actual Turing Machine computation that contains the partial halt decider we compute the mapping from the Turing Machine Description finite string of this machine.

But of course they must be the same computation, right? Everyone "knows" that a Turing Machine Description of a machine must have identical behavior to the machine, right?

When a simulating partial halt decider (based on a UTM) computes the mapping from its input Turing Machine Description (finite string) to the behavior that it specifies we see something new.

**When Ĥ is applied to ⟨Ĥ⟩**  
Ĥ.q0 ⟨Ĥ⟩ ⊢\* embedded\_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢\* Ĥ.qy ∞   
Ĥ.q0 ⟨Ĥ⟩ ⊢\* embedded\_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢\* Ĥ.qn

The above is simplified notation for the Linz Turing machine Ĥ when it is applied to its own TM description.

Ĥ copies its own TM description and then invokes its embedded version of Linz H with two copies of this input. When embedded\_H is based on a UTM it begins simulating ⟨Ĥ⟩ applied to ⟨Ĥ⟩.

[![enter image description here](https://i.sstatic.net/9tpXE.png)](https://i.sstatic.net/9tpXE.png)

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

**Tags:** turing-machines, decidability, halting-problem, undecidability, universal-turing-machines


---

## 1 answers

### Answer by username_0 on 2021-12-25. Score: -3 | Accepted answer

The center state is called embedded\_H because the Linz text explains that that Ĥ is created entirely from prepending and appending states to the original Linz H. The Linz notation has been simplified. The notation refers to the definition of Ĥ near that bottom of the Linz proof shown above.

Ĥ.q0 ⟨Ĥ⟩ ⊢\* embedded\_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢\* Ĥ.qy ∞  
Ĥ.q0 ⟨Ĥ⟩ ⊢\* embedded\_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢\* Ĥ.qn

When Ĥ is applied to ⟨Ĥ⟩ it copies its input and then transitions to the the start state of the original Linz H. Because embedded\_H is a simulating partial halt decider the first thing that it does is simulate ⟨Ĥ⟩ applied to ⟨Ĥ⟩.

(a) Ĥ copies its input ⟨Ĥ⟩   
(b) Ĥ invokes embedded\_H ⟨Ĥ⟩ ⟨Ĥ⟩   
(c) embedded\_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩   
(d) simulated ⟨Ĥ⟩ copies its input ⟨Ĥ⟩   
(e) simulated ⟨Ĥ⟩ invokes simulated  
 ----embedded\_H ⟨Ĥ⟩ ⟨Ĥ⟩   
(f) simulated embedded\_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩  
(g) goto (d) with one more level of simulation

Two complete simulations show a pair of identical TMD's are simulating a pair of identical inputs. We can see this thus proving recursive simulation.

We can see that this would repeat in an endless cycle unless embedded\_H (shown at qx) sees this repeating pattern and aborts its simulation.

[![enter image description here](https://i.sstatic.net/liNIe.png)](https://i.sstatic.net/liNIe.png)

Because neither Ĥ applied to ⟨Ĥ⟩ nor ⟨Ĥ⟩ ⟨Ĥ⟩ correctly simulated by embedded\_H would ever stop running unless embedded\_H aborts its simulation embedded\_H is necessarily correct to transition to its final reject state of Ĥ.qn.

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


---

