Educational Technology Leadership*05-06 > Hot Topic!!! Turing Machines |
|
|
Rotisserie Question
elindblom Below are three articles on the Turing Machine. Once read, an understanding shall develop. Please feel free to make comments on the material!!! Eric J. Lindblom, Ph.D. http://plato.stanford.edu/entries/turing-machine/
"Turing Machines
Turing, writing before the invention of the modern digital computer, was interested in the question of what it means to be computable. Intuitively a task is computable if one can specify a sequence of instructions which when followed will result in the completion of the task. Such a set of instructions is called an effective procedure, or algorithm, for the task. This intuition must be made precise by defining the capabilities of the device that is to carry out the instructions. Devices with different capabilities may be able to complete different instruction sets, and therefore may result in different classes of computable tasks (see the entry on computability and complexity). Turing proposed a class of devices that came to be known as Turing machines. These devices lead to a formal notion of computation that we will call Turing-computability. The proposition that Turing's notion captures exactly the intuitive idea of effective procedure is called the Church-Turing thesis. This proposition, being a claim about the relationship between a formal concept and intuition, is not provable, though it would be refuted by an intuitively acceptable algorithm for a task that is not Turing-computable. That no such counterexample has been found, together with the fact that Turing-computability is equivalent to independently defined notions of computability based on alternative foundations, such as recursive functions and abacus machines, indicates that there is at least something natural about this notion of computability. Turing machines are not physical objects but mathematical ones. We require neither soldering irons nor silicon chips to build one. The architecture is simply described, and the actions that may be carried out by the machine are simple and unambiguously specified. Turing recognized that it is not necessary to talk about how the machine carries out its actions, but merely to take as given the twin ideas that the machine can carry out the specified actions, and that those actions may be uniquely described. 1. A Definition of Turing Machine
-------------------------------------------------------------------------------- 1. A Definition of Turing Machines
A Turing machine has an infinite one-dimensional tape divided into cells. Traditionally we think of the tape as being horizontal with the cells arranged in a left-right orientation. The tape has one end, at the left say, and stretches infinitely far to the right. Each cell is able to contain one symbol, either ‘0’ or ‘1’. The machine has a read-write head, which at any time scanning a single cell on the tape. This read-write head can move left and right along the tape to scan successive cells. The action of a Turing machine is determined completely by (1) the current state of the machine (2) the symbol in the cell currently being scanned by the head and (3) a table of transition rules, which serve as the “program” for the machine. Each transition rule is a 4-tuple: < State0, Symbol, Statenext, Action >
If the machine reaches a situation in which there is not exactly one transition rule specified, i.e., none or more than one, then the machine halts. In modern terms, the tape serves as the memory of the machine, while the read-write head is the memory bus through which data is accessed (and updated) by the machine. There are two important things to notice about the definition. The first is that the machine's tape is infinite in length, corresponding to an assumption that the memory of the machine is infinite. The second is similar in nature, but not explicit in the definition of the machine, namely that a function will be Turing-computable if there exists a set of instructions that will result in the machine computing the function regardless of the amount of time it takes. One can think of this as assuming the availability of infinite time to complete the computation. These two assumptions are intended to ensure that the definition of computation that results is not too narrow. This is, it ensures that no computable function will fail to be Turing-computable solely because there is insufficient time or memory to complete the computation. If a function is not Turing-computable it is because Turing machines lack the computational machinery to carry it out, not because of a lack of spatio-temporal resources. 1.1. The Definition Formalized
The read-write head is represented by the number h which is the index of the cell scanned by the head. The transition function determines the new content of the tape by returning a new function s but this new function is constrained to differ from the original in at most the cell being scanned. If that cell is modified, then the head must not be moved in the transition, and if it is not modified, then the head is constrained to move at most one cell in either direction. This definition is very similar to that given in the entry on computability and complexity, with the significant difference that the transition function may write a new symbol as well as move during any transition. This change does not alter the set of Turing-computable functions, and simplifies the formal definition by removing the second condition on the transition function in our definition. Both formal definitions permit the alphabet of symbols on the tape to be any finite set, while the original definition insisted on S={0,1} this change also does not impact the definition of the set of Turing-computable functions. 2. Describing Turing Machines
<s0, 1, s0, » >
When we are interested in examining the behaviour of a Turing machine, it is common and perhaps more perspicuous to represent the machine using a state diagram. Here is the machine represented in this format.
In what follows we will describe Turing machines in the state machine format. 2.1 Examples
In the examples that follow we will represent the number n as a block of n+1 copies of the symbol ‘1’ on the tape. Thus we will represent the number 0 as a single ‘1’ and the number 3 as a block of four ‘1’s. We will also have to make some assumptions about the configuration of the tape when the machine is started, and when it finishes, in order to interpret the computation. We will assume that if the function to be computed requires n arguments, then the Turing machine will start with its head scanning the leftmost ‘1’ of a sequence of n blocks of ‘1’s. the blocks of ‘1's representing the arguments must be separated by a single occurrence of the symbol ‘0’. For example, to compute the sum 3+4, a Turing machine will start in the following configuration, where the ellipses indicate that the tape has only zeros on the cells that we can't see, and the upward arrow indicates the cell that is currently scanned.
Under these conventions, the state diagram in Figure 1 describes a machine which computes the successor (add-one) function. That is when started in standard configuration on a tape representing the number n it will halt in standard configuration representing the number n+1. It does this by using state s0 to scan to the first ‘0’ to the right of the (single) block of ‘1’s. It then replaces that ‘0’ by a ‘1’, and scans left in state s1 until a ‘0’ is found (this is the first zero to the left of the block of ‘1’s.) It then moves back to scan the first ‘1’ and halts in state s2. You can see a movie of the execution of this machine here. For another example, consider the machine in Figure 2 which computes the addition function. That is, when started on a standard tape representing the numbers n and m, the machine halts on a tape representing n+m.
2.2 Instantaneous Descriptions of a Computation
Two-way infinite tapes In our original formulation we specified that the tape had an end, at the left say, and stretched infinitely far to the right. Relaxing this stipulation to allow the tape to stretch infinitely far to right and left results in a new formulation of Turing machines equivalent to the original. That is for any Turing machine using a two way tape there is a Turing machine with a one-way infinite tape with the same input-output behavior, and vice versa. Two-dimensional tapes Instead of a one-dimensional infinite tape, we could consider a two-dimensional “tape”, which stretches infinitely far up and down as well as left and right. We would add to the formulation that a machine transition can cause the read-write head to move up or down one cell in addition to being able to move left and right. Again this formulation is equivalent to the original. Arbitrary movement of the head Modifying the definition of a Turing machine so that the read-write head may move an arbitrary number of cells at any given transition does not alter the notion of Turing-computability. Arbitrary numbers of read-write heads Modifying the definition of a Turing machine so that the machine has several read-write heads does not alter the notion of Turing-computability. Arbitrary finite alphabet In our original formulation we allowed the use of only two symbols on the tape. In fact we do not increase the power of Turing machines by allowing the use of any finite alphabet of symbols. 5-tuple formulation A common way to describe Turing machines is to allow the machine to both write and move its head in the same transition. This formulation requires the 4-tuples of the original formulation to be replaced by 5-tuples <State0, Symbol, Statenew, Symbolnew, Move >
Again, this additional freedom does not result in a new definition of Turing-computable. For every one of the new machines there is one of the old machines with the same properties. Non-deterministic Turing machines An apparently more radical reformulation of the notion of Turing machine allows the machine to explore alternatives computations in parallel. In the original formulation we said that if the machine specified multiple transitions for a given state/symbol pair, and the machine was in such a state then it would halt. In this reformulation, all transitions are taken, and all the resulting computations are continued in parallel. One way to visualize this is that the machine spawns an exact copy of itself and the tape for each alternative available transition, and each machine continues the computation. If any of the machines terminates successfully, then the entire computation terminates and inherits that machine's resulting tape. Notice the word successfully in the preceding sentence. In this formulation, some states are designated as accepting states and when the machine terminates in one of these states, then the computation is successful, otherwise the computation is unsuccessful and any other machines continue in their search for a successful outcome. The addition of non-determinism to Turing machines does not alter the definition of Turing-computable. Turing's original formulation of Turing Machines used the 5-tuple representation of machines. Post introduced the 4-tuple representation, and the use of a two-way infinite tape. A more complex machine In addition to performing numerical functions using unary representation for numbers, we can perform tasks such as copying blocks of symbols, erasing blocks of symbols and so on. Here is an example of a Turing machine which when started in standard configuration on a tape containing a single block of ‘1’s, halts on a tape containing two copies of that block of ‘1’s, with the blocks separated by a single ‘0’. It uses an alphabet consisting of the symbols ‘0’, ‘1’ and ‘A’.
At this point, we are either scanning the next ‘1’ of the original block, or the original block has all been turned into ‘A's, and we are scanning the separator ‘0’. In the former case, we make another trip through states s1–s4, but in the latter, we move into state s5, moving leftward. In this state we will repeatedly find ‘A's, which we replace with ‘1’s, and move to the left. If we find a ‘0’, then all of the ‘A's have been turned back into ‘1’s. We will be scanning the ‘0’ to the left of the original cell, and so we move right, and into the final state s6. This copying machine could be used in conjunction with the addition machine of Figure 2 to construct a doubling machine, i.e. a machine which, when started on a tape representing the number n halts on a tape representing 2n. We could do this by first using the copying machine to produce a tape with two copies of n on the tape, and then using the addition machine to compute n+n (=2n). We would do this by identifying the copying machine's halt state (s6) with the adding machine's initial state (s0). The construction just suggested relies on the fact that the copying machine terminates in standard position, which is required for the adding machine to correctly compute its result. By designing Turing machines which start and end in standard configuration, we can ensure that they may be composed in this manner. In the example, the copying machine has a unique terminating state, but this is not necessary. We might build a Turing machine which indicates the result of its computation by terminating on one of many states, and we can the combine that machine with more that one machine, with the identity of the machine which follow dependent on the switching machine. This would enable us to create a machine which adds one to the input if that input is even, and doubles it if odd, for example (should we want to for some reason). 4. What Can Be Computed
Turing's original paper concerned computable numbers. A number is Turing-computable if there exists a Turing machine which starting from a blank tape computes an arbitrarily precise approximation to that number. All of the algebraic numbers (roots of polynomials with algebraic coefficients) and many transcendental mathematical constants, such as e and p are Turing-computable. Computable Functions As we have seen, Turing machines can do more than write down numbers. Among other things they can compute numeric functions, such as the machine for addition (presented in Figure 2) multiplication, proper subtraction, exponentiation, factorial and so on. By adopting a convention for representing TRUE and FALSE, perhaps that TRUE is represented as a sequence of two ‘1’s and FALSE as one ‘1’, we can compute the characteristic functions of computable predicates, and we may combine the results of such functions using the boolean functions: AND, NOT, OR, IF-THEN-ELSE. In fact the Turing-computable functions are just the recursive functions, described below. Universal Turing Machines The most striking positive result concerning the capabilities of Turing machines is the existence of Universal Turing Machines (UTM). When started on a tape containing the encoding of another Turing machine, call it T, followed by the input to T, a UTM produces the same result as T would when started on that input. Essentially a UTM can simulate the behavior of any Turing machine (including itself.) One way to think of a UTM is as a programmable computer. When a UTM is given a program (a description of another machine), it makes itself behave as if it were that machine while processing the input. Note again, our identification of input-output equivalence with “behaving identically”. A machine T working on input t is likely to execute far fewer transitions that a UTM simulating T working on t, but for our purposes this fact is irrelevant. In order to design such a machine, it is first necessary to define a way of representing a Turing machine on the tape for the UTM to process. To do this we will recall that Turing machines are formally represented as a collection of 4-tuples. We will first design an encoding for individual tuples, and then for sequences of tuples. Encoding Turing Machines Each 4-tuple in the machine specification will be encoded as a sequence of four blocks of ‘1’s, separated by a single ‘0’ The first block of ones will encode the current state number, using the unary number convention above (n+1 ones represents the number n).
Figure 4: The Encoding of the Tuple <0, ‘1’, 0, »> To encode a complete machine, we need to simply write down the tuples on the tape, in any order, but separated from one another by two blank cells. The add-one machine of Figure 1, would be represented by the somewhat intimidating string shown in Figure 5. … 010110101111 00 101011011 00 110110110111 00 11010111011110 … Figure 5: The Encoding of the Machine in Figure 1
5. What Cannot Be Computed
Like the real numbers, the number of functions on the natural numbers is not countable. It follows therefore that there are uncountably many such functions that are not computable by any Turing machine. Here we give two examples of uncomputable functions. 5.1 The Busy Beaver
We can prove the uncomputability of the busy beaver function by deriving a contradiction from the assumption that such a machine exists. The crucial step in the proof, is to note that if the Busy Beaver machine were to exist, the productivity of the most productive n+2k state machine is at least p(p(n)), where k is the number of states of the (alleged) Busy Beaver machine. This is demonstrated by building a machine which initially writes n ‘1’s on the tape (which can be done in n states — exercise for the reader), and then connecting the halt state of that machine to the start state of the Busy Beaver machine (resulting in a computation of p(n)), and then connecting the halt state of that machine with another copy of the Busy Beaver machine, resulting a computation of p(p(n)). Thus (if the Busy Beaver machine exists) p(n+2k) = p(p(n)) for any n.
5.2 The Halting Problem
To see the uncomputability of the halting function, imagine that such a machine H exists, and consider a new machine built by composing the copying machine of Figure 4 with H by joining the halt state of the copier to the start state of H. Such a machine, when started on a tape with n ‘1’s determines whether the machine whose code is n halts when given input n, i.e. it computes M(n) = h(n,n). Now lets add another little machine to the halt state of H. This machine goes into an infinite sequence of transitions if the tape contains TRUE when it starts, and halts if the tape contains FALSE (its an exercise for the reader to construct this machine, assume that TRUE is represented by ‘11’, and FALSE by ‘1’.) This composed machine, call it M, halts if the machine with the input code n does not halt on an initial tape containing n (because if machine n does not halt on n, the halting machine will leave TRUE on the tape, and M will then go into its infinite sequence.) and vice versa. To see that this is impossible, consider the code for M itself. What happens when M is started on a tape containing Ms code? Assume that M halts on M, then by the definition of the machine M it does not halt. But equally, if it does not halt on M the definition of M says that it should halt. This is a contradiction, and the Halting machine cannot exist. The fact that the halting problem is not Turing-computable was first proved by Turing in (Turing 1937). 6. Alternative Formulations of Computability
the zero function: z(x) = 0, for all x
by using the operations of composition and primitive recursion. Composition: f(x1,…,xn) = g(h1(x1,…,xn),…, hm(x1,…,xn)) for all g,h1,…,hm
The recursive functions are formed by the addition of the minimization operator, which takes a function f and returns h defined as follows:
It is known that the Turing computable functions are exactly the recursive functions. 6.2 Abacus Machines
The machine can perform two basic operations, namely: add one to the content of a named register (which we will symbolize as n+, where n is the name of the register) and (attempt to) subtract one from a named register, with two possible outcomes: a success branch if the register was initially non-zero, and a failure branch if the register was initially zero (we will symbolize the operation as n-). These are called abacus computers by Lambek (Lambek 1961), and are known to be equivalent to Turing machines. The modern digital computer is subject to finiteness constraints that we have abstracted away in the definition of abacus machines, just as we did in the case of Turing machines. Physical computers are limited in the number of memory locations that they have, and in the storage capacity of each of those locations, while abacus machines are not subject to those constraints. Thus some abacus-computable functions will not be computable by any physical machine. (We won't consider whether Turing machines and modern digital computers remain equivalent when both are given external inputs, since that would require us to change the definition of a Turing machine.) 7. Restricted Turing Machines
Copyright © 2004
-------------------------------------------------------------------------------- A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z Stanford Encyclopedia of Philosophy
The concept of the Turing machine is based on the idea of a person executing a well-defined procedure by changing the contents of an infinite amount of ordered paper sheets that can contain one of a finite set of symbols. The person needs to remember one of a finite set of states and the procedure is formulated in very basic steps in the form of "If your state is 42 and the symbol you see is a '0' then replace this with a '1', remember the state 17, and go to the following sheet." Turing machines shouldn't be confused with the Turing test, Turing's attempt to capture the notion of artificial intelligence. A Turing machine that is able to simulate any other Turing machine is called a universal Turing machine or simply a universal machine as Turing described it in 1947: It can be shown that a single special machine of that type can be made to do the work of all. It could in fact be made to work as a model of any other machine. The special machine may be called the universal machine.
1.1 Informal description
3 Deterministic and non-deterministic Turing machines 4 Universal Turing machines 5 Comparison with real machines 6 A physical Turing machine 7 See also 8 References 9 External links 10 Simulators [edit]
More precisely, a Turing machine consists of: A tape which is divided into cells, one next to the other. Each cell contains a symbol from some finite alphabet. The alphabet contains a special blank symbol (here written as '0') and one or more other symbols. The tape is assumed to be arbitrarily extendible to the left and to the right, i.e., the Turing machine is always supplied with as much tape as it needs for its computation. Cells that have not been written to before are assumed to be filled with the blank symbol.
[edit]
Q is a finite set of states
[edit]
Q is a finite set of states
Old Read Wr. New Old Read Wr. New
A computation of this Turing machine might for example be: (the position of the head is indicated by displaying the cell in bold face) Step State Tape Step State Tape
The behavior of this machine can be described as a loop: it starts out in s1, replaces the first 1 with a 0, then uses s2 to move to the right, skipping over 1's and the first 0 encountered. S3 then skips over the next sequence of 1's (initially there are none) and replaces the first 0 it finds with a 1. S4 moves back to the left, skipping over 1's until it finds a 0 and switches to s5. s5 then moves to the left, skipping over 1's until it finds the 0 that was originally written by s1. It replaces that 0 with a 1, moves one position to the right and enters s1 again for another round of the loop. This continues until s1 finds a 0 (this is the 0 right in the middle between the two strings of 1's) at which time the machine halts. [edit]
[edit]
With this encoding of action tables as strings, it becomes possible in principle for Turing machines to answer questions about the behavior of other Turing machines. Most of these questions, however, are undecidable, meaning that the function in question cannot be calculated by any Turing machine. For instance, the problem of determining whether a particular Turing machine will halt on a particular input, or on all inputs, known as the Halting problem, was shown to be undecidable in Turing's original paper. Rice's theorem shows that any nontrivial question about the behavior or output of a Turing machine is undecidable. If we broaden the definition to include any Turing machine that simulates some Turing-complete computational model, not just Turing machines that directly simulate other Turing machines, a universal Turing machine can be fairly simple, using just a few states and a few symbols. For example, only 2 states are needed, since a 2×18 (meaning 2 states, 18 symbols) universal Turing machine is known. A complete list of the smallest known universal Turing machines is: 2×18, 3×10, 4×6, 5×5, 7×4, 10×3, 22×2. These simulate a computational model called tag systems. A universal Turing machine is Turing-complete. It can calculate any recursive function, decide any recursive language, and accept any recursively enumerable language. According to the Church-Turing thesis, the problems solvable by a universal Turing machine are exactly those problems solvable by an algorithm or an effective method of computation, for any reasonable definition of those terms. [edit]
Even the less powerful models of real machines are much more complex than a Turing machine. For example, a Turing machine describing an algorithm may have a few hundred states, while the equivalent DFA on a given real machine has quadrillions.
[edit]
It is also possible to build a Turing machine on a purely mechanical basis. The mathematician Karl Scherer has indeed built such a machine in 1986 using metal and plastic construction sets, and some wood. The 1.5 meter high machine uses the pulling of strings to read, move and write the data (which is represented using ball bearings). The machine is now exhibited in the entrance of the Department of Computer Science of the University of Heidelberg, Germany. Also, using a few hundred mirrors, one can build an optical universal Turing machine in one's backyard, using the Horseshoe map. This is based on a work by Stephen Smale. The concept of a Turing machine was used as an educational tool in the science fiction novel, The Diamond Age (1995), by Neal Stephenson. The main character, Nell, possesses an interactive book which teaches her creative thinking and logic by presenting puzzles in a story as Turing machines which become more and more complex as the story progresses. They begin as a simple chain-fed clockwork device and progresses to abstract economic processes, trades, and finally the interaction of entire fictional kingdoms. [edit]
Retrieved from "http://en.wikipedia.org/wiki/Turing_machine"
ViewsArticleDiscussionEdit this pageHistory Personal toolsCreate account / log in NavigationMain Page
This page was last modified 23:46, 12 Feb 2005. All text is available under the terms of the GNU Free Documentation License (see Copyrights for details).
http://en.wikipedia.org/wiki/Turing_machine "Historical Introduction --- A Century of Controversy Over the Foundations of Mathematics
We're in a state of euphoria now in the computer business because things are going so well: the web, e-commerce. It's all paying for our salaries, and it's a nice moment to be around, when things are going so well. But I'd like to make the outrageous claim, that has a little bit of truth, that actually all of this that's happening now with the computer taking over the world, the digitalization of our society, of information in human society, you could say in a way is the result of a philosophical question that was raised by David Hilbert at the beginning of the century. It's not a complete lie to say that Turing invented the computer in order to shed light on a philosophical question about the foundations of mathematics that was asked by Hilbert. And in a funny way that led to the creation of the computer business. It's not completely true, but there is some truth in it. You know, most historical statements are a lie, so this one isn't that much worse than most others! So I'd like to explain the philosophical history of the computer. In a way what happened, and I'll tell you more, is that Hilbert said we should formalize all of mathematics, mathematical reasoning. And this failed: it took Gödel and Turing to show that it couldn't be done. It failed in that precise technical sense. But in fact it succeeded magnificently, not formalization of reasoning, but formalization of algorithms has been the great technological success of our time --- computer programming languages! So if you look back at the history of the beginning of this century you'll see papers by logicians studying the foundations of mathematics in which they had programming languages. Now you look back and you say this is clearly a programming language! If you look at Turing's paper of course there's a machine language. If you look at papers by Alonzo Church you see the lambda calculus, which is a functional programming language. If you look at Gödel's original paper you see what to me looks like LISP, it's very close to LISP, the paper begs to be rewritten in LISP! So I'd like to give you this hidden philosophical history of computer technology which is how philosophically minded mathematicians set out to solve once and for all the foundational problems of mathematics and did not succeed but helped to create computer technology as a by product. This was the failure of this project! We're all benefiting from the glorious failure of this project! However this project has not died completely. --- I'm going to start more systematically from the beginning; but I'm trying to give an introduction. --- It's popular to think, well Gödel did this wonderful thing in 1931 and Turing added a lot of profound stuff in 1936, but the world has moved on from that point. And what I'd like to do is to tell you that in fact I've done some more work in this area. You may think it's misguided! Most of the world has shrugged and gone on. We had this disappointment. What Gödel and Turing showed is that axiomatic formal reasoning has certain limitations. You can't formalize it all. And at first people were tremendously shocked and then they shrugged and said, so what? Mathematicians went on, ignoring this. And my misfortune or fortune was that I didn't want to shrug. I said, I want to understand this better. And I'm going to tell you the story of my attempt to understand Gödel incompleteness. --- It's a psychological problem that a good psychiatrist could have cured me of, and then I wouldn't have done any of this work! So let me start at the beginning and tell you this story of a hundred years of intense worry, crisis, self-doubt, self-examination and angst about the philosophy of mathematics. There've been lots of crises in the history of mathematics. Mathematics is not placid, static and eternal. One of the first crises was the Pythagorean result that the square root of two is irrational. And the fact that this was a crisis survives in the word ``irrational''. Remember the Greeks thought that rationality was the supreme goal --- Plato! Reason! If a number is called irrational that means that this was the Gödel incompleteness theorem of ancient Greece. So there was a crisis there. Another crisis was caused by the calculus. A lot of people said this is nonsense, we're talking about infinitesimals, what is this? Bishop Berkeley was a theologian and he said, pure mathematicians make as little sense as theologians, you can't reject us saying we're unreasonable. The way you deal with evanescent quantities in the calculus --- this was before the calculus had a rigorous foundation --- is as bad as our theological discussions! So at that time it was pretty bad! Then there was a crisis about the parallel postulate, about non-Euclidean geometries. So mathematics is not static and eternal! But the particular crisis that I want to tell you about goes back a little more than a hundred years to work of Cantor on set theory.
So Cantor was obsessed with the notion of infinite, and it's not mentioned that he was obsessed with infinite because he was interested in theology and God, which is edited out from the accounts now, but that was the original idea. And Cantor had the idea that if you have 1, 2, 3, ... why stop there?
You can keep going for a while.
Then the next number is ω to the ω to the ω forever.
So anyway you can see this is fantastic stuff! I don't know whether it's mathematics, but it's very imaginative, it's very pretty, and actually there was a lot of practical spin-off for pure mathematicians from what Cantor was doing. Some people regarded set theory as a disease. Poincaré, the great French mathematician, said set theory is a disease, he said, from which I hope future generations will recover. But other people redid all of mathematics using the set-theoretic approach. So modern topology and a lot of abstract mathematics of the twentieth century is a result of this more abstract set-theoretic approach, which generalized questions. The mathematics of the nineteenth century was at a lower level in some ways, more involved with special cases and formulas. The mathematics of the twentieth century --- it's hard to write a history of mathematics from the year ten-thousand looking back because we're right here --- but the mathematics of the twentieth century you could almost say is set-theoretical, ``structural'' would be a way to describe it. The mathematics of the nineteenth century was concerned with formulas, infinite Taylor series perhaps. But the mathematics of the twentieth century went on to a set-theoretic level of abstraction. And in part that's due to Cantor, and some people hate it saying that Cantor wrecked and ruined mathematics by taking it from being concrete and making it wishy-washy, for example, from hard analysis to abstract analysis. Other people loved this. It was very controversial. It was very controversial, and what didn't help is in fact that there were some contradictions. It became more than just a matter of opinion. There were some cases in which you got into really bad trouble, you got obvious nonsense out. And the place you get obvious nonsense out in fact is a theorem of Cantor's that says that for any infinite set there's a larger infinite set which is the set of all its subsets, which sounds pretty reasonable. This is Cantor's diagonal argument --- I don't have time to give you the details. So then the problem is that if you believe that for any infinite set there's a set that's even larger, what happens if you apply this to the universal set, the set of everything? The problem is that by definition the set of everything has everything, and this method supposedly would give you a larger set, which is the set of all subsets of everything. So there's got to be a problem, and the problem was noticed by Bertrand Russell.
Cantor I think may have noticed it, but Bertrand Russell went around telling everyone about it, giving the bad news to everyone! --- At least Gödel attributes to Russell the recognition that there was a serious crisis.
So does this mean that some ways of defining sets are bad, or that the universal set gets you into trouble? What's wrong with the set of everything? So there was a problem with set theory --- that became increasingly clear. I think Russell helped to make it be recognized by everybody that we had a serious crisis and that methods of reasoning that seemed at first sight perfectly legitimate in some cases led to obvious disaster, to contradictions. There were a whole bunch of paradoxes that Russell advertised: the Berry paradox, the one I just mentioned is called the Russell paradox, and there's another paradox, the Burali-Forti paradox. A lot of these paradoxes in fact were really brought to the attention of the world by Russell. Russell would typically have a footnote saying this paradox occurred to me while I was reading a paper by Burali-Forti, so everyone calls it the Burali-Forti paradox. Burali-Forti I think spent his whole life trying to live down this attribution because he didn't believe that mathematics was in trouble! Okay so there was a crisis, and I think Russell was one of the key figures in this. At this point David Hilbert comes to the rescue.
David Hilbert was a very important mathematician around the turn of the century. Unlike Poincaré, a very important French mathematician --- Hilbert was a very important German mathematician --- Hilbert liked set theory. He liked this abstract Cantorian approach. And Hilbert had the idea of solving once and for all these problems. How was he going to do it?
Hilbert said let's use all the technology from symbolic logic, which a lot of people were involved in inventing, and let's go to some final extreme. Because one of the reasons you got into trouble and got contradictions in mathematics with set theory is because words are very vague. What we want to do to get rid of all these problems in mathematics and in reasoning is get rid of pronouns for example, you don't know what pronouns refer to. And there are all kinds of things that are vague in normal language.
So this is the idea that mathematics should be absolutely black or white, precise, absolute truth. This is the traditional notion of mathematics.
The real world we know is an absolute mess --- right? --- everything's complicated and messy. But the one place where things should be absolutely clear, black or white, is in pure mathematics.
The problems are 1931, Kurt Gödel, and 1936, Alan Turing.
They showed that it could not be done, that there were fundamental obstacles to formalizing all of mathematics and making mathematics absolutely black and white and absolutely crystal clear. Remember what Hilbert is proposing is that we should formalize all of mathematics so that everyone on planet earth can agree that a proof is either correct or incorrect. The rules of the game should be absolutely explicit, it should be an artificial language and then mathematics will give you absolute truth. ``Absolute truth'' should be underlined in a very beautiful font and you should hear the angels singing when you say these words! This was the thought that we mathematicians have absolute truth. It's ours --- no one else has it, only us! That was the idea.
Gödel shocked people quite a bit by showing that it couldn't work. It was very, very surprising when Gödel did this in 1931. And Turing went I think more deeply into it. So let me give you a cartoon five minute summary, my take on what they did. Gödel starts with ``this statement is false'', what I'm now saying is a lie, I'm lying. If I'm lying, and it's a lie that I'm lying, then I'm telling the truth! So ``this statement is false'' is false if and only if it's true, so there's a problem. Gödel considered instead ``this statement is unprovable''.
Here unprovable means unprovable from the axioms of Hilbert's formal axiomatic system, unprovable within the system that Hilbert was trying to create.
So there are two possibilities. Either it's provable or it's unprovable. And this means provable or unprovable from the system that Hilbert had proposed, the final goal of formalizing all of mathematics. Well, if it's provable, and it says it's unprovable, we're proving something that's false. So that's not very nice. And if it's unprovable and it says it's unprovable, well then, what it states is true, it's unprovable, and we have a hole. Instead of proving something false we have incompleteness, we have a true statement that our formalization has not succeeded in capturing. So the idea is that either we're proving false statements, which is terrifying, or we get something which is not as bad, but is still awful, which is that our formal axiomatic system is incomplete --- there's something that's true but we can't prove it within our system. And therefore the goal of formalizing once and for all all of mathematics ends up on the floor! Now I don't think that Hilbert really wanted us to formalize all of mathematics. He didn't say that we should all work in an artificial language and have formal proofs. Formal proofs tend to be very long and inhuman and hard to read. I think Hilbert's goal was philosophical. If you believe that mathematics gives absolute truth, then it seems to me that Hilbert has got to be right, that there ought to have been a way to formalize once and for all all of mathematics. That's sort of what mathematical logic was trying to do, that's sort of what the axiomatic method was trying to do, the idea of breaking proofs into smaller and smaller steps. And Leibniz thought about this, and Boole thought about this, and Frege and Peano and Russell and Whitehead thought about this. It's the idea of making very clear how mathematics operates step by step. So that doesn't sound bad. Unfortunately it crashes at this point! So everyone is in a terrible state of shock at this point. You read essays by Hermann Weyl or John von Neumann saying things like this: I became a mathematician because this was my religion, I believed in absolute truth, here was beauty, the real world was awful, but I took refuge in number theory. And all of a sudden Gödel comes and ruins everything, and I want to kill myself! So this was pretty awful. However, this
is a very strange looking statement. And there are ways of rationalizing, human beings are good at that, you don't want to face unpleasant reality. And this unpleasant reality is very easy to shrug off: you just say, well, who cares! The statements I work with normally in mathematics, they're not statements of this kind. This is nonsense! If you do this kind of stupidity, obviously you're going to get into trouble.
into a statement in elementary number theory. In its original form, sure, it's nonsense, who ever heard of a statement in mathematics that says it's unprovable? But in fact Gödel made this into a numerical statement in elementary number theory, in arithmetic. It was a large statement, but in some clever way, involving Gödel numbering of all arithmetic statements using prime numbers, he was writing it so that it looked like a statement in real mathematics. But it really indirectly was referring to itself and saying that it's unprovable.
Now my reaction as a child reading this proof is that I follow it step by step, but I don't like it. It doesn't appeal to me! Which is good, because if I had said I like it, it's wonderful, finished, I go ahead and become a molecular biologist and start up a biotech company, and now I'd be rich, but I wouldn't have done any work in this area!
Now I prefer Turing's approach. Turing goes more deeply into this. Turing starts talking about computers. This is the point where it happens! 1936 Turing Computer Turing has to invent the computer, because Hilbert says that there should be a mechanical procedure to decide if a proof is correct or not. Turing says what Hilbert really means is that there should be a computer program for checking proofs. But first Turing has to say what a computer is, it's a Turing machine, and all of this is in a paper of Turing's in 1936, when there were no computers, so it's a fantastic piece of work. And I would like to claim that this is the invention of the computer. These were general-purpose computers, that was the idea, on paper.
The halting problem says there's no way to decide if a computer program will eventually halt.
But what Turing showed is that if you put no time limit, then there is no solution. There's no way to decide in advance whether a computer program will halt or not. If it halts you can eventually discover that by running it. The problem is to realize that you've got to give up. So there's no mechanical procedure that will decide in advance if a computer program will halt or not, and therefore, it turns out, there is no set of mathematical axioms in Hilbert's sense that can enable you to prove whether a program will halt or not. Because if you could always prove whether a program will halt or not, you could run through all possible proofs in size order and check whether they're correct, and eventually either find a proof that the program's going to halt or find a proof that it's not going to halt. And this would give you a way to decide in advance whether a program's going to halt. Now in practice running through all possible proofs requires an astronomical amount of time. Imagine how many proofs are there that are one page long! You'd never get through them! But in principle you can run through all possible proofs in size order and check whether they obey the rules, if it's a Hilbert formal axiomatic system. So if you had a formal axiomatization of mathematics that enabled you to always prove whether a program halts or not, that would give you a mechanical procedure, by running through all possible proofs in size order, to decide whether a program will halt or not. And Turing showed that you can't do it. His proof, by the way, involves Cantor's diagonal argument --- all these ideas are connected, but there's no time to go into that. So I think that Turing's work makes the limits of mathematics seem much more natural, because we're talking about a question about a physical device, it's a computer.
You fantasize a little bit, you make it a theoretical computer, a computer that can go on forever, that never breaks down, that has as much storage as it wants, so that if numbers get too big it can keep going anyway. But that's not too much of a fantasy; we have devices like that everywhere, right? So it sounds much more concrete. The limits of mathematics discovered by Turing sound more serious, more dangerous than the ones that Gödel found.
And in fact Gödel's paper as I said uses LISP, there's a programming language hidden in it, and in Turing's paper there's a programming language, given explicitly, Turing machines, and it's a machine language. It's actually a very bad machine language, it's a machine that no person in their sane mind would want to program. But Turing wanted to keep it as simple as possible. Obviously, if his paper had included a manual for the machine language of a real machine, it would have been hopeless, no one would have understood it. Okay, now what happens with all of this? What happens with all of this is that Hilbert dies, World War II comes, and when I'm a child in the 1950's I could still read essays by John von Neumann talking about all of this, but the world was clearly going in a less philosophical direction. Things were going downhill rapidly until we're all billionaires with our web start-ups! People were less concerned about philosophy, and computers were becoming a technology, and Turing was very involved in that, and so was von Neumann. But stupidly I wanted to understand what was going on in the foundations of mathematics, so in a way I'm stuck in the 1930's, I never got past that stage. What happened? What happened with me is that I couldn't accept the fact that everybody said, who cares! Now it's true that there are a lot of things in life besides the foundations of mathematics and epistemology! There're things like having a family, earning a living, wars, politics, lots of stuff out there, obviously! But what I couldn't accept was that even in the world of pure mathematics, mathematicians were saying, so what, in practice we should do mathematics exactly the same as we've always done it, this does not apply to the problems I care about! That was basically the reaction to Gödel's and Turing's work on incompleteness. At first there was terrible shock, then it went from one extreme to another. Who cares, people would say, it's obvious, or it's irrelevant! This has no impact in practice on how we should do mathematics. I was very unhappy with that. I was obsessed by incompleteness, and I had an idea. When I was a kid I really wanted to be a physicist, and a lot of mathematicians say I never made it into mathematics really --- I never succeeded, I'm still stuck! I wanted to be a physicist, and I got corrupted by a lot of ideas from physics. While all of this crisis was going on in mathematics, there was a parallel crisis going on in physics, which actually started in the 1920's: that's quantum mechanics, and the key date is 1924.
And that's the whole question of uncertainty and randomness in fundamental physics. So when I was a kid, besides reading essays talking about Gödel's incompleteness theorem saying ``Oh, my God'', there were also essays asking what happened to determinism in physics, what happened to predictability, can there be randomness, does God play dice? Einstein said no, God doesn't play dice. He hated quantum mechanics. And everybody else said yes, God plays dice. God plays dice! Quantum mechanics is the most successful physical theory ever. We get transistors and computers from it. But even though Einstein helped to contribute to the creation of quantum mechanics he hated it. So it looks like Einstein was wrong. God does play dice!
And one of my motivations was the prime numbers. There's some work on the prime numbers that says that in some ways the prime numbers can be looked at statistically. There seems to be a certain amount of randomness in the distribution of the primes. That's one of the ways that people try to think about the prime numbers. And this even happens in number theory, which is the queen of pure mathematics! So on the one hand I heard this talk about probabilistic ways of thinking about the primes --- this was heuristic --- and this stuff about God plays dice in fundamental physics --- what goes on in the atom is random --- and I begin to think, well, maybe that's what's going on in the foundations of mathematics. This is what I set out to do, and this project took a long time. One of the first steps is clarifying what do you mean by randomness. What do you mean by lack of structure, lack of order, lack of pattern?
So this is a kind of a logical notion of randomness rather than a statistical notion of randomness. It's not like in physics where you say a physical process is random like coin tossing. I don't care where something comes from. I just look at something and say does it have structure or pattern or not. So this is logical or structural randomness as opposed to physical unpredictability and randomness. It's different --- it's very closely related, but they're different.
By the way, this is also what axioms do. I would say that axioms are the same idea. You have a lot of theorems or mathematical truth and you're compressing them into a set of axioms. Now why is this good? Because then there's less risk. Because the axioms are hypotheses that you have to make and every time you make a hypothesis you have to take it on faith and there's risk --- you're not proving it from anything, you're taking it as a given, and the less you assume, the safer it is. So the fewer axioms you have, the better off you are. So the more compression of a lot of theorems, of a body of theory, into a small set of axioms, the better off you are, I would say, in mathematics as well as physics. Okay, so this is this notion of lack of structure or randomness. You have to define it first! If I'm going to find randomness or lack of structure, lack of pattern, in pure mathematics, first I've got to say what do I mean by that. And I like to call this subject algorithmic information theory. It deals with this algorithmic information. Or you can call it complexity if you like, program-size complexity.
The basic concept is to look at the size of the most concise program, the smallest program --- I don't care about running time --- it's the most concise program that calculates something. That's the number of bits I have to give a computer in order to get it to produce this object. That's my most concise algorithmic description of something, and that's how I measure its complexity, its algorithmic information content or its program-size complexity.
So what happens when you start looking at the size of programs? --- and then something is random if the smallest program that calculates it is the same size as it is, and there's no compression. So the whole idea is, look at the size of computer programs, don't care about run time --- if it takes a billion, billion years I don't care! Information is the only thing I'm thinking about, bits of information, size of computer programs. Okay? So what happens when you start playing with this idea? What happens is, everywhere you turn, you get incompleteness and undecidability, and you get it in the worst possible way. For example this happens with the first thing you want to do: you can never decide that an individual string of digits satisfies this definition of randomness. Impossible! You can never calculate the program-size complexity of anything. You can never determine what the size of the smallest program is. If you have a program that calculates something, that gives you an upper bound, its size is an upper bound on the program-size complexity of what it calculates. But you can never prove any lower bounds. And that's my first incompleteness result in this area and I think Jack Schwartz got very excited about it. In normal, practical, useful complexity theory where you talk about time rather than bits of information, lower bounds are much harder than upper bounds. To get lower bounds on complexity is much harder than getting upper bounds on complexity. Because if you find a clever algorithm you get an upper bound on the time it takes to calculate something; if you find a way to do it that's fast you've shown that it can be done that fast. The problem is to show that you've gotten the fastest possible algorithm, that's much harder, right? But it can be done in some cases, within a class of possible algorithms. Well, in algorithmic information theory you can't prove any lower bounds! And I had an article about this in 1975 in Scientific American. The basic idea is that you can't prove any lower bounds on the program-size complexity of individual objects. So in particular even though most strings of digits satisfy this definition of randomness, they're incompressible in this sense, they're random in this sense of lack of structure --- it turns out you can show easily that most objects satisfy this definition, they have no structure --- if you look at all hundred digit numbers, almost all of them have no structure according to this definition, but you can never be sure in individual cases, you can never prove it in individual cases. More precisely, there may be finitely many exceptions. With N bits of axioms you can determine all the objects of program-size complexity up to N. But that's as far as you can go. And my worst incompleteness result, my very worst incompleteness result, where you have complete lack of structure in pure mathematics, has to do with a number I defined called the halting probability.
O = halting probability How is this number defined? It's very simple. Turing said you can't decide whether a program halts, there's no mechanical procedure for doing that. And I say, let's consider a real number O which is the probability that a program generated by tossing a coin halts. So I'm averaging over Turing's halting problem, saying if I generate a program by coin tossing, what is the probability that it halts, with no time limit? So this will give me a real number that's determined if you tell me --- there's a subscript --- what's the programming language. Ocomputer = halting probability of computer Once you decide, then O is a well-defined real number. Mathematically it's not a very sophisticated thing! Compared to large cardinals, sophisticated mathematics, this is a fairly low-brow object.
What is it that's maximally unknowable? Well, it's the digits or bits of this number. Once I fix the computer programming language this halting probability is a specific real number, that depends on the choice of computer, or the programming language in which I generate a program by coin tossing. So this becomes a specific real number, and let's say I write it out in binary, so I get a sequence of 0's and 1's, it's a very simple-minded definition. Well, it turns out these 0's and 1's have no mathematical structure. They cannot be compressed. To calculate the first N bits of this number in binary requires an N-bit program. To be able to prove what the first N bits of this number are requires N bits of axioms. This is irreducible mathematical information, that's the key idea. O is irreducible information This should be a shocking idea, irreducible mathematical information, because the whole normal idea of mathematics, the Hilbertian idea, the classical idea of mathematics, is that all of mathematical truth can be reduced to a small set of axioms that we can all agree on, that are ``self-evident'' hopefully. But if you want to determine what the bits of the halting probability O are, this is something that cannot be reduced to anything simpler than it is. O has a mathematical definition with a rather simple structure once I specify the computer, or the programming language, I've even written out a program in LISP that calculates this number in a weak sense. You can't calculate this number. If you could calculate it, then it wouldn't be unknowable! You can get it in the limit from below, but it converges very, very slowly --- you can never know how close you are --- there is no computable regulator of convergence, there is no way to decide how far out to go to get the first N bits of O right. To get O in the limit from below, you just look at more and more programs, for more and more time, and every time you see that a K-bit program halts, that contributes 1/2K to the halting probability.
So the time you need to get the first N bits of O right grows like the longest possible finite run-time of an N-bit program, which is a version of the Busy-Beaver function.
So this number O is a real number between 0 and 1. It's the probability that a program each of whose bits is generated by an independent toss of a fair coin eventually halts. And I'm fixing the programming language, I pick the universal Turing machine, there's a subscript, it's OUTM, it's the halting probability of a particular universal Turing machine. And I actually pick a particular UTM that I programmed in LISP, just to fix the ideas. But you could do it with essentially any universal Turing machine with self-delimiting programs; it would work. So O is maximally unknowable. This is a case where mathematical truth has no structure or pattern and it's something we're never going to know! So let me tell you what I've got here. What I've got here is maximum randomness --- like independent tosses of a fair coin --- in pure mathematics. In fact, I can even do it in elementary number theory, like Gödel did. I can make determining bits of O into an assertion about a diophantine equation. The point is, here you've got a simple mathematical question --- which is what is each bit of O: is the first bit 0 or 1, is the second bit 0 or 1, is the third bit 0 or 1 --- but the answers have no structure, they look like independent tosses of a fair coin, even though each answer is well-defined mathematically, because it's a specific bit of a specific real number and it has to be a 0 or a 1. In fact, we're never going to know: this is my version of independent tosses of a fair coin in pure mathematics. Even if you knew all the even bits of O it wouldn't help you to get any of the odd bits. Even if you knew the first million bits, it wouldn't help you to get the next one. It really looks like independent tosses of a fair coin, it's maximally random, it has maximum entropy. Physicists feel comfortable with randomness, but this is the black or white world of pure mathematics --- how is this possible, how can it be? Each of these bits is well-defined, it's a specific 0 or a 1, because O is a specific real number once I fix the universal Turing machine or the programming language that I'm dealing with. But it turns out that the right way to think about each bit is that it's not black or white, it's not that it's a 0 or a 1, it's so well balanced, it's so delicately balanced, that it's grey! Here's another way to put it. Let's go back to Leibniz. What's the idea of mathematics? The normal idea is that if something is true, it's true for a reason --- Leibniz! --- if something is true it's true for a reason. Now in pure math, the reason that something is true is called a proof, and the job of the mathematician is to find proofs, to find the reason something is true. But the bits of this number O, whether they're 0 or 1, are mathematical truths that are true for no reason, they're true by accident! And that's why we will never know what these bits are. In other words, it's not just that Hilbert was a little bit wrong. It's not just that the normal notion of pure mathematics is a little bit wrong, that there are a few small holes, that there are a few degenerate cases like ``This statement is unprovable''. It's not that way! It's much, much worse than that! There are extreme cases where mathematical truth has no structure at all, where it's maximally unknowable, where it's completely accidental, where you have mathematical truths that are like coin tosses, they're true by accident, they're true for no reason. That's why you can never prove whether individual bits of O are 0 or are 1, because there is no reason that individual bits are 0 or 1! That's why you can't find a proof. In other words, it's so delicately balanced whether each bit is 0 or 1 that we're never going to know. So it turned out that not only Hilbert was wrong, as Gödel and Turing showed... I want to summarize all of this. With Gödel it looks surprising that you have incompleteness, that no finite set of axioms can contain all of mathematical truth. With Turing incompleteness seems much more natural. But with my approach, when you look at program size, I would say that it looks inevitable. Wherever you turn, you smash up against a stone wall and incompleteness hits you in the face!
So this is what I've been working on. Now what is the reaction of the world to this work?! Well, I think it's fair to say that the only people who like what I'm doing are physicists! This is not surprising, because the idea came in a way from physics. I have a foreign idea called randomness that I'm bringing into logic, and logicians feel very uncomfortable with it. You know, the notion of program size, program-size complexity is like the idea of entropy in thermodynamics. So it turns out that physicists find this nice because they view it as ideas from their field invading logic. But logicians don't like this very much. I think there may be political reasons, but I think there are also legitimate conceptual reasons, because these are ideas that are so foreign, the idea of randomness or of things that are true by accident is so foreign to a mathematician or a logician, that it's a nightmare! This is their worst nightmare come true! I think they would prefer not to think about it. On the other hand, physicists think this is delightful! Because they remember well the crisis that they went through in the 1920's about randomness at the foundations of physics, and they say, it's not just us, we're not the only people who have randomness, pure math has it too, they're not any better than we are! I'll give an example of the attitude of physicists to my theory. It just so happens that this week I found it by chance. There's an English magazine New Scientist that comes out every week; it's like an English version of Scientific American, except that it's a little livelier, it's a little more fun, and it comes out every week. And the current issue --- the one that appeared February 26th, the next issue hasn't come out yet --- of New Scientist has on its cover an article called ``Random Reality''. And if you open the issue and look at this article, it turns out to be an article about the work of two physicists, very speculative work. They're trying to get space and time, three or four dimensional spacetime, our world, to emerge from a random substratum underneath. Go look at it if you like. There's a link on my web site to this article, ``Random Reality''. Or get the New Scientist. The reason that I mention this article is that these physicists say that their work was inspired by Gödel's and my work on the limits of logic; they're trying to absorb this stuff. They say that physicists were interested in Gödel's result, but they couldn't relate to it, it's not in terms that make sense to a physicist. But my work, they say, that makes sense to a physicist! It's not surprising: I got the idea by reading physics. So it makes sense to them because it's an idea that came from their field and is coming back to their field. Actually, they don't use my definitions or my theorems at all, because I was asked to referee their paper, and I had to say that it really has nothing to do with me. My stuff is mentioned in the introduction because it helped to stimulate their work, but actually their work is in physics and has nothing to do with my area, which is algorithmic information theory. But I think this is an interesting example of the fact that crazy ideas sometimes have unexpected consequences! As I said, formal systems did not succeed for reasoning, but they succeeded wonderfully for computation. So Hilbert is the most incredible success in the world, but as technology, not as epistemology. And unexpectedly there are physicists who are interested in my notion of program-size complexity; they view it as another take on thermodynamical entropy. There's some work by real physicists on Maxwell's demon using my ideas; I mention this for those of you who have some physics background. But I must say that philosophers have not picked up the ball. I think logicians hate my work, they detest it! And I'm like pornography, I'm sort of an unmentionable subject in the world of logic, because my results are so disgusting! So this is my story! To end, let me quote from a posthumous collection of essays by Isaiah Berlin, The Power of Ideas, that was just published: ``Over a hundred years ago, the German poet Heine warned the French not to underestimate the power of ideas: philosophical concepts nurtured in the stillness of a professor's study could destroy a civilization.'' So beware of ideas, I think it's really true. Hilbert's idea of going to the limit, of complete formalization, which was for epistemological reasons, this was a philosophical controversy about the foundations of mathematics --- are there foundations? And in a way this project failed, as I've explained, because of the work of Gödel and Turing. But here we are with these complete formalizations which are computer programming languages, they're everywhere! They pay my salary, they probably pay your salary... well, this is the School of Computer Science, it pays for all of this, right? Here we are! So it worked! In another sense, it worked tremendously. So I like to apologize in an aggressive way about my field. I like to say that my field has no applications, that the most interesting thing about the field of program-size complexity is that it has no applications, that it proves that it cannot be applied! Because you can't calculate the size of the smallest program. But that's what's fascinating about it, because it reveals limits to what we can know. That's why program-size complexity has epistemological significance. More seriously, I think the moral of the story is that deep ideas don't have a spin-off in dollars right away, but sometimes they have vastly unexpected consequences. I never expected to see two physicists refer to my stuff the way they did in ``Random Reality''. So who knows! It's true that the computer pays for our salaries but I think it's also true that there are a lot of fascinating impractical ideas out there, and sometimes when an idea is so beautiful --- I've been having wonderful conversations with people here --- Peter Lee told me over lunch, this idea is so beautiful, it's got to be right! Those are the ideas to watch out for! Those are the dangerous ones, the ones that can transform our society. This little idea of a web, for example, of linking stuff into a web! Or the idea of having completely artificial languages, because then it becomes mechanical to see what they mean... Very dangerous ideas! Thanks very much! Bibliography
A transcript of another version of ``A century of controversy over the foundations of mathematics'' was published in C. Calude and G. Paun, Finite versus Infinite, Springer-Verlag London, 2000, pp. 75-100. For a newer version of the physics described in the New Scientist ``Random reality'' article, see http://arXiv.org/abs/gr-qc/0009023, ``Process physics: modelling reality as self-organising information,'' by R. Cahill, C. Klinger and K. Kitto. The original reference is M. Chown, ``Random reality,'' New Scientist, Vol. 165, No. 2227 (26 February 2000), pp. 24-28. For a reaction to my work from mathematicians, see J. Casti and W. DePauli, Gödel, Perseus Publishing, 2000. For a reaction from a physicist, see D. Ruelle, Chance and Chaos, Princeton University Press, 1991. For a reaction from philosophers, see L. Brisson and F. Walter Meyerstein, Puissance et limites de la raison, Les Belles Lettres, 1995; Inventing the Universe, SUNY Press, 1995; Inventer L'Univers, Les Belles Lettres, 1991. Even though Gödel and Turing exploded Hilbert's dream of a formal axiomatic system for all of mathematics, for several decades Jacob T. (``Jack'') Schwartz (Courant Institute, NYU) has been working on precisely this! But what Schwartz is trying to achieve is not a formal axiomatic system that captures all of mathematical truth, which is impossible, but just one that can get to a significant theorem of real mathematics, say, the Cauchy integral theorem in the theory of functions of a complex variable. The goal is formal proofs that are comprehensible to humans and that simultaneously can be verified by a mechanical proof checker. In order to achieve this, Schwartz uses as his formal system a rich axiomatization of set theory within first order logic. And he and collaborators have discovered decision procedures for several significant sublanguages of set theory, which the proposed formal proof checker would incorporate. As an application for such a system, Schwartz envisions a proof checker that examines programs written in a set-theoretic programming language interspersed with assertions, and that attempts to verify that all the subsequent assertions follow from the initial assertion. Schwartz has convinced me that probably no fundamental obstacles stand in the way of achieving these goals, and that what is required is basically good engineering and a great deal of hard work. Schwartz has programmed substantial fragments of this system in his powerful set-theoretic programming language SETL, which employs standard mathematical notation together with finite sets and mappings. And he has also worked through many of the necessary proof schemas. I believe that his intuition that general-purpose first order logic is too weak, and that a rich axiomatization of set theory is a much better basis for actually developing a formalization of real, working mathematics, is fundamentally sound." |
Guest:
login
