Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!dali.cs.montana.edu!uakari.primate.wisc.edu!sdd.hp.com!hplabs!nsc!voder!berlioz.nsc.com!dcooper
From: dcooper@berlioz.nsc.com (D. Cooper)
Newsgroups: comp.lang.misc
Subject: Re: Halting Problem Solved! Film at 11! (Was Re:
Message-ID: <1991Jun4.165835.29519@berlioz.nsc.com>
Date: 4 Jun 91 16:58:35 GMT
References: <3354@optima.cs.arizona.edu> <1991May25.135757.6912@sbcs.sunysb.edu> <1991Jun3.210908.17574@clipper.ingr.com>
Sender: news@berlioz.nsc.com
Distribution: usa
Organization: National Semiconductor Corporation
Lines: 30

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.