Re: Restricted Turing machine

"Bjarke Walling" <bjarke.walling@xxxxxxxxx> writes:

Hi,

I've just finished a course on Computability and Logic, but I have an
unanswered question which I would like to post here.

If you imagine that you create a restricted Turing machine by limiting
the tape to contain only a finite number of cells, what languages would
it recognize (and accept)?

There are many different special cases of this, for example:

- If you restrict the tape to be read-only, so it only ever holds the
input, you have regular languages. This is also true if you add a
fixed (input-independent) number of read-write cells to the tape.

- If, additionally, you allow a fixed, input-independent number of
read-heads to the tape, you have log-space, which includes
languages of matching parentheses (with N types of parenteses).

- If you restrict the tape to the length of the input, but allow the
TM to write back to the tape, you have Chomsky Type-1 languages
(also called context-dependent languages). The compexity class is
linear-space.

Torben
.

Relevant Pages

  • Re: Find a new automata ,its language is only Recursive Lanauge.
    ... languages and add some mechanism that allows it to handle recursive ... what can be put on the tape and when. ... grammer that you are alway progressing toward an answer. ... if you could build an automata like the one you ...
    (comp.theory)
  • Re: Restricted Turing machine
    ... Since all the languages it accepts are ... recognize some simple regular languages, ... Yes, since the tape is finite, the machine will recognize an infinite ...
    (comp.theory)
  • Re: [EGN] Re: turing completeness
    ... Chris should have spoken of a TM's requiring an unbounded ... A TM with an infinite tape recognizes exactly the same ... set of languages as does a TM with an unbounded tape. ...
    (comp.programming)
  • Re: Restricted Turing machine
    ... Since all the languages it accepts are ... recognize some simple regular languages, ... Yes, since the tape is finite, the machine will recognize an infinite ...
    (comp.theory)
  • Re: Restricted Turing machine
    ... the tape to contain only a finite number of cells, ... Since all the languages it accepts are ... recognize some simple regular languages, ... size of the tape. ...
    (comp.theory)