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(i

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.