Received Date: November 10, 2014; Accepted Date: November 11, 2014; Published Date: November 20, 2014
Citation: Zagoskin AM, Sowa AP (2014) Can We See or Compute our Way out of Plato’s Cave? J Appl Computat Math 3:192. doi: 10.4172/2168-9679.1000192
Copyright: © 2014 Zagoskin AM. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Visit for more related articles at Journal of Applied & Computational Mathematics
Over the last fifteen years a quiet revolution in physics occurred. This was the result of an effort to build quantum computers; and while that effort itself was in no way “quiet” (even against the background of the LHC, Higgs boson and string theory), its most significant outcome to date is not something well publicized. All the same, the result is revolutionary indeed. As it turns out, one actually can create quite macroscopic systems which display essentially quantum behaviour-and there seems to be no fundamental barrier on our ability to make such systems bigger and bigger. The real impact of this revolution will be not so much on science (after all, we just keep obtaining results, which agree with normal quantum mechanics) or technology (we already have got more than enough Great Seals of England to crack nuts with), as on philosophy. Many questions about “reality”, “objectivity”, “existence”, etc., imposed on us by quantum mechanics, could remain until now the speculations of a small community, while the rest of physicists happily shut-up and calculated. Now, it seems, these questions must be confronted, and with the clear understanding that the common language of physicists may be inadequate to deal with them.
This is not something new: it was the inadequacy of natural language that spurred the development and application of mathematics to exact sciences. The basic theories are conveniently formulated in this elaborate and formal way, in a language far removed from our intuition and experiences. Their confirmation or refutation, their interdependence and compatibility, in most cases can only be checked by investigating some observable predictions that are linked to theoretical foundations by long chains of mathematical reasoning. These chains-at least, in the case of physics – normally contain many explicit and implicit assumptions and approximations, which fall far short of mathematical rigour – to say nothing on the question of “what is mathematical rigour?” Even so, the verification and the usefulness of fundamental theories become critically dependent on our ability to follow these chains – to perform computations, thus giving computations an independent epistemological status. Here, we present a sketch of arising problems, as seen by a physicist and a mathematician from their different vantage points. We do not presume to propose any solutions-yet.
In Stanislaw Lem’s novel “Solaris” 1, the protagonist, Dr Kelvin, finds himself on an almost abandoned space station, in the midst of bizarre and sinister events. The events are actually so bizarre, that he starts questioning his own sanity, and so sinister, that he would consider insanity a happy alternative. Dr. Kelvin is a scientist; therefore, after formulating an ad hoc hypothesis (his own insanity), which would explain his observations, he needs to conduct an experiment to test it. He knows that delusions, produced by our own brain, can seem extremely realistic and independent of our conscious self. He could take certain drugs and compare their effects with what he knows they should be–but how can he be sure the effect he anticipates is not also a delusion? Eventually, he takes a different course of action. Kelvin orders a satellite orbiting the planet to report its position in 22-second intervals. He then prints out the data without looking at them, locks the printout in a drawer, and calculates the same data from the scratch, using the space station’s main computer. “If even the figures, provided by the satellite, are not real but the product of my deluded mind, they still cannot agree with the other set of calculated data.” – reasons Kelvin. “My brain may be sick, but it could not – under any circumstances – perform the calculations done by the station’s big computer... Therefore – if the figures will agree – then the station’s big computer really exists, and I used it in reality, and not in delirium.” When the calculations are finished, he sees that they agree with the data from the printout to four significant figures. So, beyond reasonable doubt, the space station Solaris is real, with everything bizarre and sinister that happens there. And right after absorbing this shock, Kelvin finds in a drawer another set of calculations, similar to what he just did, obviously made by one of his colleagues who thought of the same reality test.
Of course, this is a magnificent bit of suspense-building, but that is not our reason for discussing it here. Dr Kelvin’s test interests us as a good epistemological argument in favour of “realism”, i.e. of the existence of the outside world, independent of any human conscience and accessible to rational enquiry. It is not surprising that Stanislaw Lem, a writer and thinker with a keen interest in the philosophy of knowledge, has used such an argument. However, it seems that the first to put forward this argument was not Lem, but another popular writer from the last century, Winston Churchill .
To refute his university–educated cousins’ assertions that “nothing has any existence except what we think of it”, he writes:”…happily there is a method, apart altogether of our physical senses, of testing the reality of the sun… astronomers predict by pure reason that a black spot will pass across the sun on a certain day. You… look, and your sense of sight immediately tells you that their calculations are vindicated… We have taken what is called in military map-making ‘a cross-bearing’. We have got independent testimony to the reality of the sun. When my metaphysical friends tell me that the data on which the astronomers made their calculations were necessarily obtained originally through the evidence of their senses, I say ‘No’. They might, in theory at any rate, be obtained by automatic calculating-machines set in motion by the light falling upon them without admixtures of human senses at any stage…”
In all likelihood, Churchill’s contribution to epistemology would now be widely unknown if not for Karl Popper, who gave this argument a prominent place in his book “Objective Knowledge. An Evolutionary Approach” . Let us recall why “realism” is so important to the philosophical foundations of science, and what the Gedankenexperiments of Churchill and Lem have to do with the scientific method.
The aim of science is to gain rational and objective knowledge about the outside world. It was the Ancient Greeks who realized that rationality and objectivity are closely interrelated. Suppose A makes to B a statement, which concerns something not immediately accessible to B’s inspection or test (for example, “The Thracian swords are better than the Egyptian ones” or “A solar eclipse is just the Moon blocking the Sun”). Since B does not have a direct access to A’s memories, impressions, and other internal workings of his mind, a rational argument is the only way A can prove to B the truth of his statement. It is thus the only general method by which the objectivity of a statement can be established. The central question is: what rational arguments can establish the truth of such a statement, and in what sense. Any such argument relies on an explicitly or implicitly agreed upon set of some basic assumptions (e.g., that a black spot seen crossing the solar disk is actually the image of the solar spot). Such assumptions can be quite deeply hidden and render scientific observations highly theoryladen. But they can be taken care of systematically – e.g., Mr Churchill could make reasonably sure that the visible spot is not the shadow of a bug crawling across the lens. On the other hand, he would have an impossible task proving logically that what he sees is not a delusion – and a confirmation from other witnesses would not help, since they could be imaginary as well. The same argument, by the way, would invalidate Dr Kelvin’s reasoning, since he could well just imagine that the two rows of numbers actually agree.
We shall not consider here this matter of mental delusions (or the logical invincibility of solipsism), which belongs to the fields of medicine and psychology. We will agree then that – in principle – any argument can be reduced to the point when one needs only to look at something – a solar spot, a set of numbers, a formula – to be convinced of its truth or falsity. This “Churchill-Lem thesis” is, of course, a rather trivial observation: human anatomy and physiology being what they are, vision is the sense, and this greatly influences our thinking, speech and behaviour (with the notable exception of St Thomas the Apostle, who put his faith in the sense of touch). Nevertheless, whether this is just a figure of speech or not, recent advances in experimental technology put us in a situation where the question of whether “seeing” can be “believing” (and if yes, believing in what) becomes one of more than speculative interest.
We refer here to quantum metamaterials  – a recent offshoot of quantum computing research. The effort to produce a universal quantum computer over the last 15 years has not yet succeeded in creating one, due to serious technological obstacles. However, some kind of a quantum computing device, containing hundreds of quantum bits (qubits) was realized , even though the question of the degree of its “quantumness” remains open . This is just one example of the field’s enormous progress, especially in the area of superconducting qubits.
Let us make a necessary digression. The expected power of a quantum computer critically depends on its being comprised of qubits. A qubit is, in principle, any controllable system which can be simultaneously in two different states (a quantum superposition of states). Quantum particles, such as electrons, photons or atoms, can do this trick regularly, but are rather difficult to control. Photons, for example, can be relied upon to stay in such superpositions for long durations (on the relevant scale, of course) because they do not interact much with anything else and, besides, have zero mass. This is why a number of key experiments testing the limits of quantum mechanics have been carried out with photons [7-9] and why photon-based quantum communications – like safe key distribution – are already widely used . On the other hand, quantum computing would require qubits interacting with each other, which for photons is inherently difficult. Therefore other kinds of qubits have been developed – including those based on superconductors (e.g., aluminium or niobium).
There are different varieties of superconducting qubits. The easiest to explain (and, incidentally, the one used both in currently realized quantum computing devices  and in quantum metamaterial prototypes  is a superconducting loop, approximately ten microns in diameter, interrupted by three or more very thin insulating layers, which form so called Josephson junctions. The loop is threaded by a finely calibrated magnetic field and cooled down to just 0.01-0.04 degrees above the absolute zero. In this situation, the electric current will eternally flow around the loop (because it is a superconductor). Moreover, for a short, but quite significant time, now running into tens of microseconds, such a current can flow both clockwise and counter clockwise simultaneously. This latter property is what makes such a loop a qubit (a flux qubit, to be more specific).
Over the past decade, experiments involving flux qubits (and other types of qubits as well), where they are prepared in quantum superpositions of states, have become routine . Nevertheless this is far from a trivial phenomenon. Indeed, in mid-80s the very possibility of observing such effects in superconducting devices was very much doubted . The reason was simple: unlike a photon, an electron or an atom, a qubit is a macroscopic object. Nevertheless, not one experiment to-date involving superconducting qubits has cast any doubt on the validity of the laws of quantum mechanics – so for all we know, they may well apply in macroscopic situations no worse than they do in the microscopic world. And this is a scary thought indeed.
The scariness is due to a longstanding fundamental discord between the rules of classical and quantum physics, and particularly the fact that in classical physics, which we still take to apply in macroscopic settings, no object can ever be in a superposition of states. Since these things can only be observed indirectly (e.g., as they influence the needle of an ammeter, or when a mark is left by an electron in a photographic emulsion), all we know about the behaviour of microscopic objects so far has been extracted from measurements – i.e. from their interactions with measuring devices. A quantum object in a superposition of states, say A and B, is described by the wave function; and in the process of measurement (or rather, when it interacts with any appropriate macroscopic object) it turns out to be in either A or B – i.e. the needle will point at A or B; the dark spot on the emulsion will be at the position A or B. The long-prevalent Copenhagen interpretation of quantum mechanics could sweep this – possibly instantaneous – collapse of the wave function under the rug, exactly because the only objects capable of being in a quantum superposition of states were not directly observable.
The famous Schrödinger’s cat paradox , a Gedankenexperiment in which a live cat could be – and, by laws of quantum mechanics, should be – in such a superposition, is a reductio ad absurdum argument against the applicability of quantum mechanics to macroscopic objects. While it could not be refuted (assuming the validity of both quantum mechanics and our everyday macroscopic experience) it was swept under the same Copenhagen rug because of the practical impossibility at the time, of producing such a cat. It was possible to speculate, even, that for large enough objects there will be tiny corrections to quantum mechanics, which make it smoothly transform into classical mechanics as the size of an object grows, with no paradoxes attached.
Now, we no longer have such luxury. The objects we’re able to prepare in quantum superpositions get larger and larger (and are not limited to qubits [14,15], as experimentalists improve their ability to control the processes which disrupt these superpositions. Still, there is no indication that the laws of quantum mechanics should be limited to any particular scale. Perhaps, then, soon enough one will be able to see such objects. The question is, if so, what shall we see?
This is where quantum metamaterials may have a central role. These objects, theoretically proposed several years ago , are periodic structures built of qubits much as crystals are built of atoms. The twist is that the quantum superposed states of these qubits (“artificial atoms”) should be controllable and, most importantly, maintain quantum coherence long enough for an electromagnetic signal to pass through. From the point of view of light (or microwave) propagation, such a system is a real Schrödinger’s cat, which can be directly seen because its optical properties – such as the refractive index, which characterizes the speed of light in the material – can be made directly dependent on the quantum state of its constituent qubits .
And here we come to the critical point. It is theoretically possible to put a piece of quantum metamaterial in a superposition of states with different refractive indices, nA and nB. We could then send a light pulse through it towards a detector. This light pulse can be macroscopic (containing many photons), but for simplicity we may consider only two identical photons. These could be produced simultaneously by the process of parametric down-conversion (a standard quantum optical technique), with one sent directly to the detector, and the other, after a known delay Δt, sent there through the slab of quantum metamaterial.
Let us then consider what happens. When the first photon is detected we will know already when the second one was emitted. We should therefore expect the arrival of the second photon at the moment if the slab is in state A, and at if it was in state B. Here, c is the speed of light in vacuum, L is the length of the quantum metamaterial slab, and D the distance from the slab to the detector. If nA < nb, then tA < tb. Therefore, if the photon is detected at the moment tA, this means that the metamaterial is certainly in state A: its superposition wave function collapsed. So far, nothing strange has happened: the collapse was caused by the interaction of our system (via the photon intermediary) with the detector, which measured its state. But what if the photon was not detected at tA? If – as we are entitled to do in a Gedankenexperiment – we exclude the possibility that it was lost along the way (absorbed or leaked out) or not detected because of the imperfection of our instruments, then we must conclude that at this moment the slab’s wave function collapsed into the state B. But what caused the collapse? There was no interaction with a detector – no measurement – until a later moment tB, which anyway just confirmed what we already knew about the state of the metamaterial at an earlier moment of time. This is indeed a strange case of zero-measurement, when not observing something seems to make a material difference.
We could further investigate the situation and, e.g., take into account that our slab does not need to undergo a collapse all at once: if it is thick enough, then when the photon “A” should be detected, the photon “B” would be still inside. Therefore, non-detection at the moment tA would mean the collapse for only the part of the slab that the photon “B” had time to travel through, with the rest still in a superposition of states. Repeating this leads to a pretty intricate pattern of photon (non)detection, but for us the simplest case, described in the previous paragraph, would be enough.
In summary, if a quantum metamaterial is realised, it appears that it can be used to demonstrate that the collapse of the wave function of a macroscopic object can be achieved prior to its interaction with a detector. Such a demonstration, it seems, would undermine the currently dominant interpretation of collapse due to interactions which wipe out quantum correlations (i.e., serving as sources of decoherence). This would probably be the first instance in which an interpretation of quantum mechanical formalism could be dismissed (or confirmed) by an experiment.
Where does it leave us with respect to “reality”? Hopefully, we will be able to say something new about the nature of the objects we’ve longsuffered to discern from the shadows in Plato’s cave. Not only might it turn out that a single object can cast several shadows, but perhaps we can learn to anticipate certain shadows by observing their neighbours before they show up on the wall. And maybe we’ll see that we should pay more attention to the structure of the wall itself.
In a way, everyone would have an answer to the title of this section. Most people know that computation has something to do with sequences of zeros and ones which encode information, and which are moved around and transformed inside computers in order to obtain desired effects, such as an answer to a specific query. People also know that this kind of information processing relies on what is known as programs, which tell computers what to do with the data they hold in memory.
And yet, computing as we know it today was not always there; it had to be invented. Perhaps the idea that much of computation is mechanical is the oldest part of the long legacy of thinkers who eventually gave us computers. A discussion of the pursuit of mechanization of calculation would take us on a long journey through post-Newtonian science and mathematics, perhaps culminating with a bold attempt by an Englishman, George Babbage, to build a programmable calculator using Victorian technology. But this is not what our present inquiry is about. Rather, we wish to highlight those thinkers who drove back the bounds of calculability and, eventually, computability, opening up new landscapes to enquiry that were not previously imagined. After all, computing as we know it today is not about number crunching only. Indeed, modern computing encroaches upon all human activities at all times. We use computers to seek, retain, process and interpret information; to sort and organize it; to search for patterns; and, in these ways, to generate new knowledge. Computers have long since surpassed the naiveté of simple calculating machines. At some point, people realized that more was going to be possible. It is our thesis that this may have been an even greater leap of knowledge and understanding than the basic concept of mechanizing calculations.
In order to better understand the prospects, the significance and the potential consequences of the current revolution in computing, let us examine it against its proper historical backdrop. The story we wish to briefly retell, but also consider in new light and re-examine, has very long roots. However, we will jump right into its final phase and consider an intellectual firestorm that was kindled by Bertrand Russell at the beginning of the 20th century. Russell may be considered the father of the mathematical philosophy of mathematics. While mathematicians have been philosophizing about mathematics from times immemorial, few of them took the problem of the foundations of mathematics as a seriously necessary pursuit. It was always tacitly assumed that mathematics is in a sense perfect, that its foundations are unshakable and its structure complete. All mathematical questions, people used to believe, can be answered. Yes, some problems are hard and will take a lot of time and effort to settle – but, no doubt, the solutions are essentially determinable.
To be sure, before Russell mathematicians had worked to establish as firmly as possible the foundations of mathematics. Calculus used to be based on a rather hazy notion of infinitesimals until Karl Weierstrass showed in the 19th century how that could be remedied with an approach based on the rigorous concept of the limit. Infinite collections, or sets, also required a thorough discussion, and that was dished out by another 19th century mathematician, Georg Cantor. David Hilbert, who gave an in depth analysis of these two pursuits in his address to the Westphalian Mathematical Society in 1928 , made the distinction between the potential infinities encountered in calculus and the actual infinities investigated by Cantor – and, what is of some interest in the present context, argued that the actual infinities are non-physical. However, according to the modern understanding of the history of mathematics, Hilbert, the great mathematician that he was, may have been the last of the dinosaurs who believed in the completeness of mathematics. That view was to be challenged and defeated before long, and the seeds of doubt were perhaps first planted by Bertrand Russell when he turned his attention to the works of Gottlob Frege on the foundations of arithmetic.
The history of computing involves a long procession of brilliant mathematicians and philosophers. That alliance between the two old academic professions has recently waned. When I am writing this, a clear memory still lingers in my mind of a clash at a certain university between mathematicians and scientists (camp one) on one side and a lonely and depleted group of philosophers (camp two) on the other, over the admissibility of courses on critical thinking and symbolic logic, traditionally taught by philosophers, towards a college general science requirement. The proponents in camp two had to withdraw defeated as it is now often strongly felt among the members of camp one that such a substitution would be a concession compromising the stringent rigors of science. Back then, in the first half of the twentieth century an alliance between philosophy and mathematics was still going strong. In fact, that alliance proved exceedingly fruitful and effective – it brought us computers as we know them today. Many of the names on the list of people who formed that alliance, both philosophers and mathematicians, will be familiar to most readers. However, the interconnections between them, both intellectual and personal, might be less known, and there were many, spanning quite a tangled web.
Frege left open some questions that would soon inspire Russell, who would collaborate with his advisor, Alfred N. Whitehead, on a monumental quest to find answers. This effort led to significant mathematical results; but also, most importantly, it infused the theme of self-reference in 20th century culture. Central to their analysis was the question of whether we can have a set of all sets that do not contain themselves as an element. There is trouble with the set so defined: if it contains itself, then it does not contain itself; but if it does not contain itself, it does. And yet, Russell observed, such definitions are permitted in Frege’s theory, which makes it faulty. How do we ban self-reference from a theory, then? Simply by brute force, suggested Russell and Whitehead, who went on to construct what is known as a type theory. From the very beginning, its creators knew that the theory was only an ad hoc solution. It was not perfect, and it could not possibly be the last word on the subject.
Russell’s self-referential antinomies, as they were known, were almost immediately popularized and thus seeped into the broader streams of the 20th century culture. There is a barber in town who shaves all local men who do not shave themselves. Does he shave himself? This type of construction took root like an addictive weed and made circles through the arts: from Magritte’s famous “this is not a pipe”, through some of the best graphics of Escher, and now in modern movies like Robert Altman’s “The Player”, and TV shows, such as Tina Fey’s “30 Rock”. Some forms of self-reference in theatre, such as the aside, have much longer roots – e.g. Shakespeare himself used this dramatic device, in which the main protagonist transcends the stage reality and addresses the audience directly, in a number of plays, including Richard III, Macbeth and Hamlet. The same trick has been used in both the original BBC version of “House of Cards” and in the more recent version produced by Netflix. In short, self-reference is so dazzling to the mind that everybody likes to play with it. It is not even that rare to find self-reference around us, nor too difficult to deliberately play on the theme.
This discovery of the simple and yet poignant paradox of selfreference captured the imaginations of some rigorous thinkers as well. Among them, Ludwig Wittgenstein and Kurt Gödel – the former, destined to change the landscape and style of philosophizing, and the latter, to make some exquisitely profound observations about the nature of mathematics. The influence of the new pursuit spread through the academe like wildfire. And that fire was responsible for the initiation of the Vienna Circle, the subsequent rise of analytic philosophy, and perhaps also its ultimate defeat beneath the vengeful plume of Karl Popper. Among the acolytes of the Vienna circle was John von Neumann, a top mathematical mind who would eventually provide the blueprint for a programmable computer which was long considered to be the first ever in the world. Von Neumann was among the first to understand the importance of Gödel’s ideas, and was responsible for bringing Gödel to Princeton and for bringing his ideas to the broader mathematical community. In turn, Gödel’s ideas were developed in the direction of computability by Alonzo Church. Alan Turing, who conceived similar ideas on computability independently, would soon thereafter write his PhD dissertation at Princeton, formally under Church’s supervision.
Turing’s immensely important work found a field of application in cryptography, and fuelled the major war effort that was undertaken by men and women at Bletchley Park. In fact, there in Bletchley, the first semi-programmable computing device, COLOSSUS, was built under the supervision of Turing’s old benefactor, Newman . COLOSSUS beat von Neumann’s ENNIAC to the claim of being the first computer by just a couple of years, yet it was kept in such secrecy that the world would only learn about it in very recent years. Turing, Newman and others found additional inspiration in the pre-existing practical results of Marian Rejewski and his colleagues Jerzy Rózycki and Henryk Zygalski, a trio of Polish cryptographers who had been the first to break into the secrets of the German cypher machine, Enigma. The glory of this extraordinary feat by the Poles would have been greater still, if it were not for the fact that they themselves did not seem to fully acknowledge or even recognize the profoundness of their own work. According to popular lore, Rejewski, in a typically Polish self-deprecating manner, did not think much of the scientific value of his dutiful contribution to the war effort. He is reputed to have kept longing to return to research in “true mathematics”. Turing, on the other hand, perhaps having the benefit of exposure to von Neumann, Gödel and Church in Princeton, knew he had something important going in connection with his mechanical calculations. Today, Church and Turing are lauded for laying the foundations of theoretical computer science – one of whose basic tenets, expressing the essence of commonly held beliefs about the nature of classical computation, is known as the Church-Turing thesis.
So far, we have left on the fringes the influence of the famed Vienna Circle – a philosophy club founded by Moritz Schlick in 1924, which came to an end with his assassination in 1932. Although it was a very elitist, by invitation only club, The Vienna Circle held in its folds a number of prominent thinkers; e.g. Hans Hahn (known to mathematicians for the co-authorship of the Hahn-Banach theorem), Otto Neurath (whose work in economics influenced a reactionary thought process in the great Friedrich Hayek). The Circle treated Russell, along with Ernst Mach and Albert Einstein, as patron saints, and worshipped Wittgenstein as a prophetic figure, taking his work as its main influence . It admitted notable guests, such as Gödel and von Neumann, but also resisted extending an invitation to some bitterly disappointed aspirants, most famously Karl Popper. The Circle’s many close or remote acolytes would become a powerhouse in 20th century science and humanities, with visible presence in the faculties of prominent American universities. Among those anointed by the Circle were, e.g., Willard Quine, one of the superstars of 20th century American philosophy, the long list of whose doctoral students at Harvard includes such names as Hilary Putnam and David Lewis, and the Polish logician, mathematician and philosopher, Alfred Tarski, who taught at UC Berkeley.
The intellectual connections and influences between the multitude of the Circle’s thinkers were often complex and should not be oversimplified. Wittgenstein tolerated being worshipped by many in the circle, most prominently Schlick himself, but accused them of misunderstanding him. This was not unusual of him, however, as he is known to have made the same accusation of his long-time patron and former teacher, Russell. The Circle’s program was strictly positivist. In brief, they believed that what cannot be stated scientifically is just a mystical babble that is not worth your while. While Wittgenstein famously said “Whereof one cannot speak thereof one must be silent” which expressed limitations of the scientific method, he did not mean to condemn all that is outside the reach of science. For some of us, the poems of St John of the Cross are meaningful although no one is likely to search for their scientific foundations. That was all right with Wittgenstein: perhaps he even thought those particular poems were meaningful, although we are not in possession of any proof of that. In fact, it is believed he tended to think that precisely the things that transcend science are the most important ones. That went against the grain of the core beliefs cultivated at the Circle.
he importance of Wittgenstein for the future development of computing is fleetingly intangible, but nevertheless potentially important. The emphasis on the limitations of science, the belief that there may be truths unreachable to rigorous axiomatic thinking, was the most important and most novel intuition of that era. The idea reverberates strongly in the profound results of Gödel showing incompleteness of any axiomatic theory rich enough to encompass arithmetic. We know that later on Turing was briefly interested in Wittgenstein’s views, although this interest faded after they met. Nevertheless, the intuition of transcendental truths takes on an independent life yet again in Turing’s results on incomputable numbers.
Rebecca Goldstein, in her masterful biography of Gödel , identifies his lifelong philosophical views as essentially Platonic. That might mean that even before he found his famous proof of incompleteness he already believed that there may be mathematical statements that are true and yet impregnable to “classical” proof via an axiomatic method. Gödel’s later essays, e.g. the remarkably approachable while in-depth article on the Cantor’s continuum problem , confirm his essentially Platonic views of mathematics. Now, Gödel’s most famous result, the Incompleteness Theorem, is crucial to the history of computing. In its proof he encoded all statements of an axiomatic system in numbers. This blazed the trail to computer programming, by showing how all information may be quite naturally encoded and processed on a number crunching machine. This was as crucial a precondition for the later development of computers as the inventions of the vacuum tube and the semi-conductor based transistor. It is, however, much harder to grasp, and impossible to put on display in a museum – hence the fact will likely remain less widely known.
A particularly painful downside of such a state-of-affairs is that we are not properly paying our debts to philosophy, and we routinely tend to forget about its once powerful hold on our culture. This may be detrimental to future revolutions in computer science and technology – e.g. the one we are hoping to witness soon with the advent of quantum calculating machines.
The Vienna Circle had a clear presence in the history, though not in the immediate derivation, of Gödel’s theorem. In particular, together with the Berlin Circle (among whose ranks were Hans Reichenbach, C. G. Hempel and David Hilbert) it co-organized a conference on “Epistemology of the Exact Sciences” in Königsberg, in October, 1930. There gathered under one roof many intellectual celebrities who shared an interest in the foundations of mathematics. In rough terms, the participants’ views were coalescing around four main streams :
• Logicism, represented by Gödel’s senior colleague from Vienna, Rudolf Carnap. The main position of this stream was that all mathematics should be reducible to formal logic.
• Intuitionism represented by Arend Heyting, a Dutch colleague of the stream’s main figure Luitzen Brouwer who did not attend the conference. This stream is best known for its opposition to the validity of non-constructive proofs in mathematics.
• Formalism, proposed by Hilbert and in his absence represented at the conference by John von Neumann. Formalists believed that mathematics is a complete self-contained game and could in essence be mechanized. Hilbert famously stated “tercium non datur” to indicate that all in mathematics is either true or not, and had little doubt at the time that all mathematical truths were obtainable through a straightforward, if sometimes mundane, a process.
• Wittgenstein’s standpoint, represented by Friedrich Waismann. Wittgenstein, consistent with his belief that there are no real philosophical problems, only puzzles, interpreted mathematics in the spirit of language games. To him, mathematical statements acquired meaning from the way they were used by mathematicians engaging in the game.
However, as brought to light by Goldstein, an odd and boyish bystander Gödel did not follow any of the above creeds. And that is indeed how it must have been, as he already had the proof of his Incompleteness Theorem in-hand. He announced it briefly at the conference during the day reserved for informal discussions. His understated message hardly reverberated and was largely ignored. It seems that even his Vienna colleague Carnap and his thesis advisor Hahn remained mute on the subject. Von Neumann, however, grasped its significance immediately, probably obsessed about it, and eventually, a few years later, brought Gödel to Princeton. Gödel speculated about the reach of his discovery very broadly, as was his right. Already in Königsberg, he expressed a suspicion that some of the classical problems of mathematics might be unreachable to proof. In particular, he so implicated Fermat’s Last Theorem. Today, with Andrew Wiles’ 1993-95 proof of that famous conjecture already part of the mathematical canon, we know Gödel was actually wrong about that.
Regardless of such speculations that were eventually falsified, it was really through the method Gödel employed that his proof turned out to be so significant to the future invention of universal computers. What Gödel proved was a statement about sufficiently rich axiomatic systems: If a theory is consistent, i.e. no statement could be both proved and disproved, then it is incomplete, i.e. there will be statements that cannot be deduced from the axioms. The core idea of the proof was to express as an arithmetical statement the sentence “This very sentence cannot be proved.” This is again a self-referential statement of the form that was brought to light by Russell. Now, if this statement could be proven in an axiomatic system, then it would be both true and false. Hence, the system would be inconsistent. In order to carry out the technical side of the proof, Gödel invented a method for encoding all of the statements of a given axiomatic system in numbers. That shows the necessity of the a priori assumption that the system must be rich enough to contain arithmetic. Arguably, this was the first fully successful translation of a nontrivial body of knowledge that is an axiomatic theory into a mechanizable number code. It was also perhaps the first inkling of the concept of universal computing, i.e. computing that goes beyond superficial calculation.
A possible conclusion is that computing as we know it is not a mere ad hoc invention tied to an electronic technology. In that regard, it is completely different than, say, television – the latter being a very complex invention, which has nevertheless arisen from natural needs and curiosity on one hand, and an enabling technology on the other. In particular, we know exactly how to envision the next generation of televisions: the pictures will be three-dimensional – a technology that we have only just begun to develop, which may someday turn out as we’ve envisioned in Sci-Fi shows with holographic figures popping out of a box. Computing, on the other hand, is really very different in that we do not know what it is going to become – nor do we know whether it can be essentially different, rather than simply faster and more reliable, in the future. But computing is also conceptually tied to a culture; a way of viewing what is and what is possible. It is therefore perhaps most important to note that computing remains tied to familiar mathematical realities . The current computing paradigm, encapsulated in the Church-Turing thesis, is classical in the sense that it is tied to an approach to mathematics that is based on a system of classical-logic based deductions. Does this mean that the next computing paradigm can only emerge after completely reinventing our view of mathematics, or even developing a completely new way of doing mathematics? In such a case, is quantum computing going to be essentially different? If so, then this time the paradigm shift would not have come from a conspiracy of mathematicians and philosophers, but rather would be an operation run entirely from physics departments with some admixture of hastily reformed computer science departments.
However, it ought to be mentioned that the current pursuit of a novel computational paradigm is based on entirely different principles. It is assumed that we already know what computation can give us, and we have certain expectations. There are computational problems that we consider important, or at least extremely alluring, such as the Travelling Salesman Problem or integer factorization, which nevertheless appear to pose immense challenges to today’s methods – viz. they do not seem to be computable in real time. If anyone can find a physical process that will yield a real time solution to any one of those problems, it will indeed be a gigantic breakthrough. It is also quite likely that such a discovery would release an avalanche of new mathematical ideas. For, just as the old computational paradigm is closely connected with today’s style of doing mathematics, that new way of computing would give birth to post-classical mathematics.
As mentioned above, from one point of view Gödel’s proof of incompleteness translates a classical mathematical theory into a classical computer program. In that framework, theorems are obtained from axioms via chains of deductions, and deductions follow certain rigid rules. In that sense, the proofs of theorems are matters of construction. Now, if a new computational paradigm broke out, we would gain a new notion of construction. A construction would be equivalent to having information encoded in a way that is specific to that new approach, and then having it processed in that specific new way. The new notion of construction would effectively be a new, post- Church-Turingian, notion of computability. That in turn would yield a new notion of provability and a new understanding of completeness. A new Gödel’s theorem would have to be proven, but it would naturally spring right out of the new concept of computability. We would gain a new insight into what mathematical truth is, and a new understanding of what truth is in general. There would be a pressing need to build new philosophical foundations. In particular, as a first order of the day, we would have to reconstruct Platonism completely anew, as now Plato’s cave and what is outside of it would be seen in a completely new light. There is a chance, although it may be too much to hope for, that we would in fact find ourselves outside of Plato’s cave, for once endowed with full vision of things as they truly are.
There is no a priori reason known to us why the scenario described above should be impossible. Perhaps the philosophical limitations on knowledge that are implicated in Gödel’s theorem are in reality just technical ones and as such can be transcended. At this stage, we can do two things: 1. Keep up the search for a physical process that will break through the complexity barrier of problems that cannot be classically computed in real time, and 2. Hold a philosophical discussion trying to understand where this might lead. If there is a moral to the story we have outlined here, it is that we should keep at both.
We are grateful to Dr. Daryl Janzen for a thorough reading of the manuscript and many thoughtful criticisms and suggestions.
1This is arguably the best novel by the best science-fiction writer of the last century, and is well worth reading–especially because the novel has virtually nothing in common with the two movies based on it (one classic and one Hollywood).
Make the best use of Scientific Research and information from our 700 + peer reviewed, Open Access Journals