Re: Restricted Turing machine

tuncay tekle skrev:
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.

Plain and simple. Thank you for the answer.

- Bjarke Walling

.

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: [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)