Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!udel!haven.umd.edu!socrates.umd.edu!socrates!rockwell From: rockwell@socrates.umd.edu (Raul Rockwell) Newsgroups: comp.lang.misc Subject: Re: The Halting Problem is _not_ solvable on real com Message-ID: Date: 21 May 91 13:09:33 GMT References: <3125@cirrusl.UUCP> <3069@optima.cs.arizona.edu> <30505@dime.cs.umass.edu> <1991May15.145359.20719@daffy.cs.wisc.edu> <1991May20.171033.3819@maths.nott.ac.uk> Sender: rockwell@socrates.umd.edu (Raul Rockwell) Organization: Traveller Lines: 49 In-Reply-To: anw@maths.nott.ac.uk's message of 20 May 91 17: 10:33 GMT Andy Walker: 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. It's not a finite state machine either, because it has too many states. ... but once you link up two FSMs with each able to read the output of the other, you get TM capability. No, a turing machine has the ability to "create" a new FSM on the fly (in state 0). In fact, it has the ability to create an infinite number of FSMs (given infinite time). The trouble is that few "useful" programs work on FSMs. FSMs cannot multiply arbitrary integers, cannot match brackets, etc. No, but they can multiply bounded integers, and they can match brackets in bounded strings. By placing the bounds conveniently high they can be considered transparent for most applications. 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. Exactly. In real life, the integers (and string lengths) are not arbitrary. By the way, a classic example of the problems involved in a solution which takes infinite time is the following "algorithm" for a turing machine: Find the first non-zero cell on a tape by scanning left till you hit a non-zero cell. If this does not terminate, scan right till you hit a non-zero cell. The tape provided is arbitrary. But the turing machine doesn't have a method for determining if a given algorithm will terminate. You could set up the TM to scan both directions, and halt when it finds the first non-zero cell that's close to the starting point, but you can't even use that result to run the above algorithm (because you still wouldn't know if the tape on the left had a non-zero cell). *lecture off* Raul Rockwell