Sense and Pattern
What are our senses? Assuming the Darwinian hypothesis of common descent, for the sake of argument, we can look to other biological organisms for clues. After all, humans are not unique in their capacity to sense the state of the physical world. Other animals can see, hear, smell, feel and taste.
The simplest organisms, single-celled organisms, also sense the state of the physical world. They do not “see” or “hear”, per se, but they do measure or sense the state of the physical world around them and react accordingly. Bacterial conjugation is mediated by the pilus, a small hair-like structure that enables a receptor bacterium (which has no pilus) to sense and attach to a donor bacterium (which has a pilus) so genetic material can be transferred. Once the transfer has occurred, the donor will use the genetic material to construct its own pilus, converting it into a donor bacterium.
At an even smaller scale, the many intra-cellular functions are performed by large molecules called polymers. The DNA replication process utilizes numerous polymers. Consider one polymer in particular, the restriction enzyme or restriction endonuclease. Its purpose is to cut the DNA strand at a specific point. The endonuclease performs this operation by chemically recognizing a specific DNA sequence (genetic code pattern) in the region that it is to perform the cut. Each distinct restriction enzyme exists for the purpose of cutting the DNA at one specific point and it is constructed in such a fashion that it chemically attaches only to the DNA and only at that point.
The restriction enzyme is a chemical which, in the language of computing theory, performs pattern recognition. It is really nothing more than a very large molecule, or macromolecule, yet it can discriminate between the billions of base pairs along the length of the DNA which it is not supposed to cut and attach to the DNA only at the points where the DNA sequence is a chemical match. The endonuclease, despite not even being a living thing, is capable of categorizing the physical world. That is, the endonuclease can discriminate between this and that.
Whatever else can be said about what sense perception is, its functional role is exactly that of discrimination. Sense perception enables us to discriminate friend from foe, male from female, predator from prey, and so forth.
Discrimination and Symbols
You are presently reading the words which I have written on this page. Written words are discrete symbols, meaning, they are easily distinguished from one another. Words are unlike liquid which is fluid and continuous. Once you pour a cup of water into a bowl filled with water, there is no way to continue distinguishing the water which was once in the cup from that which was already in the bowl. The water mixes together in a fluid, amorphous manner. On the other hand, pebbles, like those along the bottom of a creek, are easily distinguished from one another. If you have five pebbles in your hand, and I give you two more to hold in your hand and ask that you keep track of them so you can give back the very same pebbles to me, you will be able to do so. If I had asked you to do the same with a cup of water poured into a larger bowl of water, you would be unable to do so.
This difference is the distinction between the discrete and the continuous. The discrete consists of everything which can be easily distinguished. But distinguishing or discriminating presupposes a discriminator. Restriction endonuclease can discriminate between the portion of the DNA sequence it is responsible for cutting and all other DNA sequences but it cannot discriminate between red-colored and blue-colored objects because it is not a color-discriminator. The human retina, optic fiber, visual cortex and the other components of human vision do comprise a color-discriminator (within the range of human-visible light). With some fuzziness around the boundary (violets), humans can reliably distinguish red-colored objects from blue-colored objects.
The human brain is also capable of distinguishing auditory objects. The consonants and vowels of various languages can be reliably distinguished from one another by their speakers. This ability to discriminate between the discrete auditory objects of language is a crucial building block of human language. If the sounds of words were indistinguishable from one another – like water which, once mixed, is indistinguishable – communication through sound would not be possible.
Symbols are not abstractions even though abstraction is involved in the use of symbols. Symbols are physical objects. Consider a box filled with wood cutouts of letters of the English alphabet. We hand them to a young child who is just learning the alphabet and ask her to organize them however she likes. Depending on how well she has learned her alphabet, she may organize them by grain, color, weight, size, lightness/darkness, or geometric shape. If she organizes them by geometric shape, we will recognize that she has grasped the abstraction of letter. The “letter A” is an abstraction which exists independent of its physical instantiation. But it is important to keep in mind at all times that the abstraction of the letter A is not a symbol, it is an abstraction. The symbol A is only, ever a physical thing. It is the sound spoken or the letter written but, in all cases, it is a measurable, physical object. The ability to discriminate the symbol A from the symbol B is what makes language possible.
Calculation as Physical Prediction
Since symbols are physical, we can build artificial machines which recognize them and manipulate them. When you consider the restriction endonuclease, for example, we are merely following in Nature’s footsteps. Early computer programs were entered into electronic computers with the use of punch cards or punched paper tape. The computing device had an input sensor which could discriminate between a punch and a non-punch and input a series of such symbols. The input device converted the symbols from mechanical to electrical form in the computer’s memory.
One of the earliest mechanical computers was Charles Babbage’s difference engine. It is a machine built out of metallic parts which can accept inputs through setting levers and then produce an output after cranking the machine through its cycle. Calculation can be defined as prediction of the long-run steady state of such a physical device.
Computation and Randomness
In 1936, Alan Turing published the foundational paper On computable numbers, with an application to the Entscheidungsproblem in which he presented a thought-experimental device which is today called the Turing Machine. One particular kind of machine which Turing described is the Universal Turing Machine (UTM). It is the mathematical formalization of the computer. Nowadays, we find the fact that machines can perform general problem-solving tasks unremarkable. But at the time Turing wrote, “computer” was an occupation, not a device. The unique insight of Turing was that it is possible to build a computing device which can be used as a general problem-solver, that is, to solve any given kind of mathematical problem.
Armed with such a device, the natural question to ask is whether we might be able to solve any mathematical problem whatever. Turing answered that question in the very same paper: no. I will sketch the argument he gave to prove it.
Every program that is executed on a Turing machine will either halt after some finite number of steps or will continue indefinitely without halting. Turing asked: is there a program that decides, for any given program, whether or not it will halt? Let us assume that there is such a program and let us name it HALT(x), where x is the program for which it is to be decided whether or not it halts. Further, we define HALT(x) such that when x halts, HALT(x) does not halt, and when x does not halt, HALT(x) halts. Finally, we pass HALT to itself and we ask what happens? For if HALT(HALT) halts, then it does not halt and if HALT(HALT) does not halt, then it halts. Thus, we have shown by contradiction that our initial assumption was false. There is no such program.
Turing’s result has very general implications for mathematics since the Universal Turing Machine can model the behavior of any formal system. The mathematician Gregory Chaitin has extended Turing’s work and has shown that the consequences of the fact that there are unprovable mathematical truths are staggeringly broad. Chaitin has shown the connection between Godel’s famous 1931 incompleteness theorems and Turing’s uncomputable problems. “There are mathematical facts that are true for no reason”, says Chaitin.
Chaitin’s most famous contribution to mathematics is his halting probability, Omega. The idea of Omega is to attempt to “solve” the halting problem by estimating the probability that a program halts rather than directly answering the question in each particular case. After applying a suitable “prefix” to each program so that it is “self-delimiting”, Chaitin is able to apply a probability distribution over the set of all programs and then ask what is the probability that any program chosen at random from the set of all programs will halt? It turns out that the numerical value of this probability is itself uncomputable - it must be uncomputable, because we can use its numerical value to solve the halting problem in particular cases.
This is remarkable because we have a number that has a definite value - the halting probability exists - but finding its actual value is maximally computationally difficult and completely indistinguishable from a random number generated through physical methods, for example. That is, the halting probability possesses absolutely no mathematical properties at all.
We can construct a physical device that will compute the digits of Omega in worst-case time1 and we can add as many extensions to this device as desired (more memory banks). We cannot, however, state what the long-run behavior of such a device will be.
Truth and Proof
“What is truth?”, Pilate asked Saint Paul. Philosophers have struggled with this question for millenia. Many answers have been given but important properties that have been consistently identified is that the truth must be self-consistent and unambiguous.
We can imagine a brute-force approach to settling the question of what is true, once and for all. Let us write out every syntactically correct English sentence and then ask whether it is true or false. But among these sentences will be one that states the Liar Paradox and puts any propositional concept of truth to the test.
“This sentence is false.” Well, is it? If we say it is false, then it is true. If we say it is not false, then it is false.
So, there are propositional sentences that are neither true nor false. It is fruitless to troubleshoot the issue by abolishing self-reference. We can construct mutually-referential sentences with precisely the same effect and it turns out that there is nothing bizarre, unnatural or meaningless about sentences that refer to other sentences, including themselves.
In the face of this problem, we might try a more modest approach. Perhaps the problem is that natural language is vague. Instead of enumerating English language sentences, we restrict ourselves to statements in a fully formalized mathematical language, such as logic, and rather than asking whether the proposition is true or false, we restrict ourselves to asking whether it is provable or not. But it turns out that we can construct a version of the liar paradox in any suitably powerful formal language, as well. Namely, we can construct a true proposition that says “This sentence is unprovable” and we are right back where we started. In every formal system, there are well-formed, true propositions that cannot be proved. This is Godel’s first incompleteness theorem.
This is problematic because the most interesting proposition we might like to prove is the proposition that states that our formal system is consistent. If we could prove that a formal system is consistent, then we could go to sleep and rest well, knowing that a contradiction will never arise in our mathematics. This can be done for first-order logic, for example. Here again, Godel disappoints us. A formal system is consistent precisely when it cannot prove itself consistent. This is his second incompleteness theorem. This means we can never rest in the full knowledge that our formal system has no hidden contradictions unless we have already proved it consistent in some other, more general formal system but this more general formal system itself now has precisely the same problem we started with - it cannot prove itself consistent, provided that it is consistent.
The Limits of Proof
From Godel’s work, we can easily show that it is not possible to build a generalized proof generator or any machine for discovering truth. Mathematician Rudy Rucker gives an approachable argument to show why this is the case in his book, Infinity and the Mind. Imagine that there exists a Truth Machine that, when given a book, will decide whether the book is true or false. Now, imagine a book that contains the blueprint and specification of the Truth Machine itself and tacked onto the blueprint and specification the claim, “such a machine will never say that this book is true.” If the machine attempts to say the book is true, it would be false, and vice-versa.
The Limits of Knowledge
The work of Godel, Turing and Chaitin have three important consequences to epistemology:
-
Mathematicians cannot design and build a self-obsoleting mechanical mathematician. The human mathematician is ineradicable.
-
We cannot construct a mathematical theory of everything
-
We cannot construct a physical theory of everything
Each point follows from the preceding. Because we cannot build a self-obsoleting mechanical mathematician (a theory that is more powerful than our own ability to comprehend), we cannot construct a mathematical theory of everything.
Because we cannot construct a mathematical theory of everything, because symbols are physical, because calculation can be defined as predicting the long-run state of a mechanical device, and because we can build a physical device to compute the digits of Omega whose long-run behavior cannot be predicted, we cannot construct a physical theory of everything.
Clayton -
1This can be a bit confusing; When mathematicians say that something is “uncomputable”, they are actually making a statement about time-bounds… the time required to compute the answer is slower than any computable function. The idea is that the only way to see the solution to an uncomputable problem is to run it on a Turing machine and see what happens… there are no shortcuts, no way to save time and you’re never sure that you’re done no matter how long you wait.
