I'm having trouble with this problem as I haven't discovered a good way to determine the power of a Turing machine. I was under the impression that if a Turing machine can perform the same actions and satifies unrestricted access to unlimited memory they're all pretty much equivalent. Such as multiple tapes and nondeterministic Turing machines.
I am to determine if a and b are equal, more powerful or less powerful then a single-tape Turing machine. Where do I start?
a) A Turing Machine that can only make moves to the right and never left.
b) A Turing Machine that can move right one space or move left two spaces.
-
1$\begingroup$ Turing machine, not "turning machine"! $\endgroup$David Richerby– David Richerby2015年05月18日 22:00:15 +00:00Commented May 18, 2015 at 22:00
-
1$\begingroup$ You start by trying to simulate an arbitrary Turing machine using one that has the restriction you're interested in; if you fail, you try to prove that the restricted machine can't compute some function that an ordinary Turing machine can, or that it has some property that ordinary Turing machines don't. $\endgroup$David Richerby– David Richerby2015年05月18日 22:02:14 +00:00Commented May 18, 2015 at 22:02
-
$\begingroup$ Do you know the joke about this new kind of memory now sold on the market. After the ROM (read only memory) we now have the WOM (write only memory). I hope this helps you. $\endgroup$babou– babou2015年05月18日 23:36:49 +00:00Commented May 18, 2015 at 23:36
-
$\begingroup$ Related question: Single-tape Turing Machines with write-protected input recognize only Regular Languages $\endgroup$babou– babou2015年05月19日 13:04:45 +00:00Commented May 19, 2015 at 13:04
1 Answer 1
I was under the impression that if a Turing machine can perform the same actions and satifies unrestricted access to unlimited memory they're all pretty much equivalent.
Hint 1: So your first step should be to determine whether a and b have, or can obtain, unrestricted access to unlimited memory.
Hint 2: If yes, then try to emulate the missing pieces of your preferred Turing machine model.
Hint 3: If no, then try to show that the halting problem (with empty tape as input) is decidable.
-
$\begingroup$ Regarding hint 3, you should be more precise as to what halting problem you are referring to. I mean is it the halting problem for standard TM or for the mutilated TM of the question. $\endgroup$babou– babou2015年05月18日 23:39:38 +00:00Commented May 18, 2015 at 23:39