Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!elroy.jpl.nasa.gov!ncar!ico!auto-trol!davgot From: davgot@auto-trol.com (David Gottner) Newsgroups: comp.lang.misc Subject: Re: Halting Problem Solved! Film at 11! (Was Re: Message-ID: <1991May9.205401.12382@auto-trol.com> Date: 9 May 91 20:54:01 GMT References: <2953@optima.cs.arizona.edu> Sender: news@auto-trol.com Organization: Auto-trol Technology Corporation Lines: 28 Nntp-Posting-Host: davgot In article stephen@estragon.uchicago.edu (Stephen P Spackman) writes: >Let me try one more time. PRACTICAL computers are FSMs and not fully >general turing machines because PRACTICAL computers are finite. The >fact that PRACTICAL computers are finite is an important THEORETICAL >property of PRACTICAL computers and may need to be addressed before >certain ideas are dismissed. And this is true even if you include all >the input they're ever going to get as state space. PRACTICAL computers may be FSM's but programming languages are not. Nowhere in the ANSI C standard does it give a maximum amount of memory that a C program can run in. Thus your program checker must assume that the program that it is analyzing will never run out of tape, which means that the analyzer must assume that the program will run on a Turing Machine, and the undecidability theorem applies. > >...I feel a bit like you're telling me that it's impossible to code a >correct sort, because you never know when your input is going to be >an infinite stream and the function just might not terminate.... Of course some simple argorithms may be proven, like a sorting algorithm, but not >ALL< -- David Gottner davgot@auto-trol.COM Auto-trol Technology Corporation {...}ncar!ico!auto-trol!younam 12500 North Washington Street (303) 252-2321 Denver, CO 80241-2404