views:

140

answers:

1

Hi!

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?

+5  A: 

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.

DigitalRoss
Ah, I see. Thanks.
Bubba88
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.
DigitalRoss
I was almost sure that there is no computational benefit in that modification, but your answer clarified that greatly.
Bubba88
Turing machines are as simple and restricted as they are because they are designed to be analyzed easily.
starblue