[time 1008] Turing Machines vs. Real-World Computers [was: Colors of Infinity and Mathematical Reality] by Bill Dubuque


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
Turing Machines vs. Real-World Computers [was: Colors of Infinity and Mathematical Reality] by Bill Dubuque

Turing Machines vs. Real-World Computers [was: Colors of Infinity and Mathematical Reality] by Bill Dubuque

reply to this message
post a message on a new topic
Back to messages on this topic
Back to sci.math
<< previous | next >>

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)


The Math Forum



This archive was generated by hypermail 2.0b3 on Wed Dec 01 1999 - 01:15:40 JST