Turing Machine Instruction Table

Question

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?

Androgyne

Answer 1

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.

Lallygag

It's a good question, without actually remembering the point of the TM, you managed to ask the central question behind its entire existance: what can it compute. Not bad. – Lallygag

I was almost sure that there is no computational benefit in that modification, but your answer clarified that greatly. – Androgyne

Turing machines are as simple and restricted as they are because they are designed to be analyzed easily. – Pruett

Answer 2

More completely: There's a difference between a "Universal Turing Machine" and a "Turing "Machine". An ordinary Turing Machine has a hardwired ruleset, so can't be self-modifying. What you've described is a Universal Turing Machine, which reads its ruleset off of the same tape that it uses for I/O, and has the ability to modify that ruleset. If the UTM has the ability to reload (reboot) that modified ruleset from tape, then it is in fact already self-modifying.

Marciano

Does anyone know why this would have been downvoted? I'm interested in hearing what I've said that may be considered wrong, but downvoting without comment doesn't provide much information to either me or to anyone else who may be reading. – Marciano