2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Turing machine, not "turning machine"! $\endgroup$ – David Richerby May 18 '15 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 May 18 '15 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 May 18 '15 at 23:36
  • $\begingroup$ Related question: Single-tape Turing Machines with write-protected input recognize only Regular Languages $\endgroup$ – babou May 19 '15 at 13:04
2
$\begingroup$

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.

$\endgroup$
  • $\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 May 18 '15 at 23:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.