Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!swrinde!elroy.jpl.nasa.gov!decwrl!netcomsv!doug From: doug@netcom.COM (Doug Merritt) Newsgroups: comp.lang.misc Subject: Re: Will this *thread* ever halt? Message-ID: <1991May28.204434.16396@netcom.COM> Date: 28 May 91 20:44:34 GMT References: <31051@dime.cs.umass.edu> Organization: Netcom - Online Communication Services UNIX System {408 241-9760 guest} Lines: 32 In article mathew@mantis.co.uk (CNEWS MUST DIE!) writes: >In short, determining the halting status of ANSI C programs is not feasible >for real programs; and it's not possible for general ANSI C programs, because >general ANSI C programs might have arbitrarily large input spaces making >analysis require impossible amounts of memory and CPU time. I don't see why all that stuff is even being discussed; like I pointed out the other day, even determining halting for self-contained C programs (no malloc, no clock dependency, etc) is impossible, so why bring in the other junk? >If you want to write programs and be told whether they will halt or not, you >will have to use a different language; one which is restricted so that you >don't have to rely on brute-force methods for determining halting status. For >example, a functional language which uses map operations (iteration over a >structure) rather than while loops and which limits general recursion. If you are aware of work that shows that the halting problem is soluble for functional languages, I would dearly love to see the reference. Or even that it *might* be soluble. (In other words, I don't believe it for a minute; functional languages are universal computational models and as such can be mapped one-to-one with Turing machines and the lambda calculus etc.) Also, you and your conversational opponent are starting to sound like you're in violent agreement. No doubt that's just because I've lost track of your actual base positions. Doug -- Doug Merritt doug@netcom.com (apple!netcom!doug) -OR- sun.com!jfrank!doug -OR- doug@eris.berkeley.edu Professional Wild-eyed Visionary Member, Crusaders for a Better Tomorrow