Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!uunet!stanford.edu!msi.umn.edu!sctc.com!beede From: beede@sctc.com (Mike Beede) Newsgroups: comp.lang.misc Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions) Message-ID: <1991May4.192440.5527@sctc.com> Date: 4 May 91 19:24:40 GMT References: <333124@socrates.umd.edu> <30040@dime.cs.umass.edu> Organization: SCTC Lines: 54 yodaiken@chelm.cs.umass.edu (victor yodaiken) writes: >In article mathew@mantis.co.uk (mathew) writes: >>rockwell@socrates.umd.edu (Raul Rockwell) writes: >>> David Gudeman [] >>> [] Strong typing: the feature that an operation cannot return an >>> [] undefined result because it did not know the typing of one of its >>> [] operands. >>> >>> Strong typing also means that the function will terminate. >> >>I beg your pardon?! >> >>Last I heard, the Halting Problem was still insoluble. >> >>Is there some new theoretical result you'd like to share with us? >The halting problem does not really apply to actual programming languages >(i.e. those that are compiled or interpreted into machine code). >The sooner computer scientists begin to understand the actual meaning >of the undecidability and complexity results, the better off the filed >will be. Trivially, this is true. We can always run the program on the machine and look for a cycle in the total state (all memory, all register, all etc.) Then we wait for on the order of 2 ^ ( 2 ^ wordsize * ( memorysize + registercount ) ) cycles (corrected for any non-binarity of the machine) and if we don't get a repeat, the program never halts. The approximate length of time for my workstation (2^23 8-bit bytes, and arbitrary count of 8 registers, the number really doesn't matter), if it didn't have any disk, and assuming 2^24 operations/sec, is 2^8388584 seconds ~= 2^8388559 years, or something like 10^2,800,000 years. Net bandwidth considerations demand exponential notation for numbers of this size. Any even near-reasonable postulated speed increase will have no noticible effect on this number (it will still exceed the lifetime of the universe by an unreasonable factor). I would say that this is close enough to insoluble for government work, as the saying goes. Am I missing something in your post? I'd love for the field to be better off . . . . Mike Beede -- Mike Beede SCTC beede@sctc.com 1210 W. County Rd E, Suite 100 Arden Hills, MN 55112 (612) 482-7420