Generalized Turing machine (TM)

Jun 2009
83
1
So called "Church-turing thesis" says that Turing machine (TM) is the "strongest" computation device. (There exists of course other devices with equivalent strength as TM - even if it seems at first sight that these are stronger than TM.)

But what about following definition of "generalized" TM (GTM): in every step of this GTM not only the place on the tape is rewritten, state of GTM is changed and head is moved (which is the same as the "ordinal" TM) but at every step GTM can also change its own program, ie transition function.

In this fashion GTM can (as time runs) have eg. more and more states and maybe it can solve problems that "ordinary" TM cannot. Or it is not so and GTM is equivalent with TM?

Thank you for any answers
 
Oct 2013
20
0
but at every step GTM can also change its own program, ie transition function.
As I know , Turing Machine changes tape - program - makes no difference between code and data.
 
Aug 2012
2,496
781
In this fashion GTM can (as time runs) have eg. more and more states and maybe it can solve problems that "ordinary" TM cannot. Or it is not so and GTM is equivalent with TM?
I don't think this can make any difference.

Meta-argument: Your idea is simple enough that if it could compute anything a basic TM can't, someone would already have thought of it.

Argument: Your idea is that given input x, our program says:

- If input is x: Write y; Move tape forward/backward; replace current program with program z. Here we assume we have all TMs linearly ordered (by program length and lexicographically among programs of equal length).

But that's perfectly deterministic. It amounts to replacing each instruction of the original program with the n+1th instruction of the replacement program indicated by the original program. In other words after processing input x, we now have a new program. The next input is, say, x2. So we go to the new program (whose instructions are already known before we start execution) and see what its actions are for input x2 with the given state.

So in the end we really have one program. In other words we could write a TM that, given the complete ordered list of TMs, takes your program and replaces it with the new program reflecting the "replace the program at each step" idea.

This was a little handwavy but I'm pretty sure it's right. In the end you're just executing some new TM derived deterministically from the old one plus the fixed list of TMs.

Now we can go a step further. What if at each step we replace the existing program with a random TM, nevermind how we make the random selection.

Then I believe, but don't know enough CS to prove, that what we have is a nondeterministic TM, which has the same computational power as a plain old TM.
 
Last edited: