3 ms·

According to my (admittedly minimal) understanding of Turing machines and the halting problem, a Turing machine has a set state encoded on the tape and then the

According to my (admittedly minimal) understanding of Turing machines and the halting problem, a Turing machine has a set state encoded on the tape and then the head starts running the program. I didn't think there was any provision in pure Turing machines for referencing external data, so to reference itself, Q must contain itself recursively on the tape to start with. If every copy of Q contains a full copy of Q within it then it must be an infinite length program, and any Turing machine will require infinite steps to even read it. I don't believe this "proof" for this reason.

cousin_it 7y ago
> If every copy of Q contains a full copy of Q within it then it must be an infinite length program Try running this Python program and see what it prints: w = "print('w = ' + chr(34) + w + chr(34) + chr(10) + w)" print('w = ' + chr(34) + w + chr(34) + chr(10) + w)
dtech 7y ago
Setting aside that turning machines have infinite tapes, it's easier to think of them as subroutines in a program. P(input: Program): Boolean = ??? Q(input: Program) = if(P(input)) loop() else stop() A() = Q(A) Writing the above program on a tape (source code file) can be done in fixed space (I've just done it above, no recursive definition required) While running the program a turing machine can inspect the piece of tape with the program input. It's as if a program is inspecting its own code, which is not only possible in a turing machine, but common to various degrees in languages like Lisp, Scala, Javascript, Java, PHP, Ruby and Python. You might know it as reflection or macros.
tomstuart 7y ago
Here’s the information you’re missing: https://en.wikipedia.org/wiki/Kleene's_recursion_theorem https://en.wikipedia.org/wiki/Kleene's_recursion_theorem
- deleted 7y ago
  [deleted]
pontifier 7y ago
Ok, I've made a fool of myself... not sure what I was thinking at the time. Thank you.

cousin_it 7y ago

> If every copy of Q contains a full copy of Q within it then it must be an infinite length program Try running this Python program and see what it prints: w = "print('w = ' + chr(34) + w + chr(34) + chr(10) + w)" print('w = ' + chr(34) + w + chr(34) + chr(10) + w)

dtech 7y ago

Setting aside that turning machines have infinite tapes, it's easier to think of them as subroutines in a program. P(input: Program): Boolean = ??? Q(input: Program) = if(P(input)) loop() else stop() A() = Q(A) Writing the above program on a tape (source code file) can be done in fixed space (I've just done it above, no recursive definition required) While running the program a turing machine can inspect the piece of tape with the program input. It's as if a program is inspecting its own code, which is not only possible in a turing machine, but common to various degrees in languages like Lisp, Scala, Javascript, Java, PHP, Ruby and Python. You might know it as reflection or macros.

tomstuart 7y ago

Here’s the information you’re missing: https://en.wikipedia.org/wiki/Kleene's_recursion_theorem https://en.wikipedia.org/wiki/Kleene's_recursion_theorem

deleted 7y ago
[deleted]

pontifier 7y ago

Ok, I've made a fool of myself... not sure what I was thinking at the time. Thank you.