Hacker News Reader

Comment by pontifier | Hacker News Reader

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.

View on HN

> 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)

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.

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

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

Reply on news.ycombinator.com