vol 3: Development
2 Model
page 4: Computation
Site map
Directory
Search this site
Home
1: About
2: Synopsis
3: Development
Next: page 5: A transfinite computer network
Previous: page 3: Logical continuity
This site is part of the natural religion project The natural religion project A new theology A commentary on the Summa The theology company
Computation
The formal structures of mathematics and logic exist in a static, eternal 'Platonic' world. Formally, we set mathematics in motion with computation. Most of the work of learning mathematics is devoted to addition, subtraction and the many more complex computations available in mathematics.
Computation is an essential feature of mathematics. We might say that the limits to computation are the limits to mathematics. Computable function - Wikipedia Computation establishes the logical continuity which binds communication networks into a system. Logical continuity
Cantor's discoveries led Hilbert and others to believe they had entered paradise, Reid Cantor's Paradise is a formal world where there is (at first glance) no limit to the power and complexity of mathematical operations. Mendelson
Hilbert believed that formal axiomatic methods would eventually show that consistent mathematics was both complete and computable. By complete, he meant that a proof or disproof could be found for every well formed mathematical statement. By computable, he meant that the proof (or disproof) of any formal statement could be achieved by a machine with a finite program. Hodges,
This is not so. Goedel found that mathematics is not complete and Turing found that only a tiny fraction of all possible functions are computable. Goedel, Turing Turing devised a machine (now known as a Turing machine) that was capable of performing any sequence of steps that could reasonably be called a computation, and showed that there are functions that this machine can not compute.
An important feature of Turing machines is that they have a finite number of internal states, Davis We know that there are aleph(1) functions of the aleph(0) natural numbers onto themselves. Since a Turing machine may have only a finite number of internal states, the total number of different Turing machines (and hence of the different functions computable by such a machine) must be aleph(0) or less.
This is a tiny fraction of the aleph(1) possible functions of the natural numbers. In other words, the vast majority ('almost all' ) of functions on the natural numbers are not computable. We can imagine that an even smaller fraction of continuous functions are computable and so on up the transfinite scale.
What does computable really mean? We can imagine a 'machine' comprising a set of aleph(1) lookup tables which could be set to work to generate all aleph(1) permutations of the natural numbers, but this machine would itself have aleph(1) internal states and so be infinitely bigger than a Turing machine. The essence of Turing computation is that its state space is finite. In other words, computable functions are those that can be 'compressed' from infinite to finite size by careful programming.
This is the idea behind Chaitin's 'algorithmic information theory'. Chaitin When a physicist writes F = ma the three variables F (force) m (mass) and a (acceleration) are considered to be continuous, ie to have values corresponding to any of the aleph(1) points in the natural line. From this point of view, we might say that F = ma contains an infinite amount of information. From an algorithmic point of view, however, all the information in 'F = ma' is encoded in the the equation itself and whatever additional code may be necessary for a computer to evaluate it. In any case the information content of the equation is quite small.
The source of computational compressibility is symmetry. In the case of F = ma it is the arithmetical symmetry contained in the operation of multiplication which applies indifferently to all real multiplicands. The symmetric universe, as we have constructed it, is full of symmetries, since it is a hierarchy of permutation (or symmetric) groups. Group theory tells us that the abstract permutation group of any cardinal number contains all groups (and therefore all symmetries) of that cardinal. Thus we find 'islands of computability' in the abstract Cantor universe.
Since computable functions are a limited resource, we can expect a sort of 'natural selection' among possible processes which gives preference to those represented by computable functions. We see a similar process in science, where the way forward in a particular field often depends on the discovery of a computable mathematical model to represent the phenomena under consideration.
Further reading
Books
| Chaitin, Gregory J, Information, Randomness & Incompleteness: Papers on Algorithmic Information Theory, World Scientific 1987 Jacket: 'Algorithmic information theory is a branch of computational complexity theory concerned with the size of computer programs rather than with their running time. ... The theory combines features of probability theory, information theory, statistical mechanics and thermodynamics, and recursive function or computability theory. ... [A] major application of algorithmic information theory has been the dramatic new light it throws on Goedel's famous incompleteness theorem and on the limitations of the axiomatic method. ...' Amazon back |
| Chaitin, Gregory J, Algorithmic Information Theory, Cambridge UP 1987 Foreword: 'The crucial fact here is that there exist symbolic objects (i.e., texts) which are "algorithmically inexplicable", i.e., cannot be specified by any text shorter than themselves. Since texts of this sort have the properties associated with random sequences of classical probability theory, the theory of describability developed ... in the present work yields a very interesting new view of the notion of randomness.' J T Schwartz Amazon back |
| Cummins, Denise Dellarosa, and Colin Allen (editors), The Evolution of Mind, Oxford University Press 1998 Introduction: This book is an interdisciplinary endeavour, a collection of essays by ethologists, psychologists, anthropologists and philosophers united in the common goal of explaining cognition. ... the chief challenge is to make evolutionary psychology into an experimental science. Several of the chapters in this volume describe experimental techniues and results consistent with this aim; our hope and intention is that they lead by example in the development of evolutionary psychology from the realm of speculation to that of established research program' Amazon back |
| Davis, Martin, Computability and Unsolvability, Dover 1982 Preface: 'This book is an introduction to the theory of computability and non-computability ususally referred to as the theory of recursive functions. The subject is concerned with the existence of purely mechanical procedures for solving problems. ... The existence of absolutely unsolvable problems and the Goedel incompleteness theorem are among the results in the theory of computability that have philosophical significance.' Amazon back |
| Davis, Martin, The Undecidable : Basic Papers on Problems Propositions Unsolvable Problems and Computable Functions, Raven Press 1965 Description: '[Includes] ... the basic papers of Goedel, Church, Turing, and Post in which the class of recursive functions was singled out and seen to be just the class of functions that can be computed by terminating processes. Also presented is the work of Church, Turing, and Post in which problems from the theory of abstract computing machines, from mathematical logic, and finally from algebra are shown to be unsolvable in the sense that there is no terminating process for dealing with them. Finally, the book presents the work of Kleene and of Post initiating the classification theory of unsolvable problems. Already the standard reference work on the subject, The Undecidable is also ideally suited as a text or supplementary text for courses in logic, philosophy, and foundations of mathematics. Amazon back |
| Goedel, Kurt, and Solomon Feferman et al (eds), Kurt Goedel: Collected Works Volume 1 Publications 1929-1936, Oxford UP 1986 Jacket: 'Kurt Goedel was the most outstanding logician of the twentieth century, famous for his work on the completeness of logic, the incompleteness of number theory and the consistency of the axiom of choice and the continuum hypotheses. ... The first volume of a comprehensive edition of Goedel's works, this book makes available for the first time in a single source all his publications from 1929 to 1936, including his dissertation. ...' Amazon back |
| Hodges, Andrew, Alan Turing: The Enigma, Burnett 1983 Author's note: '... modern papers often employ the usage turing machine. Sinking without a capital letter into the collective mathematical consciousness (as with the abelian group, or the riemannian manifold) is probably the best that science can offer in the way of canonisation.' (530) Amazon back |
| Lo, Hoi-Kwong, and Tim Spiller, Sandra Popescu, Introduction to Quantum Computation and Information, World Scientific 1998 Jacket: 'This book provides a pedagogical introduction to the subjects of quantum information and computation. Topics include non-locality of quantum mechanics, quantum computation, quantum cryptography, quantum error correction, fault tolerant quantum computation, as well as some experimental aspects of quantum computation and quantum cryptography. A knowledge of basic quantum mechanics is assumed.' Amazon back |
| Mendelson, Elliott, Introduction to Mathematical Logic, van Nostrand 1987 Preface: '... a compact introduction to some of the principal topics of mathematical logic. ... In the belief that beginners should be exposed to the most natural and easiest proofs, free swinging set-theoretical methods have been used." Amazon back |
| Nielsen, Michael A, and Isaac L Chuang, Quantum Computation and Quantum Information, Cambridge University Press 2000 Review: A rigorous, comprehensive text on quantum information is timely. The study of quantum information and computation represents a particularly direct route to understanding quantum mechanics. Unlike the traditional route to quantum mechanics via Schroedinger's equation and the hydrogen atom, the study of quantum information requires no calculus, merely a knowledge of complex numbers and matrix multiplication. In addition, quantum information processing gives direct access to the traditionally advanced topics of measurement of quantum systems and decoherence.' Seth Lloyd, Department of Quantum Mechanical Engineering, MIT, Nature 6876: vol 416 page 19, 7 March 2002. Amazon back |
| Reid, Constance, Hilbert-Courant, Springer Verlag 1986 Jacket: '[Hilbert] is woven out of three distinct themes. It presents a sensitive portrait of a great human being. It describes accurately and intelligibly on a non-technical level the world of mathematical ideas in which Hilbert created his masterpieces. And it illuminates the background of German social history against which the drama of Hilbert's life was played. ... Beyond this, it is a poem in praise of mathematics.' Science Amazon back |
Papers
| Church, Alonzo, "An unsolvable problem of elementary number theory", American Journal of Mathematics, 58, , 1936, page 345-363. Presents Church's Theorem , which shows there is no decision procedure for arithmetic. His work extended that of Gödel.. back |
| Post, E L, "Finite combinatory processes - formulation 1.", The Journal of Symbolic Logic, 1, 42, 1936, page 103-105. back |
| Turing, Alan, "On Computable Numbers, with an application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, 2, 42, 12 November 1937, page 230-265. 'The "computable" numbers maybe described briefly as the real numbers whose expressions as a decimal are calculable by finite means. Although the subject of this paper is ostensibly the computable numbers, it is almost as easy to define and investigate computable functions of an integrable variable or a real or computable variable, computable predicates and so forth. The fundamental problems involved are, however, the same in each case, and I have chosen the computable numbers for explicit treatment as involving the least cumbrous technique. I hope shortly to give an account of the rewlations of the computable numbers, functions and so forth to one another. This will include a development of the theory of functions of a real variable expressed in terms of computable numbers. According to my definition, a number is computable if its decimal can be written down by a machine'. back |
Links
| Alan Turing On Computable Numbers, with an application to the Entscheidungsproblem 'The "computable" numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means. Although the subject of this paper is ostensibly the computable numbers, it is almost equally easy to define and investigate computable functions of an integral variable or a real or computable variable, computable predicates, and so forth. The fundamental problems involved are, however, the same in each case, and I have chosen the computable numbers for explicit treatment as involving the least cumbrous technique.' back |
| Computable function - Wikipedia Computable function - Wikipedia, the free encyclopedia 'Computable functions (or Turing-computable functions) are the basic objects of study in computability theory. They make precise the intuitive notion of algorithm. Computable functions can be used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines. Their definition, however, must make reference to some specific model of computation.' back |
| Math Archives Mathematics Archives WWW Server 'The goal of the Mathematics Archives is to provide organized Internet access to a wide variety of mathematical resources. The primary emphasis is on materials which are used in the teaching of mathematics. Currently the Archives is particularly strong in its collection of educational software.' back |
Click on an "Amazon" link in the booklist at the foot of the page to buy the book, see more details or search for similar items
Related sites:
Concordat Watch
Revealing Vatican attempts to propagate its religion by international treaty
Copyright: You may copy this material freely provided only that you quote fairly and provide a link (or reference) to your source.
