Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!wuarchive!emory!att!linac!midway!midway!stephen From: stephen@estragon.uchicago.edu (Stephen P Spackman) Newsgroups: comp.lang.misc Subject: Re: Halting Problem Solved! Film at 11! (Was Re: Message-ID: Date: 10 May 91 07:13:11 GMT References: <3007@optima.cs.arizona.edu> Sender: news@midway.uchicago.edu (NewsMistress) Organization: University of Chicago CILS Lines: 105 In-Reply-To: gudeman@cs.arizona.edu's message of 9 May 91 19: 15:58 GMT In article <3007@optima.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes: |In article Stephen P Spackman writes: |] |]... 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... | |I'm assuming that by "practical computers are finite" you mean that |computers are finite for practical purposes -- if you meant something |else, please correct me. No. I mean that practical computers are ACTUALLY finite: for both practical AND theoretical purposes. I don't know any simpler way of phrasing this. Practical computers are finite. They ARE. Really. In actuality, real, actual, practical computers are actually really finite in every way. They are limited, bounded and finite. Really. | OK, suppose that there are important |theoretical results based on the assumption that computers are finite. |That does not preclude the possibility that there are important |theoretical results based on the assumption that computers are not |finite. Of course not. But any important theoretical result that DEPENDS on a computer being infinite will have NO DIRECT APPLICATION to computers, since actual computers are not, EVER, infinite. | And it is certainly the case that there are many applications |where computers are not finite -- for practical purposes. This is absurd. Of course there are applications in which a finite practical machine of certain capacity and an infinite theoretical machine would exhibit the same behaviour. But does this make the finite machine less finite? No way, no how. Practical computers are, for all purposes, always finite. That's just the way it is. Any infinite computer is a mere approximation of a real computer and you use techniques and results derived for infinite computers at your own peril. |I have not claimed that computers are unbounded-state machines, I've |only said that it isn't the case that computers are obviously FSMs as |some on this group seem to think. I don't understand what you're saying here. Are you telling me that you actually KNOW that computers are FSMs but that you consider this fact sufficiently non-obvious that you feel justified in persisting in the pretence that they are infinite, despite the facts? Or are you merely defending OTHER people's rights to err without fear of correction? In any event, the finitude of computers is obvious to about the same extent as it is obvious that the population of ducks in Tahiti is finite, I'd say. I mean, computers are finite, have discrete states, and are machines. Therefore they're REALLY QUITE LIKELY (ahem) to be FSMs. | Both models of computers have their |uses. You bet. No question. | It is not the case that all results based on the assumption |that computers are USMs are impractical, because as long as your |problems do not hit the boundaries, the boundaries may as well not |exits. EXACTLY!!!! THANKYOU!!!! THIS IS THE POINT!!!! And any theorem that depends on the fact that the machine will *NOT* hit a boundary does not in fact apply to a real computer - and this is true any theorem that requires that encodings exist for arbitrary objects, for example. Remember: computers FINITE and (like humans) CANNOT DO ARITHMETIC. | Most algorithm analyses and programming language semantics |assume that the machines are USM's and the results from such |assumptions are valid for most practical purposes. Oh, yes. Correct me if I'm wrong, but it seems to me that they are not adequate to THEORETICAL purposes like the standard incompleteness/inconsistency proofs. You're confusing building up with building down: these theorems, at least as I've seen them, apply to "computers" that are AT LEAST infinite, not to ones that are AT MOST infinite. They may be useful approximations, but they aren't precise results. |]....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.... | |I don't understand what you mean by that. If your input is another |process of unknown origin, then there _are_ certain correctness |criteria that you cannot satisfy with your own sort. Are you |suggesting that you wouldn't want to be told that? No; I'm suggesting that it's important to attribute cause accurately. There's nothing INCORRECT about my sort, just because it can be handed unbounded input. And there's nothing INFINITE about my computer just because it can be approximated in some respects by an infinite machine. ---------------------------------------------------------------------- stephen p spackman Center for Information and Language Studies systems analyst University of Chicago ----------------------------------------------------------------------