Sysop: | Amessyroom |
---|---|
Location: | Fayetteville, NC |
Users: | 23 |
Nodes: | 6 (0 / 6) |
Uptime: | 52:16:24 |
Calls: | 583 |
Files: | 1,139 |
D/L today: |
105 files (7,722K bytes) |
Messages: | 111,533 |
Simulating (at least partial) halt decider -n.embedded_H
We assume the contrary, namely that there exists an algorithm,
and consequently some Turing machine H, that solves the halting problem
Simulating (at least partial) halt decider -n.embedded_H
either sees the repeating state of its input or not.
If it cannot possibly see the repeating state of its
input then we do know more about the halting problem
proof than we ever knew before, that the counter-example
input would be correctly decided as non-halting. We can
see that it is non-halting even if -n.embedded_H cannot.
*From the bottom of page 319 has been adapted to this* https://www.liarparadox.org/Peter_Linz_HP_317-320.pdf
-n.q0 rf?-nrf- reo* -n.embedded_H rf?-nrf- rf?-nrf- reo* -n.reR,
-n.q0 rf?-nrf- reo* -n.embedded_H rf?-nrf- rf?-nrf- reo* -n.qn
(a) -n copies its input rf?-nrf-
(b) -n invokes embedded_H rf?-nrf- rf?-nrf-
(c) embedded_H simulates rf?-nrf- rf?-nrf-
If -n.embedded_H rf?-nrf- rf?-nrf- can see the repeating state then
it will abort its simulation and correctly transition
to -n.qn on the basis that rf?-nrf- rf?-nrf- cannot possibly reach
its own simulated final halt state of rf?-n.qnrf-.
Turing machine deciders only compute the mapping
from their inputs...
Thus the behavior of the input would overrule the
behavior of -n applied to rf?-nrf- in this case. If this
behavior cannot be overruled then that would seem
to indicate that embedded_H rf?-nrf- rf?-nrf- cannot possibly
see the repeating state.
I can't know that -n.embedded_H rf?-nrf- rf?-nrf- cannot possibly
see the repeating state of its input until trying
every category of possible ways and failing.