
Computer Science Computer Science Forum 
 LinkBack  Thread Tools  Display Modes 
March 27th, 2018, 09:07 AM  #1 
Member Joined: Jun 2009 Posts: 83 Thanks: 1  Generalized Turing machine (TM)
So called "Churchturing 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, 12:54 PM  #2 
Newbie Joined: Oct 2013 Posts: 20 Thanks: 0  
March 27th, 2018, 01:26 PM  #3  
Senior Member Joined: Aug 2012 Posts: 2,102 Thanks: 606  Quote:
Metaargument: 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 01:32 PM.  
March 29th, 2018, 11:25 AM  #4 
Newbie Joined: Oct 2013 Posts: 20 Thanks: 0  

Tags 
generalized, machine, turing 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Turing Machine  krausebj0  Number Theory  1  June 28th, 2013 05:01 AM 
Turing machine  jenifer  Applied Math  1  December 28th, 2011 12:08 PM 
Turing machine 2  jenifer  Applied Math  0  November 2nd, 2011 08:50 AM 
Help On Turing Machine Problems Please  Christi123  Applied Math  1  April 14th, 2008 05:33 AM 
A Turing Machine Question  Christi123  Applied Math  0  March 22nd, 2008 04:25 PM 