🚀 go-pugleaf

In article <1991Jun3.210908.17574@clipper.ingr.com> smryan@clipper.ingr.com (Steven Ryan) writes:
>>>]>[A finite TM is translatable into a FSM.
>
>Consider an input tape with a left end marker '<' and right end marker '>'.
>Between the markers are the symbols '(' and ')'.
>
> ...
>
>This has a fixed number of rules. For any input string of length n, it uses
>finite space O(n) and finite time O(n).
>
>This is finite and TM-equivalent. Please translate into a FSM for any legal
>input string.
>-- 
>In compliance with DoC,            Steven Ryan
>this posting is devoid             2400 Geng Road, Palo Alto, CA
>of all information.                ...!{apple|pyramid}!clipper!wyrmham!smryan
>fxxx!                              A new xxxx for xxxxxxx  xxxxxxxxxx.

Quite true. A TM in which the size of the tape is limited to the size of the
input is a Linear Bounded Automaton(LBA). A LBA accepts Context Sensitive Languages (CSL).
The set of CSLs is a strict superset of the set of Context Free Languages.

The difference between a FSM and a TM with a finite tape is that the FSM has a fixed
finite amount of "memory" while the amount of "memory" available to the TM with a finite
tape must necessarily grow as the length of the input grows (i.e. the tape must be at
least large enough to hold the input string).

The only way (that I am aware of) to restict the power of a TM to that of a FSM is to
not allow the TM to write to the tape.