Re: Restricted Turing machine



Bjarke Walling wrote:
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

If you like this sort of thing, consider the modification that
stipulates that the TM may use no more cells than were necessary
to hold the input word. If, for example, the input was 10110
the TM would be restricted to 5 cells. Call the class of languages
accepted by such TMs "smallish" (so as not to give the answer away).

Where do the smallish languages fit in the hierarchy of languages
you know? Are smallish languages regular? If not, are they CFLs?
And so on--where do they fit?

Have fun. You'll find the answer interesting.


Regards,

Rick

.

Relevant Pages

  • 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
    ... 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: Cells, pycells etc
    ... other obscure technologies myself I understand the frustration of ... How does Cells compare to the properties concept in Delphi, ... In these languages you can write something like: ... instance-by-instance basis rather than a class basis. ...
    (comp.lang.lisp)
  • Re: How to get the coordinate of the lower-bound cell in Excel 2003 with C#
    ... >real data", as explicitly stipulated. ... OK, but sometimes other languages only have access to properties, not ... cells containing constants. ... No single property ...
    (microsoft.public.excel)
  • 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)