XPost: comp.theory, sci.logic, sci.math

On 3/11/2017 3:13 PM, peteolcott wrote:

http://LiarParadox.org/HP_Infinite_Recursion.pdf

As this page 319 of An Introduction to Formal Languages and Automata
by Peter Linz 1990 indicates

From H' we construct another Turing machine H-Hat. This new machine takes as input Wm, copies it then behaves exactly like H'.

q0 Wm |-* H-Hat q0 Wm Wm...

Page 320 indicates that we apply H-Hat to itself as input.

The problem is that every H-Hat needs a pair of inputs.

H-Hat takes an H-Hat as input and copies it so that it
can analyze how its input H-hat would analyze the copy
of H-Hat that it just made.

The input H-Hat would have to copy its own input H-Hat
so that it can analyze what its own input H-Hat would
do on its own input, on and on forever...

Copyright 2016 and 2017 Pete Olcott.

This post is my earliest USENET post regarding this key insight:

The halting theorem counter-examples present infinitely nested
simulation (non-halting) behavior to every simulating halt decider.

Here is the original published reference (August 2016) to this same idea:

It looks like the original specification provided
in the Linz text may be infinitely recursive in that
each TM requires its own input. We fix this by providing
simple input that definitely halts.

https://www.researchgate.net/publication/307509556_Self_Modifying_Turing_Machine_SMTM_Solution_to_the_Halting_Problem_concrete_example


--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)