Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!wuarchive!rex!caesar!fs From: fs@caesar.cs.tulane.edu (Frank Silbermann) Newsgroups: comp.theory Subject: Re: Question on halting problem Message-ID: <7260@rex.cs.tulane.edu> Date: 1 May 91 16:33:53 GMT References: <1991Apr26.135918.8607@m.cs.uiuc.edu> <3132@ylum.Morgan.COM> Sender: news@rex.cs.tulane.edu Organization: Computer Science Dept., Tulane Univ., New Orleans, LA Lines: 38 >>> We are unable to build Turing machines; >>> nobody has ever constructed a computer that was >>> more than a DFA, and nobody ever will >>> (since all computers have a fixed amount of memory). >> If I endow a foundation to add 1 tape square every year, >> then the memory is eventually large enough, and a Turing Machine >> results. > There is an upper limit on the amount of memory a computer can have, > since the universe is finite. All of you miss the point. The Turing machine _model_ is a technique to abstract out the size of the memory from the machine description. A Turing machine may be thought of as a finite automaton SCHEMA. Each time you bound a TM's tape length, the result is a new FA. By instantiating the TM to FA's with increasing tape length, you generate a series of increasingly powerful finite automata. In terms of denotational semantics, for any such FA schema (i.e. TM), the shorter-tape FA's approximate the larger-tape FA's. The least upper bound (limit) of this chain of finite automata is the conceptual (not physical) Turing machine. Turing decidability means that there exists a finite automaton _schema_ for which some sufficiently large instantiation decides the problem. (this is related to Denotational Semantics's idea of continuity). Turing undecidablity means that we _cannot_ solve the problem by building successively larger finite automata generated from such a schema. This high-level insight is often valuable. Frank Silbermann fs@cs.tulane.edu Tulane University New Orleans, Louisiana USA