My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
LinkBack Thread Tools Display Modes
March 27th, 2018, 08:07 AM   #1
Member
 
Joined: Jun 2009

Posts: 81
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
honzik is offline  
 
March 27th, 2018, 11:54 AM   #2
Newbie
 
Joined: Oct 2013

Posts: 20
Thanks: 0

Quote:
Originally Posted by honzik View Post
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.
Borneq is offline  
March 27th, 2018, 12:26 PM   #3
Senior Member
 
Joined: Aug 2012

Posts: 1,846
Thanks: 507

Quote:
Originally Posted by honzik View Post
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.
Maschke is offline  
March 29th, 2018, 10:25 AM   #4
Newbie
 
Joined: Oct 2013

Posts: 20
Thanks: 0

https://en.wikipedia.org/wiki/Oracle_machine
Borneq is offline  
Reply

  My Math Forum > Science Forums > Computer Science

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 04:01 AM
Turing machine jenifer Applied Math 1 December 28th, 2011 11:08 AM
Turing machine 2 jenifer Applied Math 0 November 2nd, 2011 07:50 AM
Help On Turing Machine Problems Please Christi123 Applied Math 1 April 14th, 2008 04:33 AM
A Turing Machine Question Christi123 Applied Math 0 March 22nd, 2008 03:25 PM





Copyright © 2018 My Math Forum. All rights reserved.