0
$\begingroup$

What is the power of a Turing-machine that cannot write?

So it can still read and go back and forth on the tape, but it cannot write.

I am wondering what this would be equivalent to in the computational hierarchy.

I suppose this would be a finite-state automaton, but it can go left and right along the input: does that increase its powers?

$\endgroup$
  • $\begingroup$ It's called a two-way finite automaton. $\endgroup$ – xavierm02 Dec 3 '18 at 17:25
  • $\begingroup$ @xavierm02 Ah, it has a name, great! Is it more powerful than a one-way FSA? I am guessing not but don't know ... that's really my question. $\endgroup$ – Bram28 Dec 3 '18 at 17:29
  • $\begingroup$ According to Wikipedia, it is equivalent to finite automaton (even if you allow non-determinism). $\endgroup$ – xavierm02 Dec 3 '18 at 17:31
  • $\begingroup$ @xavierm02 Yes, just read that as well: en.wikipedia.org/wiki/Two-way_finite_automaton Thanks!! $\endgroup$ – Bram28 Dec 3 '18 at 17:31

Your Answer

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

Browse other questions tagged or ask your own question.