Re: Restricted Turing machine

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)? Since all the languages it accepts are
finite it may also be able to recognize them, ultimately by using
enough states to regognize all possible strings. But it may not
recognize some simple regular languages, as they can be infinite. The
question is if all the languages it recognizes are regular languages?

Yes, since the tape is finite, the machine will recognize an infinite
number of FINITE languages (where the language can be at most of
cardinality x^n, where x is the number of input symbols and n is the
size of the tape. Any finite language is regular, hence the answer is
yes.

.

Relevant Pages

  • Re: Restricted Turing machine
    ... If you restrict the tape to be read-only, so it only ever holds the ... input, you have regular languages. ... languages of matching parentheses. ...
    (comp.theory)
  • 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 ... > tape, which some languages do not provide, and about which we had a ...
    (comp.programming)
  • 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)