Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!mintaka!bloom-beacon!eru!hagbard!sunic!mcsun!ukc!strath-cs!nott-cs!piaggio!anw
From: anw@maths.nott.ac.uk (Dr A. N. Walker)
Newsgroups: comp.lang.misc
Subject: Re: The Halting Problem is _not_ solvable on real com
Message-ID: <1991May20.171033.3819@maths.nott.ac.uk>
Date: 20 May 91 17:10:33 GMT
References: <3125@cirrusl.UUCP> <3069@optima.cs.arizona.edu> <30505@dime.cs.umass.edu> <1991May15.145359.20719@daffy.cs.wisc.edu>
Reply-To: anw@maths.nott.ac.uk (Dr A. N. Walker)
Organization: Maths Dept., Nott'm Univ., UK.
Lines: 36

In article <1991May15.145359.20719@daffy.cs.wisc.edu>
quale@saavik.cs.wisc.edu (Douglas E. Quale) writes:

>3) When considering termination, an FSM has only two posssible behaviors
>   on any given input:  termination or infinite loop.

	Um.  If by "infinite loop" you mean "non-termination", yes, but
not very revealing.  Otherwise, no.  Consider, for example, an input
consisting of the digits of pi, and consider the FSM that moves into
state N on reading the digit "N".  That will not terminate, and because
pi is irrational it cannot "loop" either.  For one that *may* terminate,
consider an FSM that sits there looking for the sequence "12345678924680"
[which I just made up].  I guess that will terminate, but I'm not sure;
if it doesn't then it's quite possible that states will repeat in some
perhaps regular pattern [depending on the program], but that's not quite
what one really means by looping either.  Of course, if the input is
*generated* by an FSM, then you may be able to prove something;  but once
you link up two FSMs with each able to read the output of the other, you
get TM capability.

>* What useful programs terminate as FSMs and fail to terminate as TMs?

	The trouble is that few "useful" programs work on FSMs.  FSMs
cannot multiply arbitrary integers, cannot match brackets, etc.  In
real life they do these things quite well, purely because the real-life
integers we want to multiply and the real-life programs whose brackets
we want to match fit adequately into real-life computers.

	But do people want the theory or the practice?  You can reasonably
ask for either.  We get into difficulties when trying to mix both together,
especially when contributors assume that because a TM is not an FSM it
*must* be infinite.  It merely needs to be big enough.

-- 
Andy Walker, Maths Dept., Nott'm Univ., UK.
anw@maths.nott.ac.uk