Stephen Paul King (stephenk1@home.com)
Sat, 20 Nov 1999 09:47:27 -0500
y8zlo3gmqt0.fsf_-_@berne.ai.mit.edu">http://forum.swarthmore.edu/epigone/sci.math/brendsnyzhou/y8zlo3gmqt0.fsf_-_@berne.ai.mit.edu
Subject: Turing Machines vs. Real-World Computers [was: Colors of Infinity and Mathematical Reality] Author: Bill Dubuque <wgd@berne.ai.mit.edu> Organization: MIT Date: 09 Jul 1997 07:02:35 -0400 gwsmith@river.gwi.net (Gene W. Smith) wrote to sci.math on 6 Jul 1997: | | ... You can't make a computer which can add arbitrary integers. | A Turing machine may have an infinite tape and an infinite amount | of time, but it isn't physically realizable. ... A Finite State Machine can add arbitrary integers, but cannot multiply arbitrary integers (not even square them, e.g. see Exercise 2-14 of H. Rogers, Theory of Recursive Functions and Effective Computability). All current physically realizable computers are Finite State Machines and hence are subject to the above limitation. The Turing Machine was devised by Turing not as a model of any type of physically realizable computer but rather as an ideal limit to what is computable by a HUMAN calculating in a step-by-step mechanical manner (without any use of intuition). This point is widely misunderstood -- see [1] for an excellent exposition on this and related topics. The finiteness limitations postulated by Turing for his Turing Machines are based on postulated limitations of the human sensory apparatus. A Turing style analysis of physically realizable computing devices and analogous Church-Turing theses did not come until much later (1980) due to Robin Gandy -- with limitations based on the laws of physics. As Odifreddi says on p. 51 of [2] (bible of Classical Recursion Theory) Turing machines are theoretical devices, but have been designed with an eye to physical limitations. In particular, we have incorporated in our model restrictions coming from: (a) ATOMISM, by ensuring that the amount of information that can be coded in any configuration of the machine (as a finite system) is bounded; and (b) REALTIVITY, by excluding actions at a distance, and making causal effect propagate through local interactions. Gandy [1980] has shown that the notion of Turing machine is sufficiently general to subsume, in a precise sense, any computing device satisfying similar limitations. and on p. 107: (A general theory of discrete, deterministic devices) The analysis (Church [1957], Kolmogorov and Uspenskii [1958], Gandy [1980]) starts from the assumptions of atomism and relativity. The former reduces the structure of matter to a finite set of basic particles of bounded dimensions, and thus justifies the theoretical possibility of dismantling a machine down to a set of basic constituents. The latter imposes an upper bound (the speed of light) on the propagation speed of causal changes, and thus justifies the theoretical possibility of reducing the causal effect produced in an instant t on a bounded region of space V, to actions produced by the regions whose points are within distance c*t from some point V. Of course, the assumptions do not take into account systems which are continuous, or which allow unbounded action-at-a- distance (like Newtonian gravitational systems). Gandy's analysis shows that the THE BEHAVIOR IS RECURSIVE, FOR ANY DEVICE WITH A FIXED BOUND ON THE COMPLEXITY OF ITS POSSIBLE CONFIGURATIONS (in the sense that both the levels of conceptual build-up from constituents, and the number of constituents in any structured part of any configuration, are bounded), AND FIXED FINITE, DETERMINISTIC SETS OF INSTRUCTIONS FOR LOCAL AND GLOBAL ACTION (the former telling how to determine the effect of an action on structured parts, the latter how to assemble the local effects). Moreover, the analysis is optimal in the sense that, when made precise, any relaxing of conditions becomes compatible with any behavior, and it thus provides a sufficient and necessary description of recursive behavior. Be forewarned that Gandy's 1980 paper [3] is regarded as difficult even by some cognoscenti. You may find it helpful to first peruse the papers in [4] by J. Shepherdson, and A. Makowsky. -Bill Dubuque [1] Sieg, Wilfried. Mechanical procedures and mathematical experience. pp. 71--117 in Mathematics and mind. Papers from the Conference on the Philosophy of Mathematics held at Amherst College, Amherst, Massachusetts, April 5-7, 1991. Edited by Alexander George. Logic Comput. Philos., Oxford Univ. Press, New York, 1994. ISBN: 0-19-507929-9 MR 96m:00006 (Reviewer: Stewart Shapiro) 00A30 (01A60 03A05 03D20) [2] Odifreddi, Piergiorgio. Classical recursion theory. The theory of functions and sets of natural numbers. With a foreword by G. E. Sacks. Studies in Logic and the Foundations of Mathematics, 125. North-Holland Publishing Co., Amsterdam-New York, 1989. xviii+668 pp. ISBN: 0-444-87295-7 MR 90d:03072 (Reviewer: Rodney G. Downey) 03Dxx (03-02 03E15 03E45 03F30 68Q05) [3] Gandy, Robin. Church's thesis and principles for mechanisms. The Kleene Symposium. Proceedings of the Symposium held at the University of Wisconsin, Madison, Wis., June 18--24, 1978. Edited by Jon Barwise, H. Jerome Keisler and Kenneth Kunen. Studies in Logic and the Foundations of Mathematics, 101. North-Holland Publishing Co., Amsterdam-New York, 1980. xx+425 pp. ISBN: 0-444-85345-6 MR 82h:03036 (Reviewer: Douglas Cenzer) 03D10 (03A05) [4] The universal Turing machine: a half-century survey. Second edition. Edited by Rolf Herken. Computerkultur [Computer Culture], II. Springer-Verlag, Vienna, 1995. xvi+611 pp. ISBN: 3-211-82637-8 MR 96j:03005 03-06 (01A60 03D10 03D15 68-06)
This archive was generated by hypermail 2.0b3 on Wed Dec 01 1999 - 01:15:40 JST