Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!samsung!uunet!stanford.edu!unix!clipper!smryan
From: smryan@clipper.ingr.com (Steven Ryan)
Newsgroups: comp.lang.misc
Subject: Re: Halting Problem Solved! Film at 11! (Was Re:
Message-ID: <1991Jun3.210908.17574@clipper.ingr.com>
Date: 3 Jun 91 21:09:08 GMT
References: <3354@optima.cs.arizona.edu> <1991May25.135757.6912@sbcs.sunysb.edu>
Distribution: usa
Organization: Intergraph Advanced Processor Division - Palo Alto, CA
Lines: 35

>>]>[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 ')'.

The following Markov machine terminates with 'Y' if the '()' are semi-Dyck,
'N' if not.

	<	->	[p
	p(	->	(p
	(p)	->	p
	[p>	->	Y

	[p)	->	q
	q(	->	q
	q)	->	q
	q>	->	N

	(r>	->	r
	(r	->	r
	)r	->	r
	[r	->	N

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).

>>]>[A finite TM is translatable into a FSM.

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.