vol III Development:
Chapter 2: Model
page 5: Computation
The fixed points in the Universe are an observable feature of the dynamics which is traditionally considered to be a continuous or analogue process. The formal structures of mathematics and logic exist in a static, eternal 'Platonic' world which we may consider to be the fixed points of the mathematical community. These fixed points are documented in the mathematical literature. Robert G Bartle: A Brief History of the Mathematical Literature
Formally, we set mathematics in motion with computation. Much of the work of learning mathematics at school is devoted to learning addition, subtraction, multiplication, division and the many more complex computations available in mathematics. A computation, like a proof, is a deterministic process that moves from some set of initial conditions to a final condition. It may be as simple as 1+1 = 2, or it may be a very long process, like Wile's proof of 'Fermat's last theorem'. Wiles' proof of Fermat's Last Theorem - Wikipedia
Computation is an essential feature of mathematics. When we use mathematics to model the real world we imagine that the mathematical computations model the underlying dynamics which give rise to the fixed points we are trying to model. Computation establishes the logical continuity which we understand to model the 'natural continuity' which binds the communicsting elements of the Universe into a coherent system. Computable function - Wikipedia
Cantor's discoveries of set theory and the transfinite numbers led Hilbert and others to believe we had entered a mathematical paradise. 'Cantor's Paradise' is a formal world where there is (at first glance) no limit to the power and complexity of mathematical operations. Reid, 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.
Gödel found that mathematics is not complete and Turing found that
only a tiny fraction of all possible functions are computable. 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. Gödel, Turing
An important feature of Turing machines is
that they have a finite number of internal states, We know that there are
ℵ1 functions of the ℵ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 ℵ0 or less. Davis
This is a tiny fraction of the ℵ1 possible functions
of the natural numbers. In other words, the vast majority ('almost
all') of functions on the natural numbers are not computable.
What does computable really mean? We can imagine a 'machine'
comprising a set of ℵ1 lookup tables which could be set to work to generate all ℵ1 permutations of the natural numbers, but this machine would itself have ℵ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'. 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 ℵ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. Chaitin
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.
Computation is essential to error free communication. In the earlier applications of Shannon's work coding and decoding is achieved by analogue electronic circuits, as in FM radio transmission. From a practical point of view the precision and complexity of analogue processes is limited. The advent of digital signal processing has enabled the more precise application of signal processing technology so that we can transmit gigabits over noisy channels with almost 0 errors. A Mathematical Theory of Communication - Wikipedia, FM Broadcasting - Wikipedia
Here we face a chicken and egg problem, since we can understand a computer as a network, and a network as a computer, both being number of elements like memory cells and logic gates that communicate with one another in a choreographed way. Here we make a distinction between a computer and a network based on the clocks which order the moves in the choreography. In a computer, we say, all the elements are synchronous, switched on and off by signals emanating from a single clock.
Networks, on the other hand, embrace a lot of computers whose clocks are asynchronous so the network requires interfaces that can deal with this situation. In a nutshell, we deal with asynchronicity by buffering, that is by storing signals in memory so that different processors can access them in their own time.
(revised 21 August 2014)
|
Copyright:
You may copy this material freely provided only that you quote fairly and provide a link (or reference) to your source.
Further reading
Books
Click on the "Amazon" link below each book entry to see details of a book (and possibly buy it!)
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 techniques 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 Gödel, 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 |
Gödel, Kurt, and Solomon Feferman et al (eds), Kurt Gödel: 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. 'The present formulation should prove significant in the development of
symbolic logic along the lines of Godel's theorem on the incompleteness of symbolic
logics1 and Church's results concerning absolutely unsolvable problems.'
We have in mind a general problem consisting of a class of specific problems.
A solution of the general problem will then be one which furnishes an answer to
each specific problem.
In the following formulation of such a solution two concepts are involved:
that of a symbol space in which the work leading from problem to answer is to
be carried out,' and a fixed unalterable set of directions which will both direct
operations in the symbol space and determine the order in which those directions
are to be applied.'. 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
| A Mathematical Theory of Communication - Wikipedia, A Mathematical Theory of Communication - Wikipedia, the free encyclopedia, 'The article entitled "A Mathematical Theory of Communication", published in 1948 by mathematician Claude E. Shannon, was one of the founding works of the field of information theory. Shannon's paper laid out the basic elements of any digital communication:
• An information source which produces a message
• A transmitter which operates on the message to create a signal which can be sent through a channel
• A channel, which is the medium over which the signal, carrying the information that composes the message, is sent
• A receiver, which transforms the signal back into the message intended for delivery
• A destination, which can be a person or a machine, for whom or which the message is intended
It also developed the concepts of information entropy and redundancy.' back |
| 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 |
| David Hilbert - Wikipedia, David Hilbert - Wikipedia, the free encyclopedia, 'David Hilbert (January 23, 1862 – February 14, 1943) was a German mathematician, recognized as one of the most influential and universal mathematicians of the 19th and early 20th centuries. He invented or developed a broad range of fundamental ideas, in invariant theory, the axiomatization of geometry, and with the notion of Hilbert space, one of the foundations of functional analysis.
Hilbert adopted and warmly defended Georg Cantor's set theory and transfinite numbers. A famous example of his leadership in mathematics is his 1900 presentation of a collection of problems that set the course for much of the mathematical research of the 20th century.
Hilbert and his students supplied significant portions of the mathematical infrastructure required for quantum mechanics and general relativity. He is also known as one of the founders of proof theory, mathematical logic and the distinction between mathematics and metamathematics.' back |
| FM Broadcasting - Wikipedia, FM Broadcasting - Wikipedia, the free encyclopdia, 'FM broadcasting is a VHF broadcasting technology that was pioneered by Edwin Howard Armstrong which uses frequency modulation (FM) to provide high-fidelity sound over broadcast radio. The term "FM band" describes the frequency band in a given country which is dedicated to FM broadcasting. This term is slightly misleading, since it equates a modulation method with a range of frequencies. back |
| Frequency modulation - Wikipedia, Frequency modulation - Wikipedia, the free encyclopedia, back |
| Georg Cantor - Wikipedia, Georg Cantor - Wikipedia, the free encyclopedia, Georg Ferdinand Ludwig Philipp Cantor (March 3 [O.S. February 19] 1845[1] – January 6, 1918) was a German mathematician, born in Russia. He is best known as the creator of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence between sets, defined infinite and well-ordered sets, and proved that the real numbers are "more numerous" than the natural numbers. In fact, Cantor's theorem implies the existence of an "infinity of infinities". He defined the cardinal and ordinal numbers and their arithmetic. Cantor's work is of great philosophical interest, a fact of which he was well aware' back |
| Robert G Bartle, A Brief History of the Mathematical Literature, 'Summary: The purpose of this article is to review the development of the mathematical literature by briefly tracing the history of mathematical communication leading to the founding of Mathematical Reviews in 1940. We touch on the formation of the academies and the mathematical societies, and mention some of the early journals published by these groups. Finally, we discuss the emergence of the mathematical reviewing journals. We do not discuss the growth of privately circulated unpublished literature, conference proceedings or the recent development of electronic forms of communication in mathematics.' back |
| Wiles' proof of Fermat's Last Theorem - Wikipedia, Wiles' proof of Fermat's Last Theorem - Wikipedia, the free encyclopedia, 'Andrew Wiles' proof of Fermat's Last Theorem is a proof of the modularity theorem for semistable elliptic curves released by Andrew Wiles, which, together with Ribet's theorem, provides a proof for Fermat's Last Theorem. Both Fermat's Last Theorem and the Modularity Theorem were almost universally considered inaccessible to proof by contemporaneous mathematicians, seen as virtually impossible to prove using current knowledge.' back |
|
