My Math Forum Generalized Turing machine (TM)

 Computer Science Computer Science Forum

 March 27th, 2018, 08:07 AM #1 Member   Joined: Jun 2009 Posts: 83 Thanks: 1 Generalized Turing machine (TM) 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
March 27th, 2018, 11:54 AM   #2
Newbie

Joined: Oct 2013

Posts: 20
Thanks: 0

Quote:
 Originally Posted by honzik 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.

March 27th, 2018, 12:26 PM   #3
Senior Member

Joined: Aug 2012

Posts: 2,262
Thanks: 689

Quote:
 Originally Posted by honzik 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 by Maschke; March 27th, 2018 at 12:32 PM.

 March 29th, 2018, 10:25 AM #4 Newbie   Joined: Oct 2013 Posts: 20 Thanks: 0

 Tags generalized, machine, turing

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post krausebj0 Number Theory 1 June 28th, 2013 04:01 AM jenifer Applied Math 1 December 28th, 2011 11:08 AM jenifer Applied Math 0 November 2nd, 2011 07:50 AM Christi123 Applied Math 1 April 14th, 2008 04:33 AM Christi123 Applied Math 0 March 22nd, 2008 03:25 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top