Article View: comp.lang.misc
Article #4086Re: Halting Problem Solved! Film at 11! (Was Re:
From: Steven Ryan
Date: Mon, 03 Jun 1991 21:09
Date: Mon, 03 Jun 1991 21:09
35 lines
1438 bytes
1438 bytes
>>]>[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.
Technical Details
Message-ID:
<1991Jun3.210908.17574@clipper.ingr.com>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!samsung!uunet!stanford.edu!unix!clipper!smryanReferences:
<3354@optima.cs.arizona.edu> <1991May25.135757.6912@sbcs.sunysb.edu>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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