Search code examples
turing-machinesinstructions

Turing Machine Instruction Table


The definitions of Turing Machine say that it is prohibited for one to read/modify it's instruction table (program). Exactly, Turing Machine has no access to it's own program.

What benefits can be achieved if one could weaken this restriction? If a machine could analise and/or modify it's program. Would that extend the class of turing-computable tasks?


Solution

  • The Turing machine can already implement another Turing machine, and change its rules, say, to take as input a modifiable program. In particular, the Turing machine can compute any computable function. It could in theory implement a lisp interpreter, which would have macros, "self-modifing" code, etc.

    So, the answer is NO. Remember, no one, and I mean absolutely no one person anywhere, ever, has actually wanted a Turing machine, though no doubt zillions of simulators have been written. (I won't admit to it, but as an undergrad I may have done something like that...) It's just something that various important proofs are based on.