Restricted Turing machine

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)? 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?
There might exist some finite recursive languages, which are neither a
contextfree grammer or a regular language, which it is able to
recognize. If the head was only allowed to move to the right all the
time, then it certainly would be a 'yes' since it would be exactly like
a finite automata, but the head is allowed to move in both directions.
But then again it seems plausible that all finite languages can be
described in terms of a regular expression and are in fact a regular
language.

I hope you'll help me on this one.

Thanks,
Bjarke Walling

.

Relevant Pages

  • Re: Application of formal languages
    ... automata and formal languages. ... regular languages and context-free grammars in computer science, ... they won't think that automata theory is purely theoretical crap:). ... expression to NFSA to FSA for efficient searching for patterns. ...
    (comp.theory)
  • Re: Extended context-free grammar
    ... S::= x \ T produces a word w iff T produces x.w ... David may want to know that the class of regular languages is closed ... that the class of context-free languages is also closed under exponentials. ...
    (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)
  • 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: Languages of Africa
    ... > Taxonomy and Genetic Relationships Between Indo-Pacific Languages ... > Halmaheran, South Bird’s Head, West Bomberai, Nimboran and Upper Tami ... > Guinean families for which there is sufficient data. ...
    (sci.lang)