Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!bu.edu!m2c!risky.ecs.umass.edu!dime!yodaiken From: yodaiken@chelm.cs.umass.edu (victor yodaiken) Newsgroups: comp.lang.misc Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions) Message-ID: <30164@dime.cs.umass.edu> Date: 7 May 91 12:58:26 GMT References: <30040@dime.cs.umass.edu> <30082@dime.cs.umass.edu> <1991May5.135342.13792@daffy.cs.wisc.edu> Sender: news@dime.cs.umass.edu Reply-To: yodaiken@chelm.cs.umass.edu (victor yodaiken) Organization: University of Massachusetts, Amherst Lines: 29 In article <1991May5.135342.13792@daffy.cs.wisc.edu> quale@khan.cs.wisc.edu (Douglas E. Quale) writes: >In article <30082@dime.cs.umass.edu> yodaiken@chelm.cs.umass.edu (victor yodaiken) writes: >> >>Real computers correspond to finite state machines not turing machines, >>thus the halting problem is trivially (in theory of course, not in >>practice) solvable for real computers. If you provide a formal > >and later > >>turing machines. This does not mean that there is no algorithm for >>solving the halting problem for all interesting cases. Turing's > >Naturally ``interesting'' is a subjective term, but I find the busy beaver >problem interesting, and it's unsolvable. > In the context of comp.lang.misc, the busy-beaver problem, whatever its intrinsic value, seems quite uninteresting. Diagonalization arguments are simply not the bread and butter of programming language design. >I should also point out that real computers are *not* finite state machines. > Pointing it out is nice, but most computer engineers would be surprised by this claim. If we build a device from 3dimensional switching elements, there are only two alternatives --- finite state device, or infinite volume device. Of course, if we ignore the discrete nature of the switching elements and start worrying about analog behavior then things are different. But, this does not appear to be a very useful way of thinking about computation.