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.

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\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, 2015 at 23:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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