00 185 Now, a very clever or annoying student asks, “What happens if an infinite number of infinitely large buses arrive at the hotel. Can they all fit in?” The mathematical question is “does infinity times infinity, equal infinity?” Let us ask all the guests to get out of the bus and line up in the parking lot in neat rows. Passengers from bus one in line 1, those from bus 2 in line 2, and so on. All the guests now form a two-dimensional grid. We already know how to map a two-dimensional grid to one- dimension using the zigzag method. We can fit them all in the hotel and we are done! Is Anything Larger than Infinity? Is there any bus or combination of buses that would cause the manager of Hilbert’s Hotel a problem. The answer is yes and it involves a subtle change to the contents of the bus. An infinite number of buses turn up but this time the buses are filled with men and women. The hotel manager is asked to put everyone in a room and once again he obliges using the zigzag method. At the end of the process the tour guide comes to him. “I think you have missed some people,’ he says. “Since I am just one person, I know you can fit me in. But, I have a whole bus in the car park you completely missed.” “No,” says the manager. “I did every bus.” Infinity Plus Infinity Equals Infinity HOUSE_OVERSIGHT_015875

186 Are the Androids Dreaming Yet? “Ah, no,” says the tour guide. “The first bus you accommodated had a man in the first seat but this has a woman. The second bus had a woman in the second seat but this one has a man and so on. This bus has a different gender in at least one seat to every bus you so far accommodated. It is a new bus.” The manager finds room for the passengers from the new bus but the tour guide comes back a moment later. “You have missed another bus. This one has a different gender in at least one seat to every previous bus, including the one you just accommodated. It looks like there are an infinite number of buses you missed, all lined up to get into the infinite hotel.” What is it about these buses that make them so difficult to accommodate? They are all just filled with people after all. The manager is defeated by the more complex information held in the contents of the buses. An infinitely large bus full of binary information has more information in it than an infinitely large bus specified only by its size. This is a larger infinity than the counting infinity. The permutation of all the possible options for the occupants of the bus is larger than infinity. Real Numbers What about the real world we live in? Is the larger infinity we failed to fit into Hilbert’s Hotel present, or was it just a mathematical fiction? Hold up your thumb and index finger for a moment. The gap between them is a distance. Most likely this is a whole number with an infinite decimal digits after it — say 2.2320394386.... centimeters. The infinite set of decimal digits in this measurement is the larger type of infinity: called the continuum. Distances in space form a continuous unbroken line of points, with no gaps in between. The counting numbers, on the other hand, form a broken line. We take discrete steps from one number to the next. This is a hard distinction to grasp but it is the same distinction we used in Hilbert’s Hotel. Imagine you believe you have a list of all the real numbers in the world. You can take the first decimal digit from the first number and add one, the second digit from the second number add one and so on generating new numbers not on the original list. Therefore, you cannot have a list all the real numbers; they are not countable. Let’s take a closer look at these real numbers. Here’s a quick test. Which is the larger number, the first or the second? HOUSE_OVERSIGHT_015876

7 . Holding a Real Number in your Hand First: 3.1233249837583462136421472374 Second: 3.1233249837583462 134421472374 You have 2 seconds to answer! TRY ANSWERING WITHOUT READING ON The first is larger. I changed one digit. Can you see? Notice, you need time to read each digit and process the information. If you were an obedient reader and attempted it in two seconds you either guessed or gave up. Two seconds is too short to take in all the digits. Let me give you another test. Again, I'll ask you the question, “Is the first number larger than the second?” First 3.1233249837583462 1364214723751646464646464636... Second 3.12332498375834621364214723751646464646464636... HOUSE_OVERSIGHT_015877

188 Are the Androids Dreaming Yet? I know you're looking for the difference but you wont find one, as I did not have time to write the numbers out in full. The 107°" digit is different, but even if I took the whole age of the universe and counted as fast as possible I would not reach this digit. Any number greater than, 10'”°/10 digits cannot be distinguished from another in the age of the observable universe. Real numbers are in practice subject to an uncertainty principle. Some mathematicians even wonder whether they really exist. But, they do exist in our minds and our thought experiments. In my view, any model of the Universe that ignores them is likely to be wrong. Random Numbers Which of the following numbers is random? LILLIA 34289460370124001 49293741762343083 THINK ABOUT YOUR ANSWER THEN READ ON Each of the numbers could be random. There is no reason any set of 10 digits is more likely than another, but it feels very unlikely that if I tried to generate a random number I would get 15 consecutive digits. What a human means by random is a jumbled up number: one with varying digits that have no real pattern. An American mathematician, George Chaitin has been able to explain this by saying that a random number is uncompressible. This means there is no way to describe the number more efficiently than writing it out in full. A string of ones can be compressed. “Write a million 1s” takes only 18 characters, yet accurately describes a number that is a million digits long. By contrast 8988376132 can't be compressed very much at all, its information is just a jumble. There are many interesting numbers around. Some numbers are Hamlet; some numbers are pi. One interesting number is the following: 17733173332032037377. It is the genetic sequence for the virus smallpox, or at least the first 20 digits. Copies of the full sequence sit under lock and key in the Pasteur Institute in France and the CDC in Atlanta. This number is a candidate for an ‘evil’ number. You might think there are many numbers that could represent smallpox because there are HOUSE_OVERSIGHT_015878

00 189 Smallpox Virus many languages in the world and many ways you could code the genetic sequence of GATC. But, there will be one most efficient binary coding for smallpox and that number is the nearest we have to an evil number. The other important element of random numbers is the process by which they are created. Computers can’t genuinely generate random numbers. The numbers they generate are predictable and eventually . * Child Survivor of Small Pox HOUSE_OVERSIGHT_015879

190 Are the Androids Dreaming Yet? repeat. To create the random number in my example above I went to www. random.org, a website that uses fluctuations in atmospheric quantum noise to generate random numbers. As far as we know quantum effects are truly random and have neither rhyme nor reason. Numbers are more complex than they first appear. They are infinite, yet there are different infinities, and they have meaning. The smallpox example above and the Turing numbers we will discover shortly suggest numbers do have meaning independent of culture and language. The next two chapters will show us what happens when we think about the meaning of numbers. We will also explain one more ‘super infinity’ and this will be the key to understanding creativity. “There are known knowns; there are things we know we know. We also know there are known unknowns; that is to say we know there are some things we do not know. But there are also unknown unknowns - the ones we dont know we don't know.” Donald Rumsfeld United States Secretary of Defense (2001-2006, 1975-1977) HOUSE_OVERSIGHT_015880

Chapter 9 KNOWN UNKNOWNS Donald Rumsfeld HOUSE_OVERSIGHT_015881

runners included 1200 international athletes and 20,000 amateurs. An estimated 20 million viewers watched from around the world. The top international runners stayed together for the first twenty miles and then two runners, American Dick Beardsley and Norwegian Inge Simonsen, made a push for the finish. They were long-standing rivals and, as they ran the final mile each man challenged the other to see if they could get ahead and gain the advantage. Because of the fine balance human muscles maintain between anaerobic and aerobic metabolism, the small set advantage could prove insurmountable. The other runner would need to sprint to catch up and the resultant lactic acid generated would turn their legs to jelly. As the two runners neared the finish line they glanced at each other, smiled, reached out and held hands as they crossed the line. Who won? We all instinctively know the answer. The race was a draw, but the rules of the International Athletics Federation are clear. Read rule 164. EF the spring of 1981, London staged its first marathon. The field of RULE 164 The Finish 1. The finish of a race shall be denoted by a white line 5 cm wide. 2. The athletes shall be placed in the order in which any part of their bodies (i.e. torso, as distinguished from the head, neck, arms, legs, hands or feet) reaches the vertical plane of the finish line. The organizing committee held a brief conference and the result declared a draw. They had interpreted the rules in the same way 20 million TV viewers already ‘knew’ to be true. This story should set your minds thinking about the nature of rules and truth and how the two are often different. According to the rules, one person crossed the line a little ahead of the other. The truth, as we all instinctively know, is that the race was a draw. Maybe the rulebook is missing a rule — “The contact draw rule. Clearly you could amend the rulebook to add this one rule. I checked the current athletics rules and they don't contain this amendment. If the rules were amended the mis- chievous amongst you will realize an unsporting athlete could grab the hand of their opponent as they crossed the line to force a draw. The rules would have to stipulate that holding hands must be voluntary for both parties, and refinements could go on for some time. What if I held your hand but you tripped and let go? What if my attempt to hold your hand HOUSE_OVERSIGHT_015882

Known Unknowns 193 caused you to trip? You could go on forever, generating rules to cover every eventuality. Clearly, in the fuzzy world of human endeavor, truth and rules often part company. Yet, we all assume math- ematics is free of such uncertainty. Let me tell you this is not so. The brilliant mathematician Kurt Gédel proved see eee this when he was just 22, and his proof a es says something fundamental about the 4 rs /, : nature of knowledge. a has The story of his discovery involves some of the greatest mathematical thinkers in history. My introduction to it came about from a chance accident. I became ill in my first year at University (mononucleosis, otherwise know as glandular fever, if youre curious) and was eventu- ally sent home to recover. Lying in bed for two months is boring. So to pass the time my mother suggested I read Bertrand Russell's, The History of Western Philosophy. | think she figured I had plenty of time, so picked a thick book. This nearly 800-page tome charts the entire history of philosophy from the time of the ancient Greeks. I presumed Russell was a philosophy professor, but he was originally a mathematician. He was a mathematician. And because he lived and worked productively for almost all of his 97 years, spanning much of the 19" and 20" centuries, he crops up repeatedly as a central figure in many areas of intellectual life. Russell the politician, Russell the philosopher, Russell the mathematician and Russell the peace campaigner are all the same man — not, as I had incorrectly first guessed, a prolific family. In his early career, Bertrand Russell was a Fellow of Trinity College, Cambridge, working on a broad range of mathematical problems. Meanwhile, in Germany, his contem- porary David Hilbert, also a polymath, held the chair of mathematics at Gottingen University. Both men shared a common objective: to tidy up the loose ends in mathematics and set down the rules once and for all. This movement was called Formalism. Kurt Gédel Formalism David Hilbert and Bertrand Russell believed you should be able to set out all the rules of mathematics even though it might be a complicated affair. Without contradiction or inconsistency you should be able to HOUSE_OVERSIGHT_015883

194 Are the Androids Dreaming Yet? write down the rules and then play the ‘game of mathematics’ to derive every possible truth. Hilbert despised the idea that there could be unknowable things and was a forthright speaker. His battle cry was: Wir miissen wissen — wir werden wissen! “We must know — we will know!” He believed there were no fundamental unknowns in the world. Donald Rumsfeld famously summed up the problem of unknowns in an attempt to clarify a question from a journalist at a Whitehouse press conference: “There are known knowns; there are things we know we know. We also know there are known unknowns; that is to say we know there are some things we do not know. But there are also unknown unknowns — the ones we don’t know we don’t know.” Interestingly Donald Rumsfeld, like Bertrand Russell, is another person to span a huge swath of time in the public eye. He was both the youngest and the oldest serving U.S. Secretary of Defense, serving under both Richard Nixon and George W. Bush. We will shortly discover Rumsfeld’s convoluted view of the world turns out to be closer to the truth than Hilbert’s tidy mathematical aspiration. As well as believing there were no unknowable unknowns Hilbert thought mathematics was completely abstract. You did not need to know what you were talking about. Whether the symbols meant dogs, cats or numbers all you needed to do was apply the rules and all would be well. His belief is captured in his quote below. “Tt must be possible to replace in all geometric statements the words point, line, plane by table, chair, beer mug” David Hilbert Geometry with Beer and Furniture HOUSE_OVERSIGHT_015884

Known Unknowns 195 Newton's Principia PM In 1890, the Cambridge mathematicians Alfred North Whitehead and Bertrand Russell embarked on the mammoth task of writing out all the rules of mathematics and publishing them ina set of books called Principia Mathematica. Every rule is written down in meticulous detail. The books are heavy going and look like more like computer programs than text. They set out precisely what you can, and cannot, do with numbers, and are the most impenetrable textbook you will ever read. Just to give you a flavor here is one line where Russell proves 1+1=2. It has taken about 100 pages of densely packed equations to get to this point! #5443. F:.a,del. Dian B=A.=.avBe2 From this proposition it will follow, when arithmetical addition has been detined, that 1+1= 2. One Plus One Equals Two, PM PM is a 3-volume set of books. Volume One costs £480 on Amazon. This is a significant work and a collector's item. The last time a first edition volume came up at auction in 2007 it went for over £800. Cambridge University Press printed only 750 copies and I suspect they HOUSE_OVERSIGHT_015885

196 Are the Androids Dreaming Yet? Look inside 2- Principia Mathematica 3 Volume Set (v. 1-3) Principia Mathematica Amazon Listing for Principia Mathematica are undervalued. When mathematicians use the letters ‘PM’, they are usually referring to Russell and Whitehead’s Principia Mathematica rather than the afternoon. Hilbert’s Problems In 1900, while Russell and Whitehead were in full flow writing out their rules, David Hilbert was invited to deliver the annual lecture at the International Congress of Mathematicians in Paris. He asked a mathematician friend what subject he should pick for the talk and, in a moment of inspiration, the friend suggested laying out a vision for the future of mathematics. Rather than tell people how wonderful mathematicians were, and why their discipline was the pinnacle of human scientific endeavor, why not try modesty and list all the problems on which they were stumped? Hilbert liked the idea and devoted his talk to all the problems he thought mathematicians would solve in the 20" century. Hilbert’s Problems were simply an intellectual challenge. He offered no prizes. At the turn of the 21* century, the Clay Institute created the Millennium Prizes for solving the most important modern mathematical problems. Each solution wins a prize of a million dollars! There are 23 numbered Hilbert Problems in all: ten in the original lecture and a further 13 in the written transcript. In 1928, he clarified the 2™ and 10" problems, refining them into three distinct questions: Is mathematics consistent, complete and decidable? Ironically this means that Hilbert’s 23 problems actually number 24! The most important Hilbert questions where these last three. They ask whether Russell and Whitehead would be successful — can you write out all the rules of mathematics and then simply calculate the answer to any problem or derive any proof. This is known as the Decision Problem. Can you mechanically decide any mathematical question without doubt? To explain Hilbert’s Problems, I need to define mathematics properly. HOUSE_OVERSIGHT_015886

Giuseppe Peano, Mathematician “A mathematician is a blind man in a dark room looking for a black cat which isnt there.” Charles Darwin HOUSE_OVERSIGHT_015887

The Game of Math ne of my most vivid childhood memories is driving my mother () distraction by asking the ‘why’ question. Most children go through this phase: Me: “Why is a sponge wet?” My mother: “Because it has soaked up water.” Me: “Why has it soaked up water?” My mother: “Because it has small holes in it” Me: “But what makes water wet?” My mother: “Because it is made of wet stuff” a bit weak now. Me: “What is wet stuff?” You can ramble on indefinitely unpeeling a never-ending onion. Sometimes, if you are unlucky, you may get stuck in a loop. For example, “where did the chicken come from?” “An egg, “and where did the egg come from?”.. Mathematics breaks this cycle! In mathematics, there is no danger of an infinite number of ‘why’ questions because at its core are a clearly defined set of absolute rules called axioms. You cannot ask the ‘why’ question of an axiom. It is a RULE! Starting from an absolute minimum of fundamental rules everything else is built up so that no step requires any leap of faith nor generates any contradiction. Let me give you a concrete example and, in the process, show you how numbers are defined. HOUSE_OVERSIGHT_015888

Known Unknowns 199 Numbers It was not until the late 18" century that numbers were properly codified. The mathematician Giuseppe Peano gave us the rules, so they are called Peano axioms. Here are his ‘axioms’ in natural language. Peano Axioms 1. The first number is named zero. 2. Every number hasa next number (called its successor). Example: the next number after one is two. 3. Numbers are singular. Every number with the same name is the same thing. 4. If something is true of a number, it should be true of the next number (the successor number). From this we can prove some very simple things. 1+1=2. Because the next number after 1 is 2 and ‘+1’ means take the successor. (You can see J cheated here a little and did not take 100 pages for the proof.) Back to my poor mother: “Why is the lowest number zero, Mummy?” “Because I say so!” Or, at least “...because Mr. Peano said so.” That’s what an axiom is. “OK, but why is 3 greater than 2”” “Because I said that each number has a thing that comes after it. “But, why can’t 3 come after zero!” “Tt can!” “But then, if 3 is the thing after zero, I could count 0, 3, 2, 4...” “Yes, if you want to...” “Tm sort of lost. Now, you are saying that 3 doesn't really ‘mea’ anything. It just comes after 0” “Yes. You can make up any symbols you like. You just have to remember what you said and be consistent.” The dialogue shows the importance of definition in mathematics. I could define my counting numbers as 0, 1, 2, 3, 4 or as 0, 2, p, 6, ¢, OF = th, {k, 2 or to be really annoying and confusing 0, 3, 1, 2, 4; they are only arbitrary symbols. It helps us to learn the numbers because 1 is a single line, 2 is two lines joined, three is basically three lines looped together, and four is four lines, but we could have used any symbols we cared for. It is the rules for manipulating these symbols that are the important part and give mathematics its meaning. HOUSE_OVERSIGHT_015889

200 Are the Androids Dreaming Yet? The Game of Mathematics When I was a child, our living room carpet had a square pattern. You could use boiled sweets to play checkers on it. Even though there was no board and no pieces, it was clearly a game of checkers because we followed the right rules (with the one exception that if you jumped over a sweet you got to eat it). Mathematics is like a game with a set of rules. If you follow the rules, you are doing mathematics. Consider the simple mathematical theory that if A equals B, then B equals A. This seems clear-cut, but you can get into trouble if you're not careful when defining the word ‘equals. ‘My dog equals naughty’ does not imply ‘naughty equals my dog. Here I have used ‘equals’ to mean ‘has the property of? My dog has the property of being naughty. This is an attribute, not equivalence. You must be careful with mathematics. A equals B implying B equals A is a property of numbers when the equals sign is used to mean equivalence. Here are the rules of the game that provide a proof for this theory. Let us start with the position in which we don’t know whether A equals B implies B equals A. We have these three axioms, call them rules for now since we are using the game analogy. Rule 1: If] have no minus sign in front of a letter I can assume there is an invisible + sign there. Rule 2: If I have a positive letter (or a letter with no symbol in front of it) I can put a minus in front of it and put it on the other side of the equals sign. Rule 3: I can swap the plus and minus signs of all the letters in my equation if I do it to all of them. Now I am ready to prove my theorem. A = Bis the same as +A = + B. (rule 1) +A = + Bis the same as -B = - A (rule 2 done twice) -B = -A is the same as B = A (rule 3) Success. So A= Bis the same as B= A. I have my proof. It might be glaringly obvious, but that’s not the point. The point is you can apply rules to symbols and derive new rules. It does not matter what the symbols are or how obvious it is. Here’s the same proof with dingbats. HOUSE_OVERSIGHT_015890

Known Unknowns 201 Rule 1: If] have no glyph in front of a symbol I can assume there is an invisible Y there. Rule 2: If] have a positive letter (or a letter with no symbol in front of it) I can put a F in front of it and put it on the other side of the > Rule 3: I can swap the ¥ and symbols of all the symbols in my equation if I do it to all of them. The proof in symbols WY > & is the same as ¥ VY > ¥ &. (rule 1) Y VY > & is the same as AS > BY (rule 2 twice) B&> AY is the same as 8 » V (rule 3) Any collection of symbols will do. The symbols have no meaning in themselves other than the meaning we have given them. A tribe in the Amazon jungle could demonstrate a proof without knowing any mathematics. All I need say is, “Hey, I want to play a game with you. Can anyone make this into that, in the fewest possible steps, while obeying these rules?” But, is it true we can ignore the meaning behind the symbols. Does it matter that we were talking of numbers rather than spears, counters, or crocodiles? If we look at the marathon winning analogy again, we know the nature of a game is important. In a running race we can interpret holding hands to mean the two athletes are treated as one, the existing rules can then be applied as normal and the pair become a single winner. But, in tennis, there would be a problem. I wouldn't want to come on court and find I’m playing against two opponents! On consideration though Id be happy if they had to hold hands while they played so that they constituted a single player. When we examine the actual circumstances, we can add a rule and show the rule works, but we have to see something about the specific sport that makes the rule fair and workable. Hilbert was convinced mathematical truth is not like this and that proofs follow from the rulebook without any knowledge of the circumstances, i.e., the sport being played or any other analogous thing. He was to be proven wrong by Kurt Gédel. HOUSE_OVERSIGHT_015891

202 Are the Androids Dreaming Yet? ni NUNGSEKGA Kénigsberg Bridges Gédel Gédel studied mathematics at Konigsberg University, Hilbert’s hometown. Kénigsberg is famous for having a mathematical problem related to the seven bridges that link the city together. It’s quite fun to try to solve. Find a route across the city that crosses each bridge once and once only. You can start anywhere, but no walking halfway over a bridge and no swimming! Euler discovered a rigorous mathematical proof that there can be no solution in 1735 after five hundred years of failure by other mathematicians. The answer is you cannot. In 1931 Kurt Gédel, then working at the University of Vienna, proved mathematics is like our sporting analogy. There are true statements in mathematics that cannot be proven by the rules of the system. Someone outside the system, with common sense, can see a statement is true, but it’s impossible to prove this if you constrain yourself inside the system. It is the equivalent of all the members of the London Marathon Committee wondering what to do about the race while all of us watching the TV are shouting, “It’s a draw!” Looking at the rulebook ‘really hard’ doesn't help. HOUSE_OVERSIGHT_015892

Known Unknowns 203 You have to step back and think about the problem in the round and then devise some additional rules to handle the circumstances. Mathematics is like this also. Here is how Gédel proved his result. It is easy to turn logic or any text into numbers. That’s how this book is stored on my laptop. All we need do is translate sentences into ASCII or Unicode. In this way, any theory can be reduced to a string of numbers. Since Gédel’s proof predates the invention of the computer, he had to come up with a novel way to store information. He deployed an old Roman invention; a substitution code. The number one was represented by 1, two by 2 and the symbols by larger numbers, for example, ‘=’ was coded as 15 and so on. He then raised a sequence of prime numbers to the power of each of these codes and multiplied all the results together. This generated a single enormous but unique number that he could later factor back into its constituent parts to recover the information. This is a truly complicated solution to a very simple problem. Today we would solve it by storing each number in the memory of a computer as an array. Let’s use the easier table method to store things and code as follows: 000 will stand for ‘start of proof’ Each step in the proof will start with 00 and each symbol in the proof starts and ends with a zero. This way we can code one plus one equals two as follows. 0000001110454011101210222000000 I think this is simple enough for you to guess the coding scheme. Hint: 111 stands for 1. The scheme is on my website if you can’t work it out. Using this technique, any series of mathematical statements can be turned into a number. As a series of mathematical statements is a proof, we can generate proof numbers. They are just the sequential list of all the instructions. These numbers are sometimes referred to as Godel numbers. Gédel’s next step was to say one number demonstrates the proof of another number. For example, the number 000820962 might demonstrate the proof of another number 000398... This is the mathematical equivalent of my saying a Word file demonstrates the truth of your mathematical theorem. Any statement can be represented by numbers, provided you have a consistent coding scheme that allows you to get back to the meaning. Now Gédel set up his paradox: HOUSE_OVERSIGHT_015893

204 Are the Androids Dreaming Yet? Every correctly formed theorem number has another number, which demonstrates the proof of that number. If this is universally true there should be no contradiction. Unfortunately if you apply the theorem to itself you get something similar to the liar’s paradox. “This proof number is not a proof of the truth of this theorem number.” The proof number proves the theorem number is true, but the truth of the statement is that it can’t be a proof of the statement... Paradox. The only way to resolve the paradox is to go back one step and realize that not every correctly formed theorem number has a proof number using only the rules of that system. Concisely, Godel’s theorem says, “Within any formal system of mathematics there can be statements that are true but are not provable using only the rules of that system” When Hilbert heard of Gédel’s proof, his first reaction was anger. After all, he had spent 30 years of his life trying to prove mathematics was tidy and complete. Gédel had just shown it was not. Hilbert never worked on formalism again, but the rest of the mathematical establishment largely ignored the result. Godel’s proof did not stop mathematicians proving new theorems nor doing useful mathematics. They went on much as before, using a mixture of intuition and analysis. The only difference was someone had told them analysis alone would not succeed. The repercussions of Gédel’s theory have more to do with understanding our place in the Universe and the nature of knowledge discovery. These are ‘big’ philosophical questions, which don’t greatly affect the day-to- day ability of a mathematician to do their job. However, it is important to understand that knowledge discovery is not simply analysis. Knowing this helps us understand human creativity. Inconsistency In the proof above, I said the only way to resolve the paradox is by saying there cannot be a proof number for every mathematical statement and therefore mathematics is incomplete. There is one other way to solve the paradox, and that is by allowing inconsistency into the system. Gédel’s proof assumes you can prove something true or false, but what if you could prove it true and false? In this case, the system is complete but you can prove truths and untruths within it! This may seem an acceptable solution, but inconsistency in a mathematical model is a cancer that will HOUSE_OVERSIGHT_015894

Known Unknowns 205 spread through the entire body. Think about it. If 1 am allowed to prove anything either way, of course, my system is complete. It can say anything it wants, but the proofs I make are worthless. Let us imagine, for a moment, we created a new system of mathematics where all the numbers in our new theory behave as we expect, except for the numbers 5 and 6. You may use them to count, but they are also equal to each other! This feels bad and it certainly breaks the Peano axioms. In my new system | plus 5 and 0 plus 5 are the same, so I can equate 0 to 1. Because 0 and | are the basis of binary arithmetic, all numbers can be equated. Numbers now have no guaranteed meaning in my system and, what is worse, since logic uses 1 and 0 to represents true and false, all of logic falls apart as well. Whenever we allow inconsistency into mathematics it rapidly brings the whole pack of cards down. The example I gave was glaring; an inconsistency right in the middle of the counting numbers! Maybe I was too aggressive and a subtle and less damaging inconsistency might be tolerable. However, any inconsistency allows me to make zero equal one somewhere in my system and, therefore, any theorem based on proof by counterexample will be suspect. There might be systems where inconsistency could be a legitimate part of a mathematical system, but I would always need positive corroboration for each proof. IfI tried hard enough, I could always prove something either way. I would need to formulate a new mathematical rule — something like “I will believe short, sensible-looking proofs to be right and circuitous proofs to be wrong.” Mathematics would be a bit like a court of law. You would have to weigh up the evidence from a variety of sources and the verdict would be a matter of subjective opinion rather than objective fact. Inconsistency is very bad in mathematics. The Lucas Argument J.R. Lucas of Oxford University believes Gédel’s theorem says something fundamental about the nature of the human mind. In 1959, he wrote a paper, Minds, Machines and Gédel, where he argued humans must be able to think outside a fixed set of formal rules. The paper has been causing arguments ever since. Strong AI proponents have a visceral reaction to it. Forty years later, in 1989 Roger Penrose picked up the baton and put the Lucas argument on a stronger theoretical footing. The Lucas-Penrose argument is this: HOUSE_OVERSIGHT_015895

206 Are the Androids Dreaming Yet? If humans used a formal system to think, they would be limited by the incompleteness theorem and unable to discover new theorems that required them to extend the formal rules. Humans do not appear to have such a limitation and regularly extend their appreciation of mathematics by expanding the rules, and seeing through to the truth. Many scientists dislike this argument and think it farfetched, saying there is no evidence to show people see past the limitation. Our brains could be following a formal system capable of discovering everything we have discovered to date or, indeed, might encounter in the future. Why should we assume human minds are constrained in the same way as the mathematical systems they discover? There is no evidence to suggest a human thinking about Peano arithmetic is running a Peano based model in their head. When Peano discovered his theorem he was certainly extending our mathematical knowledge, but this does not imply he was extending the capability of his brain. The critics of Lucas and Penrose have one big problem to deal with. The formal system in our head would need to be able to see the truth in everything we could ever encounter. But, our formal system appears to be small. As infants, it is almost nonexistent. Where does this enormous system come from? It can’t come from our parents because they have the same problem; they were once children. You might argue that the capability of the human brain is huge and we can learn from all the other humans on earth, but let me remind you what Godel said. However large Two Giants HOUSE_OVERSIGHT_015896

Known Unknowns 207 a system you have and however much you extend it, the system will always be incomplete. And we really do mean; however large. Even an infinitely large formal system would be incomplete. The only way to avoid this problem is with some sort of conspiracy theory where we only come across problems our formal system can already solve. Such a theory is a determined Universe. In a determined Universe, all the mathematical problems we ever solve must be expressed by the formal systems existing in the Universe. We must never encounter a problem where we need to extend the system and break the Gédel limit because we are pre-determined not to do so. The Inconsistency Defense An argument put forward by opponents of the Lucas-Penrose position is that humans are inconsistent formal systems. Inconsistent formal systems are not subject to the incompleteness limit. Humans certainly behave inconsistently with remarkable regularity but simply making inconsistent statements is not sufficient to show the underlying formal system is, itself, inconsistent. Inconsistent beliefs can come simply from making mistakes or reading the same story in two different newspapers! We need a fundamentally inconsistent thinking mechanism inside our brains to break the constraint. The very machinery itself would have to be inconsistent. But this is exactly Penrose’s point. Constructing a machine capable of reasoning in an inconsistent but useful manner would need exotic technology, some sort of non-deterministic, rationalizing computer. The components to make it could not be computer logic as we know it today. All such logic is entirely computationally deterministic. Let me see if I can reframe the Lucas argument. Imagine IBM’s Watson computer was let loose on mathematical reasoning. Watson could scan every mathematical theorem ever written down. It would know every programming language created. It would have its enormous bank of general knowledge to call upon and it could answer many questions. It would sometimes appear inconsistent because the information it had trawled from the Internet would be wrong. But Watson would still be a consistent formal system and Gédel’s theorem says there would be truths Watson could never see. Lucas argues humans can see such truths where a machine cannot, and these truths would allow a human to discover a proof to a mathematical problem that would forever elude Watson. The Lucas argument runs into a brick wall because it asserts we see truths a machine cannot. For each alleged creative step, his opponents simply assert your brain was already sufficiently powerful to perform HOUSE_OVERSIGHT_015897

208 Are the Androids Dreaming Yet? that creative step. Lucas’s argument is largely a philosophical one. Surely all this creativity can’t all be pre-coded within the brain. Surely we must be extending our model in order to extend mankind’s mathematical model. “Prove it; say the detractor, and he cannot. We need something more practical if we're going to show a difference between humans and machines - something an engineer, or even a physicist, could grasp! That thing is a Turing Machine. We will examine this next. HOUSE_OVERSIGHT_015898

Chapter 10 TURING’S MACHINE Alan Turing HOUSE_OVERSIGHT_015899

‘A computer would deserve to be called intelligent if it could deceive a human into believing that it was human.” Alan Turing “The only real valuable thing is intuition.” Albert Einstein “Mathematical reasoning may be regarded rather schematically as the exercise of a combination of two facilities, which we may call intuition and ingenuity.” Alan Turing HOUSE_OVERSIGHT_015900

to their wireless set, waiting to hear whether the German army will advance on Warsaw. The Polish Intelligence Bureau badly needed to know what the German army was planning and had recruited this group of young mathematicians as code breakers. Up to this point, code- breaking had been the domain of linguists able to see word patterns in apparently random sets of letters. The arrival of electro-mechanical machines made this method redundant, and code-breaking had become the domain of mathematical minds. The British, French, and American intelligence agencies were all hard at work deciphering the German codes, but only the Polish group, motivated by the imminent threat of invasion, had made real progress. The code they were breaking: ‘Enigma. As with many inventions, Enigma got off to a difficult start. The inventor, Arthur Scherbius, tried to sell it to the army but they rejected it saying it did not provide any real military benefit. Instead, the machine went into service transmitting commercial shipping manifests. However, some senior figures in the German military had not forgotten the lesson of the First World War. During that war, the German army suffered major setbacks because the British broke all their codes early on. With the onset of World War II, Rommel ordered the German Army and Navy to deploy modern coding machines. The previously rejected Enigma was rapidly pressed into service and, all of a sudden, Europe went dark to Allied Intelligence. The man to lead the task of breaking Enigma for the English was Alan Turing. I: is 1943 and a small group of Polish mathematicians sit, ears glued Alan Turing Alan Turing was conceived in India but born in London in early 1912. He was precocious from an early age and an extraordinarily determined character. His first day at Public School, Sherborne in Dorset, coincided with the British General Strike of 1926. With no public transport available, the thirteen-year-old Turing cycled the 60 miles to school, staying in a guesthouse on the way and earning a write-up in his local newspaper. Turing went on to study Mathematics at King’s College, Cambridge and was made a Fellow at only 22. In 1936 Turing, aged 24, published On Computable Numbers and their Application to the Entscheidungsproblem, not a snappy title, but one of the most influential mathematical works of the 20" century. The paper described the new the science of computing and solved Hilbert’s “Entscheidungsproblem, a mathematical puzzle HOUSE_OVERSIGHT_015901

212 Are the Androids Dreaming Yet? simply translated as ‘the Decision Problem’ - could you decide the truth of a mathematical statement using some sort of automatic computation — an ‘algorithm’ as we now call it? It is difficult to imagine, but Turing worked on ‘computing’ before the invention of the computer. When he talked of computing, he meant the abstract idea of doing something mechanically. The nearest thing he had to a ‘computer’ at the time was a human mindlessly but methodically calculating something with pencil and paper! The scientific paper he submitted to the London Mathematical Society described both the theoretical basis of computing, and the design of a general-purpose computing machine: the forerunner of all modern computers. At the time, only a handful people in the world could assess Turing’s paper. One of them, Alonzo Church, was based at the Institute of Advanced Mathematics in the USA on the Princeton University campus, next door to the Institute for Advanced Study that housed Einstein. Turing travelled to America in 1937 and completed his doctoral thesis at Princeton. He might have stayed, but Europe was heating up and war seemed inevitable, so Turing returned to England to take up a part-time job in the government code-breaking branch. Here he was able to indulge his passion for hands-on engineering, experimenting with the newly invented valve technologies. When war finally broke out Turing was ordered to report to Bletchley Park, just north of London. This was to be the home of the top-secret British code-breaking group tasked with cracking Enigma. Turing’s first task was to debrief the Polish mathematicians and see what they had discovered. The Polish mathematicians had seen there were flaws in Enigma that made it repeat itself. They had made a copy of the machine to test different coding configurations and had been routinely cracking Enigma for 6 years, but the Germans had been getting smarter and it was taking longer and longer to crack the codes. Turing realized he could apply the Polish ideas in a more general way and break the codes on an industrial scale. He was installed at Bletchley Park to lead the project. Initially he was successful but as the war continued, Enigma developed subtleties making it harder to break. At one point, it was taking a whole month to break a single day’s messages. Turing realized the only solution was to use computer technology to fully automate the decryption. He built a computing machine that could simulate thousands of Enigma machines and try out all the possible settings in a short space of time. The machine acquired the nickname ‘a bombe; perhaps because of the ominous ticking sound it made as it calculated (or maybe as a reference to the smaller Polish machines). HOUSE_OVERSIGHT_015902

Turing’s Machine 213 Thanks to Turing’s insight into coding schemes and the machines he designed, the British were soon able to read almost every coded message the Germans sent during the war, giving the Allies an enormous advantage. The D-Day invasion involved convincing Hitler that the Allies had a huge army of nearly 400,000 men, massed around Dover preparing an attack on Calais head on, with a second army in Scotland poised to attack Norway. In truth, they had only 150,000 men planning an assault on the Normandy Beaches in the South. Just before the landings messages were decoded showing Hitler had fallen for the Allied subterfuge. Even as the Normandy landings began, Hitler still thought this a bluff and kept his 28 divisions at Calais waiting for the imagined attack. Without this intelligence advantage, the Allies would have needed a much larger invasion force, and Churchill believed Turing’s work shortened the war by as much as two years. The cracking of Enigma remained a secret after the war and Turing’s story remained untold for many years. When Churchill wrote his history, The Second World War, a massive work in six volumes, all sorts of sensitive information featured, but Turing’s work was omitted. One sentence hints that Churchill might write something about it in the future, but he never did. Churchill considered the work at Bletchley Park so sensitive he had it put in the highest classification — extending the 30-year secrecy rule. We must presume the decoding schemes were still being deployed during the Cold War. The papers were finally released in 2010. In one of those sad turns in history Turing was found guilty of gross indecency for homosexuality in 1954, a criminal act at the time, and was prescribed hormone treatment. This affected his mental state and he took his life by eating an apple laced with cyanide. He was eventually honored posthumously as a war hero and one of the most significant thinkers of the 20" Century. A Turing Award is the equivalent of the Nobel Prize for Computing. He was given a royal pardon in 2013. To see how Turing came up with the idea for the Turing machine and solved the decision problem, we need to get a feel for theoretical mathematics. That might sound a little heavy going but don’t worry, I will use a simple piece of mathematics to explain, one we have all played with as children, secret codes. HOUSE_OVERSIGHT_015903

214 Are the Androids Dreaming Yet? Codes Everyone has played with some sort of secret code as a child — the Aggy Waggy game, passing notes written in invisible ink made from lemon juice, or perhaps a simple cypher. If I want to send you a secret message, I can use a substitution code. Let’s see how good a code breaker you are. Can you decode this? Gdkkn Qdzcdq It’s really easy. You might guess the message from the pattern of letters and your knowledge of my writing style. There are a couple of interesting patterns to note: the 3“ and 4" letter of the first word are the same and the first and last letter of the second word are the same. As a test I gave this code to my wife and my eight-year-old daughter to see how long it took them to decode... Less than a minute for my wife — a linguist. We will come back to my daughter shortly! Roman Emperors used this sort of simple code to secure their messages, but modern codes have to be a great deal more sophisticated. Let us use a progressive cipher where we vary the substitution using a secret word. Take the name of my dog and write it down repeatedly next to the letters of the message you want to keep secret. Now translate all the letters in the message and the code into numbers ‘a = 1, ‘b = 2 and so on. Then add the letters of my dog’s name to the letters of the message one at a time. If I get to 26 (‘z’) just wrap around to ‘a and carry on. This is called modulo arithmetic. This coding scheme will translate T to ‘a the first time but ‘T to ‘c the second making it much harder for a linguist to see any pattern. Enigma Machine hello reader can you read this code georgegeorgegeorgegeorgegeorgegeorge Gives ojacveyjpvlwghpegcvzoilfkehzpxghcvle HOUSE_OVERSIGHT_015904

Turing’s Machine 215 The advantage of this cipher is that I can easily remember the name George. I don’t need to write it down. And the circular application makes the message sufficiently obscure you cantt easily work it out... Is this, therefore, a good code? No. This cipher is easy to break. Once you have guessed that I have applied a repeated short code word, you can write out ALL the possibilities and decrypt my message! This may be tedious, but if you are fighting a war and your life depends on it, you can employ a thousand people to write them all out. The British government employed 10,000 people at Bletchley Park, many of them doing exactly this. You might think that applying ALL the possibilities is too time consuming in practice but there are many shortcuts. If I suspect the message contains the name of a German town all I need do is try keys until I find a German town somewhere in the message then work my way outwards from there. Or perhaps I suspect the key is something easy to remember like the name of the Commandant’s dog. I can try ALL German dog names until I get lucky. If I’ve 10,000 people working for me this is easy. The Enigma machine and the coding process set up to operate it was designed to remove these loopholes. For a start, the keys were all random numbers taken from a code book — no dog names allowed — and the machine took the idea of a simple progressive cipher and made it much more complex. Imagine I took my GeorgeGeorgeGeorge pattern but then every 3" character added one, every 14" character subtracted 15 and every 40" character added the 3™ letter of the First Mate’s mother’s maiden name. Now this would be a VERY hard code to break. I would need a machine to code messages because if I tried to do it by hand I would make so many mistakes that the messages I send would be unintelligible. The Enigma machine made these coding schemes a practical possibility. But, although Enigma is hard to break it is not impossible with enough computing power. Is there any code that is impossible to break? An Unbreakable code Is there a way of coding a message so you can never break it? The answer is there are two ways to code a message so it is PERFECTLY safe. The first is to use a one-time pad and the second is quantum cryptography. HOUSE_OVERSIGHT_015905

216 Are the Androids Dreaming Yet? One perfect way to encode a message is to use a one-time pad. On a sheet of paper I write a completely random set of numbers or letters — since we are going to translate numbers to letters it does not matter which. I make a copy and give it to a person I later want to send a coded message. Because I will only use these two paired sheets once it helps to make a few of them - a pad in fact. By convention, we refer to a single sheet or a whole book as a one-time pad code. Here is the one-time pad I created earlier. It is just a random sequence of letters and spaces. kaleygngaloiuebldlan dlkawoqyevbax gmlsosuebal To code a message, I substitute numbers for letters as with the progressive cypher earlier again using modulo arithmetic to wrap around if I reach the letter ‘z. I have applied my one-time pad to the hello reader message below to get ‘sfacngfvbpta. hello reader sfacngfvbpta This code is unbreakable — almost! Notice there are very few clues for anyone wanting to decode it without holding a copy of the pad. Spaces do not necessarily indicate breaks between words, and letter patterns are absent. It has only one flaw. The total number of characters and spaces could have some meaning. This is a problem because if I routinely communicated bombing targets and my message was “Bomb Bath’. You could figure out the sender was not going to bomb Bristol if the message were shorter than 11 letters and spaces. To avoid this problem, messages are extended with nonsense at beginning and end to make sure no information can be gleaned from the length. The convention is to code messages to the full length of the pad. You must never reuse a pad. Each time you code a message, rip off that page rather like a calendar. Destroy it and use the next page for the next message. At the other end, the recipient uses his copy of the pad to run the process in reverse. Decode the message by swapping each letter according to the modulo method, rip the page from the pad, and burn it. Because each key is only used once you can't use any sort of statistical method to work out the message, making the one-time pad perfectly secure. Claude Shannon proved this in 1945 while working for Bell Corporation but, due to wartime secrecy, his proof was not published until 1948. HOUSE_OVERSIGHT_015906

Turing’s Machine 217 The Perfect Code The proof that a one-time pad is perfectly secret is straightforward. Imagine I take a coin and flip it 1000 times. PI write down some of the results as follows: HHTHHHTTHTTTHTTTTTHTH... I give you a copy of my results and keep one for myself. Now we each have the same random set of Heads and Tails recorded on a piece of paper. I can convert any message from letters to binary numbers: ‘a = 00000001, ‘b’ = 00000010, ‘’ = 00000011 and so on. If you are not familiar with binary just assume I have a code where we only ever use combinations of 0s or 1s. To encrypt the message we flip each bit — 0 goes to 1 or 1 goes to 0 — using my random list of heads and tails according to the following rule: If I have a head flip the bit, otherwise leave it the same. I now have a randomized message, and it really is truly random. To convince yourself, imagine answering the question, do you like coffee or tea? Think of your answer and flip a coin. If the coin lands heads change your answer otherwise leave it the same. Now write your answer down. Try it out a few times. Do you see you end up with a totally random set of decisions — tea, coffee, coffee, tea, tea, tea. If you don't record the coin toss there is no way to determine your true answer. Similarly, the message I encoded above now looks like a completely random stream of 1s and 0s and the only person who can decode it is the party with the other record of the coin tosses. Apply this to the message and, as if by magic, the message reappears. Any other random sequence will yield gibberish. It has to be the SAME random sequence I used in the first place. Mathematically, the proof involves working out that the probability of getting the right answer by applying a random sequence is 1 in 2" and the probability I could guess the answer is also 1 in 2"? The same! So the chance of decrypting the message knowing the encryption method is the same as simply guessing the message and getting lucky. Therefore, the message is perfectly encrypted. Quantum Cryptography It turns out there is one other perfect encryption method that involves thinking about the nature of secrets. Normally we consider the primary problem with sending a secret message is coding it so that it can’t be read HOUSE_OVERSIGHT_015907

218 Are the Androids Dreaming Yet? by anyone but the intended recipient. However, wouldn't it be equally valuable to know if someone other than the recipient had intercepted and read the message? This is the trick quantum cryptography gives us. Taking a measurement with a quantum device disturbs the system so measurements can be taken only once with the same results. By the same logic, I could send you a message and if someone else has read it in the meantime, you will know. I could arrange to meet with you in Berlin and if you detect the message has been intercepted, you could simply not show up. I could use this same technique to send you a one-time pad. If you receive it without it being overheard, I could then safely send you an encrypted message. In 2007, this technique was used to transmit the results of a Swiss election from the polling booths to the central counting center. Enigma World War II accelerated the evolution of encryption from simple substitutions a human could perform to complex ciphers only a machine could calculate. You might wonder why everyone does not use a one- time-pad since it is a perfect code. The problem is distributing and maintaining the pads while keeping them secret. My daughter cracked my earlier code because she knows my laptop password, broke in, and read the answer. That’s the problem with codes — security. The pads could be sent out in sealed envelopes but it would be easy to intercept an envelope, copy the pad and reseal it. You would then have a perfect and undetectable way to break the code. Also, if I were an Admiral wanting to communicate with my fleet of submarines I would need a huge pad — one page for every message I want to send — and either a pad for each submarine or one pad for all submarines. If I use only one pad, then I cannot talk to a submarine privately, and if any pad were lost all security would be breached. One-time-pads were used by both sides during World War Two, and often printed on nitrocellulose — a chemical similar to the explosive nitroglycerine. This allowed users to burn the codebooks quickly if an enemy threatened to capture them. Both the Americans and British captured Enigma machines and codebooks during the war. A Navy Enigma machine was a sought-after prize, as it was more complex than the Army version, with extra dials and plug settings. To crack the more sophisticated codes Bletchley Park HOUSE_OVERSIGHT_015908

Turing’s Machine 219 needed to get hold of Enigma machines, ideally without the Germans’ knowledge. The film U-571 merges two such capture stories into one, taking a few dramatic liberties along the way, but it’s well worth watching. Even with a captured machine, the codes were hard to break. You needed a starting point — a crib to give you a clue what the machine settings were. Helpfully, the German Army often began their messages with a weather report. Everyone knows the German word for weather — ‘Wetter’. Decode the first 20 letters of a message until you found “Wetter’ and the message is unlocked. The German Navy, however, was less chatty and avoided obvious words in their messages. One way the Allies could find a crib was to blow something up. They would sail to some point in the Atlantic, fill an old boat with oil drums, and set it alight. The German Navy would get wind of this and go to investigate. The first thing they would do is to radio a message back to base with the coordinates of the wreckage, which, of course, the British already knew. This gave the British a crib, and once they were in, they could decode messages for several days in a row because the Enigma machines often cycled through a repeating pattern. Throughout the War, the German military never suspected the British had cracked their codes and thought they must have traitors giving away their secrets. The Enigma machine was an elegant compromise between a truly unbreakable code and a simple cipher. Unfortunately for the Germans, Turing was on the side of the Allies. In the 1930s almost all mathematics, accounting, and code-breaking were performed by humans using pencil and paper. It was the science behind this process Turing sought to understand. We'll take a step back in time again to 1935 and Turing’s discovery ofa solution to the Decision Problem — the Entscheidungsproblem. HOUSE_OVERSIGHT_015909

Lego Turing Machine “Machines take me by surprise with great frequency. Alan Turing HOUSE_OVERSIGHT_015910

The Machine r uring probably learned of the Entscheidungsproblem in a lecture given at Cambridge University by Max Newman. Newman described a new proof by Gddel showing mathematics was incomplete. The proof solved the completeness and consistency problems by turning mathematical statements into numbers and showing you could generate a logical paradox if you tried to argue for completeness and consistency at the same time. Thus, of the three original Hilbert problems, completeness, consistency and decidability, only decidability remained unanswered. Turing spent all of 1935 and much of 1936 thinking about this question: Is mathematics intuitive, or could a machine decide mathematical questions automatically? Eventually, cycling through the Cambridge countryside one day, he stopped to rest in a field near Grantchester and in a flash of inspiration envisioned his mathematical machine. The machine was entirely imaginary but made as if from mechanical parts common in the 1930s. The idea was to reduce the process of computing with pen and paper to its most basic level. Turing hit upon the idea of using a long ribbon of paper tape similar to the ones used in telegraph machines. A paper tape is simpler than rectangular paper as it can be handled mathematically as a single sequence of numbers — we don't have to worry about turning the page or working in two dimensions. If you are worried that a tape is less powerful than a sheet of paper remember Cantor’s theorem: an infinite plane is the same as an infinite line. The use of a tape massively simplified the mathematics, and subsequently many early computers used tapes, as they were easy to handle in practice as well as in theory. HOUSE_OVERSIGHT_015911

222 Are the Androids Dreaming Yet? The eye, hand and pencil of a human mathematician was modeled as the read-write head of a teletype. It allowed the machine to read input from the tape and write information back so as to keeping track of intermediate calculations or provide the final output. The operation of the machine was straightforward. At each moment in time the machine could read a symbol on the tape, move the tape forward or backwards, and write or erase a symbol. That's all he needed to model a human doing something like long multiplication. Turing argued his model was exactly analogous to a human performing a computation. Turing’s imaginary machine was now able to perform computations just like a human. You could write down the rules for a given procedure and the machine could, for example, do long multiplication. At each step of the calculation, the computer would examine the state machine, look up the state in the instruction book and put the machine into its new state. If you recall Searle’s Chinese Room, this is the same process the man in the room followed: get a symbol, look it up in a book, and reply with the corresponding symbol. Universal Turing Machine We have missed one important step from our explanation of the modern computer: the ability to run programs. Nowadays, we take for granted you can download a program from the Internet or buy one from a shop. In the 1930s adapting a single machine to multiple purposes was a radical idea. Machines were built to do one thing, and one thing only, and there was no concept of a general-purpose machine. Nowadays this is hard to comprehend, but there is a similar revolution going on in manufacturing today with the widespread adoption of 3D printing. Today most factories use tools — lathes, drills and saws — to fashion objects. Each machine does a specific job and is not ‘general purpose. But innovative new machines can now be purchased relatively inexpensively called 3D fabricators, which print entire objects. The same happened for electronic logic in Turing’s time. Before computers, logical tasks were performed by banks of relays. How these banks work can be illustrated by the workings of an old- fashioned elevator. If you pressed a button to call an elevator, you closed a switch coupled to a relay in the basement sending power to the car. Another switch was tripped automatically when the elevator reached the desired floor. All the functioning of the elevator system was fixed. Once you pressed a button to go up you could not change your mind and press HOUSE_OVERSIGHT_015912

Turing’s Machine 223 Old Fashioned Relay Mechanism the button to go down. That logic did not exist in the relay banks. If you wanted to improve the logic of the elevator you would need to rip out all the relays and rewire everything from scratch. Turing’s first imaginary machine was set up in the same way. It had a fixed set of hard-wired logic, a rule book. In order to perform different tasks — say addition or multiplication you had to use a different rule book. His revolutionary idea was to write a rule book that told the machine to read a soft-wired set of instructions from the tape and execute those instead. He called this a Universal machine since it could perform any procedure written on the tape. Today we call this software. It is fair to say Turing was not the first to use this idea. Charles Babbage’s analytical engine could read instructions from cards and execute different procedures, but Turing thought through all the ramifications of the idea and made it general purpose, giving us the modern science of computing. It is easy to build a real Turing machine, but by today’s standards it is a little clumsy; a team in Denmark has built one using Lego. You can see a link on my website. Very soon after Turing’s paper was published, a number of people proposed better practical implementations. In 1943, John von Neumann of Princeton University created the architecture for ENIAC, the first stored program computer, developed for the United States Army’s Ballistic HOUSE_OVERSIGHT_015913

224 Are the Androids Dreaming Yet? 3D Printing Machine Research Laboratory. The laptop I am writing on uses the von Neumann architecture, and most modern computers evolved from it. By contrast, mobile phones are descended from the Harvard architecture developed by IBM and first supplied to Harvard University in 1944, hence its name. The distinction in architectures has blurred over the years. The world supports two main computer chip technologies, one built for desktop and laptop computers, designed by Intel in Santa Clara, California, and the other, designed for mobile devices by ARM, in Cambridge, England. All these computers can, in principle, run any piece of software. Programs Software is just a series of numbers. When you click an icon on your desktop, the computer reads the number and interprets it as a series of instructions. There is a decoder inside the computer that knows the number ‘1’ means add the next two digits and the number 5493 means display them on screen and so on. On my computer the operating system, Apple's OSX, takes the number, decodes it and passes it to the CPU for HOUSE_OVERSIGHT_015914

Turing’s Machine 225 execution. You might ask what runs the operating system and that is a smaller program called the BIOS. What runs BIOS? An even smaller program called the Bootstrap. Once all this is up and running you have a working computer, which can run any program you throw at it. The problem with programs is they tend to crash — usually at the most inconvenient times. It is often not clear whether a program has truly crashed. It might be stuck in an infinite loop, or it could be calculating the answer to a complex question, such as the answer to life, the Universe, and everything. How would we know? If only I had waited a little longer before rebooting, the program would have run to its end and given me the answer to Douglas Adams’ question. It would be very useful, and save a great deal of time, if I had a way of telling whether a program will ever stop. An elegant solution would be to have a second program called “Halt, which would test the program and output ‘will halt’ or ‘will crash’ as appropriate. It turns out this program would be more than just useful. It could be used as an oracle, capable of answering almost any question imaginable. I could, for example, write a program that says: for every index in Fermat’s puzzle try every number and halt if you find a solution greater than 2. Now if I run my halt program on this program and it states ‘will crash; I will have solved Fermat’s Last Theorem! Do you see why? If we give ‘Halt’ an input: a program we are interested in, along with some data, it will tell us if the program finds an answer. If I am trying to solve Fermat’s Last Theorem, we will ask it to try every possible index for the equation 3*+4*=5* and halt when it finds a true result greater than 2. If the halt program says yes and halts, you can trace through the program and work out how it did it. The theory would be proved. If the program says no, the theory is disproved. This gives us a way to discover proofs of many mathematical theorems. I could try almost any puzzle using a program with this form. All I need do is put a problem in the following decision format: try all possible options, and then stop and ring a bell if a solution is found. The Halt program would then give the result leading to untold riches, winning all the remaining Clay Mathematics prizes at the very least and earning me $6m. Does such a magical program exist? The answer, sadly, is no. There is no Halt program and the final part of Turing’s paper proved there can never be. HOUSE_OVERSIGHT_015915

226 Are the Androids Dreaming Yet? The Proof Let’s write a list of all the possible programs my laptop could ever run. A comprehensive way to do this is to start at one and try every number.As I count up Iam simply generating numbers, for example, 5,433,232, then turning each number into a program file and running it. For a bit of fun, I created a couple and tried them out on my laptop. They did nothing, so it was not very edifying. Most numbers are just junk because programs have to be in the right format for the computer you are working on. It’s just like words. If you randomly take a handful of scrabble tiles out of a bag, most of the time you will have nonsense, but every now and they you will have an actual word. Be careful with this; you could accidentally write, “delete every item on my hard disk.” Of course, the probability is astronomically low, but Murphy’s Law says it will happen, so back up your data! As you count up, you will generate every possible program along the way. A mathematician would say programs are recursively enumerable. The word recursive means there is an algorithm and enumerable means to count. Therefore, there is a counting algorithm that would run every imaginable program. Here is a list of them, or at least a some of the highlights: 0 (probably doesn’t run) 1 (ditto) 00 (ditto) 01 (ditto) 011001001001000100 (makes the computer beep once) ... (from here on T'll give the program names since the numbers are too large to print) Does Nothing (there are many of these) Is Gibberish (there are an infinite number of these) Junk (an infinite number of these) Print Something (again an infinite number of these) More Gibberish Excel Word PowerPoint Mathematica... Fermat’s Last Theorem enumerator (runs for ever) A nonworking version of the Halting Program A nonworking version of the Crashing Program Really big programs that don't fit on my hard drive HOUSE_OVERSIGHT_015916

Turing’s Machine 227 and so on. You can see that every program imaginable is generated in our list. If you are wondering which version of Word or Excel, the answer is every version and every bug ridden unreleased version as well. We are enumerating every program that could ever be run in the known universe! Perhaps you can see a problem looming. Ican pose any mathematical puzzle in a clever way so that a program only stops if there is a solution. I am about to list every possible program that could ever be created. If halt exists this will automatically prove every mathematical theorem imaginable. Let us see if this is so. For our thought experiment, we will assume every program takes an input. Historical convention in computing means this is generally the case. If you type a program into the command line of a computer with some words listed afterwards, the computer will usually run the program with the words as input. For example, if you type, “Print “Hello World”, most computers will print “Hello World. We now imagine there is a Halt program that can run on an infinity of inputs. Will it work for every input? We are looking for a paradox caused by the existence of the Halt program. If Halt causes a paradox then Halt cannot exist. Here goes... If there is a Halt program, we can write a Crash program. That’s a program that goes into an infinite loop if it detects a program will halt. Now what happens when we feed Crash into itself? Does Crash halt if it runs with the input Crash? This creates a paradox; there is no solution which makes sense. It’s similar to the Barber Paradox of earlier. Since a paradox is created there must be a fault in our original theory. The error is the existence of Crash. Since Crash cannot exist and it was created as the logical opposite of Halt, Halt cannot exist either. QED. There is no general program that will tell if another program will halt because such a program could not run with the negative of itself as input. This places a limit on the power of computers to automatically solve problems. There is certainly no general purpose algorithm which will solve every problem. Slightly more subtly there is no general purpose program that is guaranteed to solve one arbitrary problem. HOUSE_OVERSIGHT_015917

228 Are the Androids Dreaming Yet? If there were, you could just write a program to sequentially present every problem to the arbitrary problem solver and you would have solved everything. This presents us with a puzzle. A huge software industry has grown up based on Turing’s ideas, employing tens of millions of people worldwide. This industry regularly solves all manner of problems. The proof from Turing’s original 1936 paper suggests there should be quite strict limits on the power of computers. In the next chapter, we will examine this industry and take a look at Turing’s theorem from a modern view point. The chapter can be read as a stand alone article but was originally written as an integral part of this book. HOUSE_OVERSIGHT_015918

Chapter 11 SOFTWARE Fred Brooks HOUSE_OVERSIGHT_015919

Medieval Block Print from ‘No Silver Bullet’ “The bearing of a child takes nine months, no matter how many women are assigned.” Fred Brooks “Adding manpower to a late software project makes it later.” Brooks’ Law HOUSE_OVERSIGHT_015920

Fred Brooks explains why writing software is hard, and why machines are not going to do it for us anytime soon. The original article appeared in the proceedings of the Tenth World Software Conference. It was subsequently expanded into the, now famous, book, The Mythical Man Month. Brooks believed solving real world problems involves understanding the essential complexity of life. ‘Accidental Complexity’ — the simple type I: No Silver Bullet — Essence and Accidents of Software Engineering, — is the time-consuming part of writing software, for example, listing all 220 countries of the world in a website, or making sure all the buttons in an interface line up correctly. These tasks are tedious — you have to look up all the countries in Wikipedia and make decisions, such as whether the United Kingdom will be denoted ‘UK’ or ‘GB. They don’t need any real ingenuity. ‘Essential Complexity’ is altogether different. It involves understanding the world and setting out the rules in meticulous detail. Brooks argued essential complexity is not susceptible to being sped up by machine processes. Navigating these architectural decisions cannot be automated. He gives us an analogy by comparing writing software to building a house. When you build a house, an architect designs it, an engineer makes the calculations to ensure it is safe, and a construction firm builds it. The construction process dominates the cost and time. In software projects, an engineer writes a program that precisely defines the design and the construction and calculation is done by a compiler — software that takes the design and makes it machine-readable. Compilers operate in a fraction of a second. Making software is, therefore, dominated by the design time, and design is all about capturing the essential complexity of a task. This chapter will try to show where essential complexity comes from, why computers can't tackle this sort of complexity and, therefore, why they can't write software. Good news for programmers as this means job security! For a more thorough treatment of the mathematics read my paper The Free Will Universe at www.jamestagg.com/freewillpaper. HOUSE_OVERSIGHT_015921

<html Lang="en"> ehead> «meta charset="UTF-8" /> «meta http-equiv="Content-Type" content="text/html:; charset=UTF-8" /> <meta name="viewport" content="width=device-width, initial—scale=1.8"> <title>James Tagg | Invention, Physics and Farming</title> <link rel="profile" href="http://gmpg.org/xfn/11" /> <link rei="pingback" href="http://jamestagg.com/xmlrpc.php" /> <!—[if Ut IE 9]> <script src="http://[email protected]/wp—content/themes/premium/broadsheet/js/html5. js ?m=1393348654q" type="text/javascript"></script> <! [endif]—> <script src='//r—-login.wordpress.com/remote—Login. php? action=js&amp;hast=jamestagg. com&amp; id=57804437eamp; t=14060428698amp; back=httpesAs2Fa2Fjamestagg. coms2F' type="text/javascript"></script>= <script type="text/javascript"> f* <![CDATA */ if ( ‘function’ === typeof WPRemoteLogin } { document.cookie = "“wordpress_test_cookie=test; path="; if ( document.cookie.match( /(;|*)\s#wordpress_test_cookie\=/ } ) { WPRemoteLogin(}; } i f* ]]> */ </script> <link rel="alternate" type="application/rss+xmLl" title="James Tagg &raquo; Feed" href="http: //jamestagg. com/feed/" /> <link rel="alternate" type="“application/rss+xml" title="James Tagg &raquo; Comments Feed" href="http: //jamestagg. com/comments/Teed/" /> <script type="text/javascript"> /* <![CDATA[ +/ function addLoadEvent(func){var oldonload=window.onload;if (typeof window.onload!='funetion') {window.onload=func; }else{window. on load=function( ){oldonload{);tTunc();}}} fe ]]> */ James Tagg’s Home Page “Computers are stupid. They can only give you answers.” Pablo Picasso “Software is like sex: it's better when it’ free.” Linus Torvalds HOUSE_OVERSIGHT_015922

Silver Bullets Can't be Fired uman brains are wonderfully creative things. We can compose H music, play golf, write novels, and turn our hands to all manner of problems. Many people use their brains to write software. In our modern-day lives we use software all the time: when we access the web, type on a word processor or play a computer game. Software also inhabits many apparently dumb devices. Modern cars contain dozens of computers quietly working away; providing entertainment and navigation, controlling the engine, and helping the car brake safely. In my living room I count over a hundred computers. Many are tiny, like the one in my TV remote control, while others are hidden as parts of larger machines. The laptop on which I write has over twenty computers inside it, besides the main Intel processor. One thing all these computers have in common is that a human being sat for many hours writing their software. Software is formal logic written in something resembling English. If I go to my ATM and try to withdraw cash, a programmer will have written out the logic for the transaction as a set of rules. When I put my bankcard in the slot, and type in my PIN, a line of software will ask: If the bank balance of ‘James Tagg’ is less than twenty dollars and I have pressed ‘withdraw for an amount in excess of twenty dollars, then display, “We are sorry we cannot process the transaction at this time.” and return the card. There seems to be an unwritten rule that the things a computer says should be accurate but unhelpful! HOUSE_OVERSIGHT_015923

234 Are the Androids Dreaming Yet? TLL NEED TO KNOW FIRST OF ALL, YOUR REQUIREMENTS WHAT ARE YOU BEFORE I START TO | TRYING TO \ DESIGN THE SOFTWARE. ] ACCOMPLISH? = oO Jo 3 = =i] uw = = 2 E °o oO w a E ui a T WON'T KNOW WHAT T CAN ACCOMPLISH UNTIL YOU TELL ME WHAT THE SOFTWARE TRY TO GET THIS CONCEPT THROUGH YOUR THICK SKULL: THE SOFTWARE CAN DO WHATEVER I DESIGN IT TO DO! at Oe Alice, Ted and Software Specification It would have been much more helpful if the computer had said, “You do not have enough balance in your account.” And, it would have been more helpful still if it had asked whether I needed a temporary overdraft. However, such a feature needs many more lines of software and this is time-consuming to write. Software takes time and is expensive, because it has to be written in a general-purpose way. Any name could substitute for James Tagg, and any amount could be used. After all, it would be useless if an ATM machine could only give out $20 to one person. The generalization of software makes use of variables instead of fixed values and this renders it hard to understand. Wherever we meet an idea that needs to be generalized, a letter must be used instead of a fixed value. Computer programs tend to look like this: if @ wants to do ‘b’ with ‘c then allow it only if ‘@ is greater than ‘c. The software programmer has to keep track of all the possible values that could be inserted into each of the variables and make sure each and every combination would make sense. My ATM scenario gets complex quickly. It needs to be able to answer a range of questions for all the bank’s customers, deal with any amount of HOUSE_OVERSIGHT_015924

Software 235 IT MEAN WHAT ARE YOU TRYING TO ACCOMPLISH WITH THE SOFTWARE? IM TRYING TO MAKE YOU DESIGN MY SOFTWARE. -- 3 bj ww rg — ] > r=) a Q 6 i a — bs 4 = f=] o wn o o S a 2 CAN YOU DESIGN IT TO TELL YOU MY REQUIREMENTS? www.dilbert.com money and handle security when communicating with foreign banks is necessary. A human being must write lines of code for all the rules and every exception, making provision for any gibberish that might be typed in by the customer. Many people ask, “Wouldn't it be great if my computer could write software for me? Humans could sit back and put their feet up?” While most people don’t actually believe this could happen, they will often ask why we can’t specify software exactly and use unskilled people to write it. Both proposals fundamentally misunderstand the nature of writing software. What do Programmers Do? A human software programmer can write up to 1000 lines of code per day. At the beginning of a project, when the work is unconstrained, programmers write fast. Things slow down once programmers encounter the enemy: the real world. By the time the code is complete and selling in shops, the productivity of a programmer can be as low as one line of code per day. This is staggeringly low and luckily only applies to big HOUSE_OVERSIGHT_015925

236 Are the Androids Dreaming Yet? commercial software, equating to about 10 words per day. A good typist types at 80 words per minute and most programmers are reasonable typists. So software writers in a big project spend only a minute or so per day in the act of writing. The rest is taken up by meetings, process discussions, email, reporting and so on. In projects that avoid much of this administrative overhead, good software programmers reach a long-run average of about 225 lines per day. This has been the level of productivity on the products I have developed in the past. These projects were lucky. They had a single team on the task from beginning to end and, in general, the projects took few wrong turns. Still these programmers were spending only 10-20 minutes of each day on actual programming. What were they doing the rest of the time? In the early days of programming you might have a great idea, but the process of turning this idea into software was immensely long- winded. I learned to program at Manchester University in the 1980s. The enormous machines in the basement of the computer building provided heat for both our building and the mathematics tower next door. We were not permitted to play with these basement monsters but were ‘privileged’ to submit instructions to a mini computer in the undergraduate section - a PDP11-34. For those of you not acquainted with computers I can tell you the process of writing software in the 1980s was immensely tedious. To add two numbers and display them on a screen took a month of lab time, using detailed instructions written in machine code. Everything was manual, including writing your code out in pencil on special paper with little numbered squares and then giving it to someone to type in overnight! You would return the next day to discover whether you had a usable program or a something riddled with errors. If you found an error, it would require editing. This was nothing like using a modern word processor. The online editors of the day were the ultimate in annoying software. If you misspelled a word, you would need to count up the letters and spaces manually on a printout and enter a command - replace letter 27 of line 40 with the character ‘r. Each and every typo would take five minutes to correct. I managed to finish the simple program required for course credit — I think it displayed an eight-digit decimal number — and ran for the hills. In my second year I bought a PC and decamped to the physics department next door where I remained for the rest of my undergraduate life. The PC revolution provided programmers with a new and intuitive software creation environment where almost all the tedium was removed. A wealth of tools for creating software was pioneered by Bill Gates of HOUSE_OVERSIGHT_015926

Software 237 Microsoft and Philip Kahn of Borland, along with intuitive applications such as the spreadsheet invented by Dan Bricklin and Bob Frankston and made popular by Lotus Corporation. Today all computers have elegant WYSIWYG, “What You See Is What You Get’ interfaces, where you drag and drop elements into place on the screen. Over the last 25 years writing software has sped up and stopped being tedious — becoming almost a joy! In No Silver Bullet, Brooks explains that writing software can't be accelerated any further because all the tedious mechanical tasks have already been removed. Remember his analogy: Writing software is like building a house, but with some important differences. With a house, an architect handles the design and then turns over construction to a building company. Construction takes an appreciable time, more time than the design and quite a bit more effort. But in software the construction is totally automated. When we complete the design for a piece of software we press compile on the computer and the software is built and tested automatically in a matter of seconds. Speeding this process up any further would make only a tiny improvement in the overall software creation time, since the process is already 99% design and 1% building. For the most part, the creative process of writing software cannot be improved through mechanical means. This is not always the case. I recently upgraded the machines for some developers I work with. We added solid state hard drives. Compiling a program now takes only 10 seconds, compared with 6 minutes before. Because programmers nowadays tend to compile their programs very regularly we estimate this saves them as much as an hour a day. This is the only real innovation I have seen in the build phase of software in the last 5 years, and it’s arguably not an innovation at all. We just forgot to keep on top of the build time and allowed it to get out of hand. You might argue some counter examples. Modern software design suites let you drag and drop things on the screen to make applications or build a website. Two hundred million people have managed to put together WordPress websites using this technique. These are mechanical procedures for solving a programming task and seem to contradict my argument. They allow us to lay out graphics, press a button and turn the design into software. But they perform very simple tasks. The computer simply notes the coordinates of each box on the screen and places those numbers into a file. The process is entirely mechanical and could be performed by a clerk with no programming knowledge following a set of rules. The computer just does it faster. I did the clever work; I had the HOUSE_OVERSIGHT_015927

238 Are the Androids Dreaming Yet? idea for the software, I came up with the idea for the interface, I decided where to place the boxes, and I chose all the colors, fonts and graphics. I did all the creative bits! So, now we know what programmers do all day. They create! Origins of Software Alan Turing first described the modern day computer in a paper presented to the London Mathematical Society in 1936. He was not trying to invent the computer. That was a by-product. He was trying to solve a puzzle that had been troubling mathematicians for 30 years: The Decision Problem. David Hilbert set out the challenge during a public lecture to the French Academy of Science in 1901, marking the turn of the century. Rather than give a boring lecture extolling the virtues of scientists, he decided to give his audience a list of all the puzzles mathematicians were stumped on. Rather like the XPRIZE of today, he presented the problems as a series of challenges. Sadly for the mathematicians of his time, there were no million dollar prizes on offer, just a moment of fame and the adulation of their colleagues. Each challenge was given a number. The list included many famous puzzles; the Riemann Hypothesis, the puzzle of Diophantine Equations and the Navier Stokes Hypothesis, to name only three. A group of these questions were to coalesce into what we now know as the Decision Problem. The Decision Problem is very important to computer science because it asks whether an algorithm can be written to automatically discover other algorithms. Since all software is itself algorithmic you could rephrase the question: Can software write software? This might seem esoteric. But, if you are a computer scientist, it is an important question. If we could solve all mathematical problems automatically we would not need mathematicians anymore. And, since programs are applied mathematics, the same goes for computer programmers. Before you breathe a sigh of relief because you are neither a mathematician nor a computer scientist, you should remember it is possible to describe all knowledge using numbers. That's what your iPhone does when it stores music. If everything can be represented by numbers, then a fast-enough computer could use an algorithm to create everything! You really could set Douglas Adams’ Ultimate Question of Life the Universe and Everything before a computer and it would come up with the answer — presumably extrapolating the existence of rice pudding and income tax along the way. HOUSE_OVERSIGHT_015928

Software 239 Algorithms Back in the 1930s no mechanical system could perform a calculation with any speed. People still used pencil and paper for most things; the newly-invented mechanical cash registers were slow and could perform only one calculation for each crank of the handle. If you wanted to calculate something complex, you had to employ a computer: a person who could do mental arithmetic enormously fast. Richard Feynman’s first job was computing for the Manhattan Project. The question was: Could a computer, either mechanical or human, blindly follow known rules to decide all mathematical questions? Hilbert’s 10" Problem asked this question of a particular type of mathematical expression — called a Diophantine equation. Hilbert’s 10" Problem “Given a Diophantine equation with any number of unknown quantities, devise a finite process to determine whether the equation is solvable in rational integers.” David Hilbert Diophantus lived in ancient Persia — now Iran. His son died young and Diophantus was so consumed by grief he retreated into mathematics. He left us seven books of mathematical puzzles — some he devised himself and some of them taken from antiquity. The puzzles look deceptively simple and are all based on equations using whole numbers. His most famous puzzle is set in a poem which tells how old Diophantus was when he died. Can you solve it? “Here lies Diophantus,; the wonder behold. Through art algebraic, the stone tells how old: ‘God gave him his boyhood one-sixth of his life, One twelfth more as youth while whiskers grew rife; And then yet one-seventh ere marriage begun; In five years there came a bouncing new son. Alas, the dear child of master and sage, after attaining half the measure of his father’s age, life chill fate took him. After consoling his fate by the science of numbers for four years, he ended his life.” Diophantine puzzles look straightforward. Hilbert asked if these problems could be solved by a mechanical procedure, in modern terms, by an algorithm. To show you what is meant by this, allow me to take you HOUSE_OVERSIGHT_015929

240 Are the Androids Dreaming Yet? 435 x 31] 435 xX 311 439 435 1305 139285 rE mre ec ang ree [reece aes DUPE, Long Multiplication back to your childhood. Do you recall being taught long multiplication at school? Take a look at the next illustration and it will all come flooding back. Once you learn the process of long multiplication you can follow the rules and get the right answer for any similar problem every time. To do this, you lay out the calculation in a particular format and apply the logic. Multiply each number by a single digit of the other number and then add the results together. Diophantine problems are a little more complex than long multiplication and some of them are a bit abstruse. But there is one very famous Diophantine problem we can all recite. “The square on the hypotenuse is equal to the sum of the squares of the other two sides” The equation for a Pythagorean triangle. The theorem applies to right-angled triangles and there are sixteen whole number solutions, known as Pythagorean triples; three, four, five; is one example. HOUSE_OVERSIGHT_015930

Software 241 Purists may protest that Fermat’s Last Theorem isn't strictly Diophantine because it refers to a variable exponent — the x to the n part. This is hair splitting. But, of course, the splitting of hairs is bread and butter to a mathematician. We will see later that Fermat’s Theorem can be made Diophantine, but we are jumping ahead of ourselves a little. A question that taxed mathematicians for many centuries was whether there are triples for higher powers, such as cubes. In other words, would the cube of the hypotenuse be equal to the sum of the cubes of the other two sides for some set of numbers? After much work, it was proven no triple exists which can solve the cubic equation. But what happens if we substitute higher indices? The next shape to consider is the hypercube — a four-dimensional cube. That may stretch your visual imagination but the equation is simple, 34444454, Again the challenge is to find a whole number solution for: Hypercube HOUSE_OVERSIGHT_015931

242 Are the Androids Dreaming Yet? “The hypercube of the hypotenuse is equal to the sum of the hypercubes of the other two sides” A picture of the hypercube might help you visualize things. It's quite difficult to get your head around this shape because it is hard to think in four dimensions. This seems strange because we have no problem seeing in three dimensions on flat, two-dimensional paper — it’s called a picture, but four dimensions on flat paper appears to stump us. Again there is no solution for a hypercube: no Pythagorean triple exists. Fermat’s Last Theorem asked whether this inequality for the cube and the hypercube is true for all higher dimensions — for the hyper- hypercube, the hyper-hyper-hypercube and so on. Tantalizingly, he claimed to have found a proof but wrote that it was too large to fit in the margin of his book. Its partly due to this arrogant annotation that it became the most famous puzzle in mathematics, frustrating mathematicians for nearly 400 years. Hilbert’s question back at the turn of the 20" century was whether a machine could find a proof of this conjecture by following a mechanical procedure, similar to our long multiplication example above. The puzzle was eventually solved in 1995 by Andrew Wiles, a mere 358 years after Fermat claimed to have solved it. Wiles’ proof runs to eighty pages of densely typed mathematical notation — considerably larger than the margin in which Fermat claimed his proof did not quite fit! There is an excellent book by Simon Singh — Fermat's Last Theorem - that tells the whole story. We now know for certain, thanks to Wiles, that the answer is ‘no. There are sixteen answers to the two-dimensional triangle puzzle but there is none for any higher dimension all the way up to infinity. How might a computer tackle this problem and find a proof? A computer could apply brute force and try many solutions; every combination up to 100 million has already been tried and no exception found. But, mathematicians are haunted by big mistakes of the past. There were theories they imagined to be true until someone discovered a counterexample. This sort of thing dogged prime number theorems. Mathematicians don’t like to look foolish and are suspicious of practical answers, “Well, I’ve tried it and I can’t seem to find an exception.” This sort of argument does not wash with them. That’s what engineers and physicists do. Mathematicians are better than that! Mathematicians want definitive answers; “It is certain no solution can exist’, and these sorts of answers require an understanding of the problem to see why no solution could exist. That’s a very high bar. What we need is a program that, rather than mechanically trying every possible HOUSE_OVERSIGHT_015932

Software 243 combination, takes our problem and definitively says, “Yes, there is a solution,” or, “No, there is not.’ There are plenty of man-made proofs of this nature. Pythagoras’s proof there are an infinite number of primes is an example. Pythagoras did not have to try every prime number. He simply understood the nature of prime numbers and gave us a logical reason why it is so. Mathematicians love a general solution. One way to solve Hilbert’s 10" Problem would be to find a single mechanical way to solve every problem. If you could solve every possible problem, you could certainly solve Hilbert’s 10% Problem. It turns out there is a way to test whether every problem has a mechanical solution — pose the Halting Question. The Halting Question I should say for a little historical color that the Halting Problem was not called that by Turing. The name was coined much later, in the sixties, by Martin Davis. Turing knew the problem by the less catchy name of the “not crashing” problem, or as he preferred, “Being circle free’, meaning the program did not get caught in an infinite loop. To understand halting we should imagine a brute force program stepping through all the possible solutions to Fermat’s problem. If there is a solution this stepping program will eventually halt and answer ‘true. If there is not, the program will run forever. Can we predict a program will not run forever? At first pass this is hard. We can’t watch it forever and say, “It never halted” So is there a clever way to do this? An algorithm perhaps? The Answer to the Ultimate Question The answer is ‘No! In 1936, Alan Turing proved there is no general- purpose mechanical way to tell whether a program is going to find an answer at all, much less what the answer is. This means Hilbert’s Decision Problem has no solution; there is no general purpose algorithm which will discover all mathematical theorems. Turing succeeded in proving this by turning the problem on its head. He proved that a crash detection program is unable to see whether it will crash itself. Since you cannot tell whether a program will crash — and by this I mean go into an infinite loop — you cannot tell if it will halt. He used the simple argument that since you cart tell if the crashing program will halt, you have already proved you can’t predict if every program will halt. HOUSE_OVERSIGHT_015933

244 Are the Androids Dreaming Yet? Impossible Shape That is Turing’s argument in a nutshell. But if that was too large a step, let’s take the argument a little more slowly and prove it a couple of different ways. First, we will use a proof by counterexample, known by mathematicians as an ‘indirect proof: These may tax your brain. If you want a visual image to help with the idea of an indirect proof, take a look at the impossible shape. It is paradoxical, which means it does not exist. QED. The Proofs There are several ways to prove the non-existence of the Halting Program. I am going to present a few in the hope one of them will hit the mark and allow you to see why. The first proof uses a software flowchart. I have laid this out on the assumption the program exists and then attempted to apply it to itself. Unfortunately, the flowchart contains a paradox and thus there can be no Halting Program. The paradox is at once straightforward and confusing. It is a more elaborate version of the liar’s paradox: “This sentence is a lie” If the sentence is true it must be false, and if the sentence is false then it must be true. The Halting Program Let us suppose there is a Halting Program. Remember that a Halting Program simply takes another program as input and predicts if it will halt or not. It follows there must also be a program called Haltcrash. Haltcrash goes into an infinite loop if it examines a program with input that halts, otherwise it halts itself. HOUSE_OVERSIGHT_015934

Software 245 K —tProgram K— Input Halting Flowchart Now we create a third program called RunMe. RunMe runs Haltcrash on itself. Still following this? Now execute RunMe with RunMe as its own input. What happens? The analysis is as follows: 1. RUNME started on input RUNME halts. If RUNME started on RUMME halts, then Haltcrash started on RUNME with input RUNME halts. If Haltcrash started on RUNME with input RUNME halts, then HALT decided that RUNME started on RUNME does not halt! Therefore, RUNME started on input RUNME halts implies that RUNME started on input RUNME does not halt. (contradiction) 2. RUNME started on input RUNME does not halt. If RUNME started on RUNME does not halt, then Haltcrash started on RUNME with input RUNME does not halt. If Haltcrash started on RUNME with input RUNME does not halt, then Halt decided that RUNME started on RUNME halts! Therefore, RUNME started on input RUNME does not halt implies that RUMME started on input RUNME halts. (contradiction) HOUSE_OVERSIGHT_015935

246 Are the Androids Dreaming Yet? Both analyses lead to a paradox! There is only one way out. There can be no halting procedure. I’m sorry if this is quite convoluted. Philosophical Proof If you find these technical proofs difficult to follow, it may be easier to examine the problem philosophically. Consider the consequence of the existence of a Halting procedure. A Universal Turing Machine is a relatively small program. Roger Penrose gives a three-page example in The Emperors New Mind, and Stephen Wolfram has implemented one using a cellular automaton with as few as five component parts. A Halting Program running on such a machine should be able to compute all the knowledge in the Universe. Every structure, every work of literature, every galaxy could be the output of this single, simple program. My pocket calculator could, theoretically, paint like Picasso and compose like Mozart. All art, knowledge and science would be entirely determined in our Universe and we would have no free will. If you philosophically rebel against this then the Halting Problem must have no solution. Gédel’s Insight Another way to understand this conundrum is through the earlier work of Gédel. Solutions to mathematical puzzles are neat, orderly sequences of statements where the problem is solved step by step. Computers are good at step by step processes. Surely a computer could simply proceed in a painstaking fashion to check all the possible combinations of words and symbols to discover a proof. An analogy might be trying to find your hotel room if you have forgotten the number. You could simply find it by trying every room. As you progressed through each floor, you would try every corridor and retrace your steps to the main hallway before attempting the next. Eventually you would succeed. Finding proofs of theorems is often understood to be the same sort of task: search systematically through all the numbers and you will find the solution. But this is not so: There is a hidden problem. Although it is true to say problems and proofs can be described by numbers, they are not simply related like a lock and key. We need the first number to translate into a set of symbols meaning something about mathematics: for example, that x squared plus y squared equals z squared but for higher powers there is no equality, and the second number to HOUSE_OVERSIGHT_015936

Software 247 denotes a set of sequential steps we can apply to demonstrate this fact. These steps must have meaning and obey the rules of mathematics, but what are these rules? Are they written down in a text book? It turns out there is no way to find this set of rules; it is a super- infinite task. We would need to reach into our infinite bag of numbers and pull out rule after rule, turning each into a mathematical model that explains numbers and logic and what can be done with them to form mathematical statements. The number of ways to do this is not just infinity, but two to the power of infinity. This is the number of ways to permute all possible mathematical rules. Your mind may be rebelling at this. Surely, if I have an infinite set of numbers I can just pluck all the numbers from my bag and then I am certain to have the solution. Unfortunately, it turns out there is no complete, consistent set of rules; no valid dictionary that maps all numbers to all of mathematics. That is Gédel incompleteness theorem. Despite a fundamental limit on mapping all numbers to all of mathematics, there might still have been an algorithm which could practically find solutions for a given arbitrary problem. Turing proved this is not the case. The Wiles Paradox Turing showed us there can be no general purpose, mechanical procedure capable of finding solutions to arbitrary problems. A computer program cannot discover mathematical theorems nor write programs to do so. Yet computers regularly solve problems and generate programs. That’s what software compilers do. This seems to be contradiction. The solution to this apparent contradiction is to propose a boundary: a ‘logic limit’ above which computers may not solve problems. With a high boundary a general-purpose machine could solve most problems in the real world, though some esoteric mathematical puzzles would be beyond it. But if the boundary were low, many activities in our daily life would need some sort of alternative, creative thinking. It is crucial to know where the logic limit lies. The Logic Limit Amazingly, in many branches of science it is possible to pinpoint the exact location of the logic limit, but finding that boundary in mathematics has taken forty years work from some of the greatest mathematicians of the 20" century. HOUSE_OVERSIGHT_015937

248 Are the Androids Dreaming Yet? The story starts back in the 1940s at Berkeley University with a young Julia Robinson, one of the first women to succeed in the previously male-dominated profession of mathematics. By all accounts, she had a wry sense of humor. When asked by her personnel department for a job description she replied: “Monday—tried to prove theorem, Tuesday— tried to prove theorem, Wednesday—tried to prove theorem, Thursday— tried to prove theorem, Friday—theorem false.’ Like Andrew Wiles, she fell in love with one of the great mathematical puzzles, and although she made great strides, the problem passed from her to Martin Davis for the next steps. The final elements were put in place in the 1970s with the work of another young mathematician, this time a Russian — Yuri Matiyasevich. Robinson wrote to him when she heard of his proof, “To think all I had to do was to wait for you to be born and grow up so I could fill in the missing piece.” The complete result is the Robinson Davis Matiyasevich theory which sets out the limits of logic and algebra. What, you may ask, do we mean by logic and algebra? Mathematicians like to turn everything into logical statements, even ordering a round of drinks! The discipline of logic emerged from ancient Greece as the study of language. The starting point was the syllogism: Statements such as, “All cows eat grass.” or Lewis Carroll’s assertion, “There are no teachable gorillas.” Over time the study of logic became ever more precise with, for example, the introduction of variables and equations; a=all cows, b=some grass. The formula “a eats b” translates by substitution into, “The cows eat the grass.” This doesn’t look much like a step forward but, trust me, it is. The modern way to represent logic is using prenex normal form. This mouthful simply means separating relationships between things from the things themselves. The following four statements say the same thing, each in a more formalized way. Speech: Harry loves Sally Logical: x loves y (substitute Harry for x and Sally for y) Formal: There exists an x, there exists a y (x loves y) Prenex: xdy (x Ry), Where R, the relationship, is ‘loves’ HOUSE_OVERSIGHT_015938

Software 249 The final example is in prenex normal form. The symbol ‘3’ means ‘there exists’ and R stands for relationship in this equation. All logical statements can be translated into this form using a purely mechanical process. There is even a website that will do this for you. It’s useful but I don't recommend it as entertainment! In the example above, something exists in relation to the existence of something else: one person who loves another. Give me a name and I can look up the person they love. This is simple. A computer can easily solve such problems. Indeed there are hundreds of websites doing this every day. Once you've solved one problem of this type, you have solved them all. We can rearrange Diophantine equations into many different prenex forms. The simplest form might be, ‘there exists an x which solves the following equation, x equals three? This would be written out as Ix, x=3 and is of the 4 class — ‘there exists. There are slightly more complex classes than our simple 4 relationship: VV ‘for all, there exists for all’ or the class V°V ‘for all, for all, there exists, for all: Each of these groups of equation is called a ‘reduction class. One way to think about a reduction class is as a problem in topology, ‘knots, to non-mathematicians. Imagine someone handed you a bunch of tangled cables - the sort of mess you get when they are thrown haphazardly into a drawer. You can tease them apart and rearrange them but you must not cut them or break any connection. Once you have done this you will be left with a series of cables on the desk. They are all separate, looped or in someway knotted together. Each cable has a fundamental topological arrangement: straight cables, granny knots, figure eight, and so on. You have reduced them to their simplest form, their logical classes. The same goes for logical statements. Once you have rearranged logical statements into their simplest form you can lay them out and group them together according to their complexity. Each group makes up a reduction class and you can ask whether that class as a whole is automatically decidable. It isa huge task to untangle and classify mathematical problems, and it took Robinson and her colleagues nearly forty years to succeed. It turns out problems with a form as simple as VAV (for all, there exists, for all) have no general purpose algorithm. Each must be examined individually and solved by something that is not a computer. This is a remarkable result as the logic boundary is set quite low. An 44, (exists, exists), class of problem is automatically solvable by a general HOUSE_OVERSIGHT_015939

250 Are the Androids Dreaming Yet? algorithm, but a VAV, (for all, there exists, for all), is not. Each individual type of problem within the class must be examined with insight and understanding. Our lives are full of problems — playing chess, finding a mate, designing space ships and simply getting to work in the morning. Imagine we expressed everyday problems as logical problems. Where is the logic limit for life? We have no answer for this yet, but we do know the logic limit for computing; it is given by Rice’s Theorem. Named after Henry Rice, and proven in 1951 as part of his doctoral thesis at Syracuse University, Rice’s Theorem states: “No nontrivial feature of a computer program can be automatically derived” You cannot tell if a program will halt with a given input. You cannot tell if one program will generate the same output as another. You cannot tell if a simpler program could be written to do the same task as a more complex one. In fact, no nontrivial thing can be proven. This means the logic limit in computers is low, and computer programmers have job security. For Programmers For the programmers amongst you, here are some of the things that cannot be done automatically even given infinite time: « Self-halting Problem. Given a program that takes one input, does it terminate when given itself as input? * Totality Problem. Given a program that takes one input, does it halt on all inputs? * Program Equivalence Problem. Given two programs that take one input each, do they produce the same result on every input? * Dead Code Elimination. Will a particular piece of code ever be executed? e Variable Initialization. Is a variable initialized before it is first referenced? * Memory Management. Will a variable ever be referenced again? HOUSE_OVERSIGHT_015940

Software 251 Can humans solve ‘unsolvable’ problems? The question of whether Fermat’s Last Theorem could be solved mechanically remained unanswered until 1970 when Yuri Matiyasevich filled in the missing piece in Julia Robinson's proof. Matiyasevich used an ingenious reduction method to match up sequences in Robinson's theorem with a set of Turing machines. This showed that if Robinson's theorem was false you could solve the halting problem and since you can't solve the halting problem, then Robinson's theorem must be true. All this effort proved Diophantine equations have no general algorithmic solution. This was a hugely important result but, as we noted earlier, Fermat’s Last Theorem is not, strictly speaking, a Diophantine. It is an exponential Diophantine equation. We still had no definitive answer to Fermat. In 1972 Keijo Ruohonen and again in 1993, Christoph Baxa demonstrated that Diophantine equations with exponential terms could be rewritten as regular Diophantine equations with one additional complication — the necessity of adding an infinite set of terms to the end of the equation. In 1993, J.P. Jones of the University of Calgary showed the logic limit for regular Diophantine equations lies at thirteen unknowns. Matiyasevich had already pointed this out but never completed his proof. Since infinity is greater than thirteen, all exponential Diophantine equations are above the logic limit and, therefore, undecidable. Finally, we have a proof that Fermat’s Last Theorem is unsolvable by a computer — or at least by a general purpose algorithm running on a computer. Matiyasevich went on to show many mathematical problems can be rewritten as exponential Diophantine equations and that much of mathematics is undecidable. For example, the Four Color Conjecture: “Given an arbitrary map on a Euclidean plane, show the map can be colored in a maximum of four colors such that no adjacent area shares the same color.” Meanwhile, Andrew Wiles, an English mathematics Professor at Princeton had been secretly working on Fermat’s Last Theorem. When I say secretly, he had not told anyone in his department, and only told his wife late in 1993 when he suspected he might have a solution. He had been working on the problem a long time, having fallen in love with it at the age of 8! In 1995, after nearly 30 years work, he announced he HOUSE_OVERSIGHT_015941

252 Are the Androids Dreaming Yet? Four Colors is All You Need had found a proof. He had solved an unsolvable problem, a problem that could not be answered by using a computer. Therefore, Andrew Wiles cannot be a computer! As with all real-life stories, it was not quite as neat as this. It turned out Wiles’ initial proof had an error in it, identified by one of his referees. Wiles had made an assumption about a particular number theory that had not been proven: it was still a conjecture. Working with another HOUSE_OVERSIGHT_015942

Software 253 mathematician, he managed to prove this conjecture and so, two years after first announcing that he had solved Fermat's Last Theorem he could finally lay it to rest. The Special Purpose Objection Before I declare mankind’s outright victory over computers, the Special Purpose Objection must be overcome. The objectors would argue that Wiles is a Special Purpose computer. Special Purpose computers are at no risk of breaking the Turing limit when they solve problems they have Theorem (Undecidability of Hilbert’s tenth problem) There is no algorithm which, for a given arbitrary Diophantine equation, would tell whether the equation has a solution or not. been programmed to answer. The objection misses the key point. I am not arguing having a solution to a given mathematical puzzle presents a difficulty to a computer; I am arguing a computer cannot discover one. Take, for example, the search engine Google. If I type “where can I find the proof of Fermat’s Last Theorem?” into the search box, it will retrieve a PDF of the proof as the third result. It appears this special purpose computer solved the problem. But you immediately see the difficulty. Google search already knew the answer, or more precisely had indexed the answer. The computer was not tackling a random problem from scratch. It was tackling a problem for which it knew the answer, or at least where an answer could be found. There is no sense in which the search engine discovered the proof. To really understand this objection we need to examine exactly what Turing and Matiyasevich proved. An arbitrary problem is one you do not already know the solution to when you write the algorithm. You can think of it as a variable. Is there an algorithm that can solve problem ‘X’? The alternative is a special program. It can solve problem Y. Y is a problem it knows. It must have the solution coded somewhere within it in a computably expandable way. You might think of this as a table of constants; problem Y has solution 1, problem Z has solution 2, and so on. But it could be more subtle than that. Problem Y might have a solution which is encrypted so you cannot recognize it within the program, or it might even be the result of some HOUSE_OVERSIGHT_015943

254 Are the Androids Dreaming Yet? chaotic equation so complex that the only way to see it is to run the program and watch the output: no form of program analysis will give you any clue as to what it produces. There is only one stipulation. The answer to problem Y MUST be held within the program as a computable algorithm. Put another way, the computer must already be ‘programmed’ to answer the question. Could a human mathematician be pre-programmed from birth? Yes, there is no fundamental objection to this. Mathematicians could be born to solve the problems they solve. But this would present a couple of issues. Where is this program stored? And who, or what, programmed the mathematician? Could we perhaps find an experiment to determine whether mathematicians are pre-programmed? One view held by philosophers is that the Universe programmed the mathematician. They believe we live in an entirely determined Universe with no free will. There is then no mystery as to how Andrew Wiles came up with his proof. He was destined to do it from the dawn of time. The ink that fell from his pen to the paper was always going to fall in just that way. We live in a clockwork Universe and although we might feel we have free will, this is an illusion. I simply don’t believe this. If I am right and humans do exercise free will, Andrew Wiles cannot be a computer. And because Andrew is not alone in discovering proofs, those mathematicians cannot be computers either. Humans are, therefore, not computers. The Chance Objection I said there was no automatic way to solve any problem above the logic limit, but this is not quite true. There is one automatic method you could deploy to generate a non-computable proof, the infamous ‘monkeys and typewriters’ idea where we use random chance to generate information. Many people have suggested it is possible to write a play such as Shakespeare's Hamlet by simply typing random characters until we happened upon the play. The argument is flawed. The first flaw is the process would take a super-astronomically long time. Even if every atom in the Universe were a monkey with a typewriter, it would take orders of magnitude longer than the age of the known Universe to come up with the script to a play or a mathematical proof. The probability of finding a solution to Fermat’s Last Theorem by chance is about 1 in 10°°. That’s 1 with 50,000 zeros after it. For a comparison, there are only 10’ atoms in the known Universe. To be, or HOUSE_OVERSIGHT_015944

not to be, certain of finding the proof, you would need to run a computer long enough to calculate all the possible proofs up to the length of Wiles’ solution. Currently, a computer using every particle in the Universe clocked at the Plank interval — the fastest conceivable computer running at 10° operations per second — would take 10°” times the age of the known Universe to do this. If someone tells you this is astronomically unlikely they are making a huge understatement. A computer running until the end-of-time would only scratch the surface. The second flaw is even more damning. Even if the monkeys succeeded in generating something interesting, something else needs to spot this. If an algorithm stumbled upon a proof of Fermat’s Last Theorem, what would recognize it as such? There are no ways to systematically analyze proofs. There are no mechanical methods that understand these. HOUSE_OVERSIGHT_015945

“Well, this certainly buggers our plan to conquer the Universe.” Dalek Trouble “All non-trivial abstractions, to some degree, are leaky.” Spolsky’s Law of Leaky Abstractions HOUSE_OVERSIGHT_015946

Consequences achines cannot discover theorems using algorithms, yet AY Eee do it all the time. Do the rest of us break the logic limit? It seems we do. People appear creative — painting, composing, sculpting and so forth. But, are these endeavors creative in the mathematical sense. To prove this, ironically we need to find something outside mathematics that is definitely non-computable. This is tricky. Most artistic things are fuzzily defined and there are no written rules we can apply. How can we prove a work of art could not have been generated by a computer? Trivial proofs exist but they are rather contrived. For example, it would not be possible to make a film with a solution to the still unproven Riemann Hypothesis on the blackboard in the background of a movie scene. All the mathematics Good Will Hunting had been already discovered before the movie was made. New mathematics cannot be accidentally generated by a set designer — unless, of course, they also happened to be a world class mathematician. These trivial proofs might lead a mathematician to argue the theory is proven. There are some artworks which cannot be computed. QED. But these are not very satisfactory proofs. I could create almost any movie I wanted without tripping over this rule. What I really wanted to know is whether Good Will Hunting as a whole could have been generated by a computer. Not that some weird version with a particular mathematical proof on the blackboard is forbidden. Movies are a difficult subject for HOUSE_OVERSIGHT_015947

258 Are the Androids Dreaming Yet? this argument, but music is much easier to analyze. It is linear, highly mathematical and largely uniform by culture and language. Yet it is universally appreciated. Is music a computational or a creative endeavor? Is Music Computable To prove a piece of music is non-computable requires two tests. First to show we can ‘reduce’ it to a problem that is already non-computable and, second, to demonstrate it ‘looks like’ or ‘sounds like’ a piece of music. An accountant would say it needs to pass ‘the smell test’. The first non-computable problem to be studied in depth was Emil Post’s Word Problem. Post was a contemporary of Alan Turing and studied at the Institute of Advanced Mathematics in Princeton. He solved the Halting Problem six months before Turing, but his proof used a complex recursive method called the lambda calculus. Turing’s method was far more practical, which is why we now refer to Turing machines rather than Post machines. Later in his career, Post came up with a branch of non-computable mathematics called ‘Post Problems. They look like a puzzle you might find in a newspaper. Imagine starting with the word ‘camel’ and being asked to turn it into ‘aardvark, using only a few simple rules. We'll make the problem very easy to start with: cam @ aard and el ovark. This solution is obvious; just do the substitutions and you are there. But what if the rules were a little more complex? Gennadii Makanin, a Russian mathematician based at the University of Moscow, found a set of extremely simple puzzles that are nevertheless non-computable. Here is one: {“CCBB” <> “BBCC”, “BCCCBB” <> “CBBBCC”, “ACCBB” <> “BBA? “ABCCCBB” @ “CBBA’, “BBCCBBBBCC” <> “BBCCBBBBCCA’} Word Problem Can a computer tell us which word problems have a solution and which do not? The answer is ‘no. Word substitution puzzles are a class of non-computable problem. Martin Davis proved this in 1948. Using a reduction argument we can use these word problems to prove some music is also non-computable. HOUSE_OVERSIGHT_015948

Software 259 Let us start by substituting the notes of the musical scale for the letters of the alphabet to create a piece of ‘music. Since it is a direct analogue of the word problem, we have created a non-computable piece of music. It is definitely non-computable, but is it music? If it just looked like a random jumble of notes it would be unconvincing, but luckily there are many forms of music that look exactly like a word substitution puzzle. Bach's Art of Fugue, the canons of Tudor composers such as William Byrd and Thomas Tallis, and the works of Grieg all use sequences of chords that move from one to the next using substitution rules. If you were to listen to the steps in our word substitution music, they would definitely sound musical. I think they should pass the main artistic criticism — that they should not sound formulaic. But is any actual human composition non-computable? Unfortunately, we cannot prove whether a particular piece of Bach, Tallis or Grieg is non-computable because we don't know the specific rules used to compose it. All we know are the general musical principles of harmony and counterpoint that applied at the time. We don’t have these composers personal rule sets because they were held in their brain and they are, of course, long since dead. It is statistically likely that most pieces are non-computable because there are an uncountably infinite number of them, whereas computable pieces are merely countably infinite. But that’s just probability; it is no proof. I puzzled for some time whether there is a way to prove it but had to conclude it is impossible. However, and this is how creativity works, once I had given up on the problem, my brain continued to work on it. I was not conscious of this, I was only aware that failing to solve the problem annoyed me. I then had a Eureka moment. Although I couldn't prove a piece of music was non-computational, I could make one! - a piece that could not have been created using computation alone. This requires me to inoculate your brain. Take either Andrew Wiles proof of Fermat's Last Theorem or Alan Turing’s proof of the Halting Problem; both proofs are non-computable. Each document is made up of symbols, the Roman alphabet and some special Greek symbols such as a, B, ¢, and so on. Let us Creative Inoculation HOUSE_OVERSIGHT_015949

260 Are the Androids Dreaming Yet? write out the symbols in a table and assign a musical note to each. It is straightforward to put these notes into a synthesizer and play the piece of music. I have provided a link to such a piece. Warning: once you listen to this you will have been ‘creatively inoculated’ This resulting piece of music, based on the transliteration of a proof, is non-computable. You might immediately argue with this, “The piece of music was translated from proof text to music file using a computer. It is clearly computed. but this is not my point. The music could not have come into existence in our Universe as a result of a computation. It is a computable translation of a non-computable string. It could not have been generated solely by a computer: It was done in two steps, the first of which could not have been computed. If, up to this time, our Universe has never contained a piece of music that was generated non-computationally, it does now. If you listen to this piece, you will find it impossible not to be somewhat inspired by it. You cannot erase the experience from your memory. And once you have heard it you will have been creatively inoculated. I have defeated Daniel Dennett and his like, and given you creative freedom! www.jamestagg.com/noncompmusic Having made at least some music above the Turing limit I could declare victory but I want to go further. Using the same reduction method, I believe we can show all art is above the limit. First let’s attempt novels and plays. Do you enjoy those crime novels by Agatha Christie and Colin Dexter? It must be possible to construct a plot sufficiently complex, and a murder sufficiently baffling that it exceeds the logic limit. I could keep extending this idea to provide any number of examples and, therefore, prove all art and creative output is above the logic limit. There are many other arts we could apply this argument too. In the visual domain there are non-computable images. In principle, it is possible, to draw or paint things beyond the capability of a computer. Roger Penrose has created non-computable visual puzzles such as tiling an infinite plain with special jigsaw pieces. Creating an image containing a solution to his visual puzzle is non-computable. This extension argument also applies to me. There is an argument that I am a finite being and therefore can be simulated by a computer. Since I can be simulated by a computer, I am the same as a computer and therefore incapable of non-computable thought. The argument is as follows: James Tagg will have during his life a finite number of inputs and, equally, a finite set of outputs. This means you could model me using a HOUSE_OVERSIGHT_015950

Software 261 chem Pollock computer. You could simply create a table of all the possible inputs and all the possible outputs I would make and this would be a perfect facsimile of me. A number of people have posed this as an argument to refute Roger Penrose’s assertion that humans are capable of non-computable thought. But this analysis misses a key point. There is no way to calculate all the contents of this table. My past could be tabulated. It is the history of all the things I ever did, but my future cannot. I might yet discover some great theorem that could not be computably generated. This would be a part of my output which could not be generated by an algorithm or any mechanical process. This forms a non-computational arrow of time; we can write down the past, we cannot write out the future. If a creative person such as Andrew Wiles could be simulated in advance, we would have an automatic way to find a solution to Fermat’s Last Theorem. Since this is not possible, it follows that creative people cannot be simulated. This also means the Turing test is not passable by a machine. Humans can create; machines cannot. That is the difference. Will Computers Take over the World? Ray Kurzweil, the American inventor and futurologist, has suggested computers are getting exponentially faster and will soon reach such immense power they became effectively infinitely powerful. They could instantly answer any question posed and solve all our engineering problems. He dubs this point ‘the singularity’: a point of near infinite HOUSE_OVERSIGHT_015951

262 Are the Androids Dreaming Yet? Watson and Our Future? computing power and therefore universal knowledge. This could herald a Utopian future; global warming, cancer, all things of the past. But computers might just as easily become bored and determine we humans are the real problem. If we are lucky, they may treat us as amusing pets. If we are unlucky... These consequences might have come to pass if the answer to the Halting Problem were ‘yes’ but as the answer is ‘no! This is not the future we face. Mummy, where do Bugs Come From? One consequence of the logic limit provides a theoretical basis for the origin of computer bugs. The mention of ‘bug’ conjures up stories of dead creepy crawlies stuck in early computer circuits, but the term had been in use for over 150 years before the computer was even invented. Bugs are not simply annoying mistakes.If you misspell my name as Stagg instead of Tagg that’s just carelessness. Real flaws creep into a computer program when you fail to understand Brooks’ essential complexity, or by my terminology, you stray above the logic limit without realizing it. Imagine we have created a piece of software. The software goes into test and is subjected to a range of use cases. Some of these will fail because we did not take into account all the real world possibilities. Then a strange thing happens. We get trapped in a loop of patching the errors in the program in a rather mechanical way. Find an error, patch HOUSE_OVERSIGHT_015952

Software 263 it. Find another, create a work-around, and so on. By doing this, we are effectively mechanically generalizing our solution. This is forbidden as it breaks the Turing limit, so we can’t mechanically solve a general logic problem above the logic limit. We need instead to use intuitive or creative thought. In our panic we did not stop, take a step back and engage our brain. Instead, we attempted, unsuccessfully, to blindly hack our way through the problem. If we eventually succeeded in perfecting the code this way, we would have broken a fundamental law of the Universe. Something nasty would have to happen to prevent it, such as rupturing the space-time continuum or an event equally horrible! Luckily something prevents this and keeps our Universe intact - BUGS! Bugs stop us breaking Turing’s limit. The next time you curse a bug, remember if they didn’t exist youd be in danger of causing a logical paradox. There is no problem in redefining the domain and then creatively producing an all-encompassing design, but, you can’t patch and hack your way there. This theory of bugs leads to an explanation for some modern programming rules of thumb. Written specifications are valuable because they force you to lay out the whole problem. You don't need to be detailed regarding the depth, but should be expansive about the breadth, covering all the logical complexity. This might result in many details as a by-product, but a specification needs to delineate the edges of the problem space and not simply focus on a few key points. Writing the tests for the software in advance is helpful as it is likely to tell you early whether your design encompasses the whole problem space. Also, building a prototype, throwing it away, and then building the real thing can help greatly. It may be the only way to examine the edges of the problem space in detail. Armed with a full understanding, you can then imagine solutions to the complete problem in a single creative sitting. Whatever techniques you use to improve the quality of your software, remember you are engaged in a creative process that is not, itself, open to automation. The Art of Programming Programming is an art: a creative endeavor. It is also, of course, highly scientific. When you work with a good programmer — and I have been fortunate to work with some of the best in the world — they all follow a similar process. First they talk with you at length about your needs HOUSE_OVERSIGHT_015953

264 Are the Androids Dreaming Yet? WELL... IT TURNED OUT WE SO BASICALLY ROSS |S DION'T HAVE ENCUGH BURGET || GOING TO HELP YOU TILL ITS TO HIRE ANOTHER DONE. PROGRAMMER ON THIG PROJECT. Geek Humor and examine the full scope of the problem space. Even if you say, “Oh don't worry about that bit? they always will. They want to know about everything. Then, they write a high-level list of features, some simple block diagrams, and occasionally a flow chart, only then do they begin to code, ticking off the list as they go. Sometimes, they will check to see if their list is the same as your list but more often they will come back and just check the high-level purpose. “If I give you something that achieves this, will that do it for you?” They test as they code so you end up with is something that meets your high-level purpose, and can prove it does so in its own right. At the end of the coding they write out the specification for the project so that they can remember what they did, or a colleague can pick it up in the future. This is not how students are taught. Students are told to write a detailed specification at the start and then simply implement it. If you’ve been following my argument, they are being taught to do something impossible! There is no ‘just’ to programming. Sometimes teams are even split up so that one person writes the specification and another the code — again an impossible task. If the specification was the answer to the problem, it must have required creative thought to develop and so would be as complex as the program itself. Since it is not yet a program you cannot test it, so it becomes an untestable solution to a creative problem. Since the specification is not the answer but rather a general list of tasks, the great danger is to give it to a separate programmer and HOUSE_OVERSIGHT_015954

Software 265 |WHATIPE ROSS DOESN'T KNOW || HAHA, ART? COME ON! LIKE ANYTHING ABOUT IT WOULD BE THAT DIFFICULT PROGRAMMING! HE WOULD BE TO TYPE ON A KEYBOARD ALL USELESS AND NOTHING BUT A || DAY! MY SON |S TEN AND HE BURDEN! MY PROJECT IS DOES IT TOO! STATE OF THE ART AND I'M GONNA LET NO VIGUAL BASIC PROGRAMMERS NEAR |[T! they implement it mechanically. You see, of course, the problem. It will be riddled with bugs because they have missed the creative step of imagining the whole problem and solving it in the round. This fundamental misconception of software is common in many organizations. “Ah,” says the finance director, “I'll write a very detailed spec and then we can get someone cheap to just program it.” This does not work. If the finance director has done the creative work of taking a problem and turning it into a detailed specification for the programmer to ‘just program’ — removing any ambiguity and therefore the creative overhead - he will have all but written software himself, albeit in a computer language of his own making. On the other hand, if the specification is a linear list of issues with no creative thought, he will not have reduced the time needed to program. He may have improved the quality by effectively getting a second pair of eyes onto the requirements gathering stage, but this does not help the programming effort itself. Ideally, you should never split up specification and coding. It is a creative process best handled by very small numbers of people working intensively on it. Of course, there is one big problem with this: some software tasks are huge. Before we look at the science of splitting up a software project, it is worth pointing out that many of the most famous projects were written by one man. I have met many of these people and they are all exceptional - Linus Torvalds, Linux; Anthony Minessale, FreeSWITCH; Daniel-Constantin Mierla, Kamailio; Eric Allman, ssendMail. Before splitting a project between many people, it is worth considering whether you can give it to just one individual. To do this you HOUSE_OVERSIGHT_015955

266 Are the Androids Dreaming Yet? will need to unload this person of ALL interruptions and administrative burdens. This is the most effective way to solve a creative programming task. Practically, once your task is over the limit for a single human, a software project must be split up. This requires great care. Dividing a problem efficiently means specifying the interfaces between them and decoupling the components. This is the art of an architect or a producer in the creative arts. The creative process operates similarly in other walks of life. There are many examples of successful creative duos — Rogers and Hammerstein (The Sound of Music), Ben Elton and Richard Curtis (Blackadder). Good managers, therefore, find ways to break projects into manageable sub-projects that can be worked by pairs or rely on single super-programmers with support around them. If you are lucky enough to gather together a group of super-programmers and can divide a problem efficiently amongst them, you can achieve great things. You see this pipeline in movie production. A script writer generates a script creatively. The casting director finds the actors, a director is in charge of filming, and an editor puts it together. In very great movies you will often find a great director or producer who had a hand in almost everything holding it all together. They are often accused of micro-managing but you can see that’s what they must do. They are the super-programmer with the whole creative work in their head, and an eye on the audience and financial backers. If you talk with great programmers you will be amazed by their breadth of technical, commercial and product knowledge. Why do they need all this commercial information to do their job in the round? Rules and Tips I began writing some rules on how to split up a project, and almost immediately ran into exceptions and special cases. The job of dividing things into sub-tasks is, itself, a creative problem and must not be done mechanically. Any ‘one size fits all’ rule will fail and you must apply domain knowledge and careful thought to the process. It is the job of architects or a senior engineer to split projects into smaller chunks. To do this they must accurately ‘guess’ boundaries between subtasks to create self-contained, creatively solvable problems. This can be done by either vertical or horizontal abstraction. Both have their problems. HOUSE_OVERSIGHT_015956

Software 267 Horizontal abstraction is the simpler of the two to understand, and the more common. Computer systems are built ‘on the shoulders of giants. That is to say we no longer need to place individual pixels onto the computer screen. We can assume a computer will draw a square if we specify the dimension and coordinates of the center. That’s abstraction. Today’s computers are even more helpful. We can ask them to draw a rotating cube lit from a certain angle and the computer will do the whole job for us. But, there are always practical limitations to this. I want my cubes to move around the screen naturally but I am not sure what physics model has been implemented. What will happen when they bump into each other? If the abstraction is not thoroughly thought through they pass through each other in a very odd way, breaking up and showing me they are really made of triangles, the illusion of three dimensions is lost. Whenever we work at an abstract level, we risk being exposed to its inner guts at some point. Joel Spolsky, a computer scientist who worked on Microsoft Excel, proposed the Law of Leaky Abstractions to explain this. An example of his law in action is the TCP/IP protocol stack that transports data over the Internet. The stack is hugely reliable, yet I have to debug one of these stacks at least four times a year! The problem is that the TCP (Transmission Control Protocol) is designed to provide reliable delivery of information: internet pages, my bank account and the like. But, the internet protocol ‘IP’ on which it relies is only designed for best-efforts. When a link loses a packet of information, the TCP has to retransmit it. This takes additional time. TCP provides an abstraction of a reliable connection, but the implementation is not as robust as it may seem, and the details leak through as variable latency and throughput. This explains why your web pages sometimes do not completely render. You are told it is reliable, but often it is not! Experience is so valuable to a programmer because they know which of these specifications to take with a pinch of salt and when they are likely to leak. They are battle scarred by previous naivety. I think Spolsky’s Law follows from Rice’s Theorem and ultimately from Turing’s no halting proof. If leak-less abstraction was possible you could, in principle, write a recursive partial halting solution. By layering abstraction on top of abstraction you would be able to solve some very complex problems, eventually including the Halting Problem. We know this is impossible, so non-leaky abstraction cannot exist. The other method of splitting software is vertically. This is often done following the natural boundaries of an organization: functional or geographic. Again there will be leakage between the systems; the data you get from the finance department might not be detailed enough for HOUSE_OVERSIGHT_015957

268 Are the Androids Dreaming Yet? How the project was What operations installed How the customer was billed documented Specification Cartoon the engineers or vice versa, and so groups have to interact. The main problem with vertically divided software is each group tends to reinvent the wheel, so you end up with multiple similar implementations of the same thing. All said, the architectural job in software is a dynamic one. You can split up software into separate elements but you must take into account the leakage between them. When you detect a leak you must bring people together to collaboratively solve the problem, rather than insisting on the original partitioning. While doing all this you must keep track of the overall aim and all the irritating small details contained in the many HOUSE_OVERSIGHT_015958

Software 269 How it was supported What the customer really needed lists that form the project specification. I should confess that I am no great fan of specifications, because they can mislead you into thinking you've solved the problem, but I concede a good specification is helpful. Spolsky’s Second Law is ‘Always write a specification’? Engineers should collaboratively write the specification as a response to the desires of the project creators. But they must not blindly implement the specification they’ve been handed. They must not forget the creative element. HOUSE_OVERSIGHT_015959

270 Are the Androids Dreaming Yet? The Role of ‘Process’ in Creativity We hear a lot about ‘process’ when developing software and other creative tasks. The first thing to realize is process does not write software and every moment spent on process is a moment not writing software. Excessive process can bring the productivity of the average programmer down from a thousand lines per day to one. On the other hand, we all know that using no process to write software results in useless software. Good solo programmers, playwrights or composers are surrounded by lists and post-it notes full of process. Where is the balance to be struck? In my view ‘process’ is there to help humans with the tasks we find naturally difficult. Humans, as we know, are dreadful at remembering lists of symbolic information. Give a human ten numbers to memorize and they will quickly forget them. Give Microsoft Excel ten numbers and it will remember them forever, or, at least, until your next upgrade! So the first job of process is to collect lists of things and sometimes even lists of those lists. Another significant affliction affecting humans is procrastination. We tend to put off decisions. Process can set waypoints; when will the job of splitting a project occur, when will we begin the test, and so on. The third job of process is to keep track of the division of labor — if the project has to be divided. Who will do what? Essentially we are back to lists again. The most important job of process, in my view, is to keep track of scope. ‘Logical scope creep’ when unrecognized destroys software projects. Scope creep is fine if it just adds more linear work. “Could we add three more product types?” “Could you do another language?” “Can you make this interface prettier, less cluttered?” It may cause a busy team to groan, but it does not damage the integrity of the design. To put it back in Brooks’ language, accidental creep is fine — provided you add some resource. Essential creep is not. Adding the french language prompts to a project in English might be fine, putting language translation into a project may be a step too far. The project may have strayed into a different logical class. Increases in logical scope often require redesign, you must stop and re-architect if you are to avoid bugs in plague like quantities. If programming software is a creative task, how can we help improve productivity? The most important factor is to provide uninterrupted peace and quiet. Programming is a task where people need to hold many ideas in their head at the same time, and this requires deep concentration. To get some idea of the creative process at work, listen to the excellent TED lecture by John Cleese. HOUSE_OVERSIGHT_015960

Software 271 A common and costly mistake is to put off thinking about a class of things you are going to need in the next release because of time pressure. ‘Time out, that’s for the next release’ and similar statements spell disaster for the future of a project as when you come to the next release, you may have to rewrite much of it from scratch. This is why good architects are so valuable. They anticipate the future even when they are told to ignore it and ship now! Just as there are artistic geniuses, there are programming geniuses. Hold onto them if you get one. They are rare. We don’t know if they can be made or they are lucky accidents, but statistics shows that some people are 1000 times more productive at writing code than the average. If you can find lots of them and make them work together you will build the next Google or Facebook. If you have a tight deadline, a super- programmer may get you out of a hole, producing in a week what might otherwise take a year. Remember your great programmers will most prolific if you can get process and distraction out of their way. Just make sure they have a clear idea of purpose. Laws A programmer interrupted eight times a day does no work. A creative person interrupted eight times a day does no work. Programming is a creative endeavor. There are creative geniuses. Hold onto them. Bugs save us from collapsing space-time when we are lazy and try to use mechanical means rather than creative thought to write software. HOUSE_OVERSIGHT_015961

HOUSE_OVERSIGHT_015962

Chapter 12 HYPER-COMPUTING What’s in a Brain HOUSE_OVERSIGHT_015963

, ff i 14: ry — | i (-s Mu r i er <1 i i | : ‘i: _— Wy : —— = _ A Hye veling ithe ped fh, eadlights, hi an does smpthing} ‘ppens Stephen Wright HOUSE_OVERSIGHT_015964

f you believe humans outthink computers, be warned; you are in controversial territory. This would need a hyper-computer and many scientists speak of these in the same breath as perpetual motion machines. I’m not sure it’s an entirely fair analogy. We understand machines, and the physical laws of our Universe forbid perpetual motion. We don't understand brains, so we can't reasonably dismiss human hyper- computing. Humans commonly demonstrate one clear example of thinking which appears to break the Turing limit, namely finding solutions to mathematical puzzles. We need an explanation for this. Let me take you on a whistle-stop tour of all the schemes people have imagined that might lead to a hyper-computer. A hyper-computer is a machine that can calculate a function which a Turing machine can not. For example, when given a number denoting a problem such as Fermat’s Last Theorem, it can give me in return a number representing a valid proof. We are not concerned here with speed. We are talking about fundamental ‘do-ability’ Such machines are often dubbed ‘super-Turing’. Epic Fails Let us first look at some proposals that blatantly fail. My children call these ‘epic fails, and they are the perpetual motion machines of the hyper-computing world. Could we run many Turing machines at the same time, perhaps even an infinite number? Then we would have a much more powerful machine that must beat the Turing limit. The answer is no. Turing machines are already infinitely powerful and we know from our chapter on infinity that all countable infinities are the same. Infinity plus infinity, infinity times infinity, infinity to any power; all are equal. One single, fast, one-dimensional machine can simulate them all. We get no greater power with an infinite number of similar machines. The next technique which might realize a hyper-computer is to have a machine which simultaneously runs every possible branch in a program. Each time the machine gets to a point where there is a binary decision, it can take the ‘yes’ branch, spawn a copy of itself, and run the ‘no’ branch as well. Logically this machine should be able to calculate anything since it tries every conceivable option. The process is called non-determinism. This doesn’t mean the computer has free will. It just means the computer never chooses one option over another. It just HOUSE_OVERSIGHT_015965

276 Are the Androids Dreaming Yet? assumes each could be correct and travels down both. Solving a problem using a machine like this can be fast. The problem is this machine has no greater power than a regular Turing machine. Let me show you why. A non-deterministic machine is essentially the same as a single Turing machine; each time there is a branch in the program you would start running two processes. The first process works on every even tick of the computer clock and the other on every odd tick. Now we have a single machine running two branches at the same time. Using this trick over and over again, a single machine can run a program exploring every possible branch. Although it generates an enormous number of branches and takes a huge time to run, it is still a single machine and we have an infinity of time on our hands. Therefore, the machine is limited as before. We are not doing well so far and we have already exhausted an infinite number of options! Let’s try a different tack. We know true randomness is non-computable, the sort of randomness generated by the Lavarand we examined earlier in the book. Might this help? Truly random processes can’t be simulated by a computer. If we throw this into the pot might it let us compute something a Turing machine cannot? Again, no. This idea still only generates a machine as powerful as the non- deterministic machine above. A non-deterministic Turing machine runs every possible program. All a random one does is choose some of the same paths at random. It, therefore, can’t be any more powerful. The one difference is that it can generate non-computable numbers. However, the only interesting characteristic of these numbers is they are truly random and this randomness was an input. Their presence does not make the machine any more powerful. There are quite a few proposals for hyper-computers that are just cleverly dressed up versions of the machines we have already met and dismissed. For example, it has been proposed the Internet could form a super-Turing machine. This is known as a site machine because the processing is distributed across many sites linked together through the Internet. It is proposed each site could act as an oracle to the others. This is quite an elegant idea, and some proofs have been offered that show such a machine is capable of generating non-computable functions. The problem with this idea is that you can simply draw an imaginary line around the whole site machine and it looks exactly like a big Turing machine. There is no conceptual difference between such a machine and a regular computer with subroutines. After all, that’s in Turing’s HOUSE_OVERSIGHT_015966

Hyper-Computing 277 original proof. Again we have reached a dead end. We need something qualitatively different to a traditional computer in order to break the Turing limit. The obvious place to turn is the quantum world. Quantum Computers Quantum computers have had an extraordinary run in the press recently. It has been variously claimed they offer limitless computing power and can break all known security schemes; cracking, for example, the prime factors that form the basis of public key cryptography. This is big news. These codes are used to protect all the financial transactions we make on the web. Ina regular computer, bits of information are processed by switches that make simple ‘yes’ or ‘no’ decisions. In a quantum computer each switch can take both the yes and no branches, at least fora short time called the decoherence interval. The calculations are said to be superposed. This allows a quantum computer to calculate exponentially, rather than linearly, as the number of logic gates increases. Grover’s algorithm and Shor’s algorithm use this superposition to speed up factoring numbers and looking things up in databases, respectively. Grover’s algorithm gives us the ability to find something stored ina random place without having to look in every box. If you think about a standard search, say for your lost car keys, you must look everywhere to guarantee finding them. It does not much matter in what order you do it. When you are halfway through the search, you will be 50% likely to have found your keys. But, with a quantum computer, you can be fuzzy and look in many places at once. A quarter of the way through a quantum search, you are 50% likely to have found your keys. That might sound like a small improvement, but when working with very big numbers, it makes an enormous difference. Shor’s algorithm works a little differently and, yes, it does allow a quantum computer to break Internet encryption, so the newspaper headlines are true up to a point. Some time in the future we will need to move to a more secure type of encryption. The largest quantum computers today can process 300 qubits at a time or remain ‘coherent’ for about two seconds. These results are pitifully low. The largest prime number factored so far is 143, a mere 7 bits long! By way of comparison, internet security routinely uses 1024 bits. But, quantum computers are improving exponentially faster than classical computers: They really do change the rules of the game. If you remember our discussion of chess, the quantity of space needed for a HOUSE_OVERSIGHT_015967

278 Are the Androids Dreaming Yet? calculation can be the limiting factor. A quantum computer is very space efficient. When the computer branches and makes a copy of itself, it does so without needing more space. There are two theories for how it does this, (well, three, but the third is highly controversial). The first theory is the computer doesn’t need the space because it hasn't made its mind up yet; somehow the calculation floats in an undecided state. The second is that the computer puts a copy of itself in a parallel Universe each time it branches. When the calculation is over, either all the Universes collapse to a decision, or every possibility is chosen in some Universe or other and they all go on their merry way! This is the ‘many-worlds’ interpretation of quantum mechanics and we will return to it later in the book. We have now explored all the straightforward ways to make a hyper- computer, and all have failed. We need something still more exotic. More Horse Power Needed Is there anything more powerful than a Turing machine? Yes, in theory, there is. The first person to explore ways of breaking the Turing limit was Turing himself. He cut right through the problem by proposing the existence of an oracle function. At any point in a computation, you could ask this function a question and it would give you the right answer. We must leave completely aside the question of how this wonderful oracle function is constructed. All we know is it can’t be a machine. If it really existed, a Turing machine that was able to consult it would be able to answering any question you put to it. That is a hyper-computer. Unfortunately having access to such an oracle does not get us far. We can use it to compute numbers we could not otherwise have obtained — or answer a single question — but it does not give us a general-purpose way to solve further problems outside of the logical area we asked it to answer. Each time the oracle answers a question we break the limit a tiny bit. Each question and each answer moves us forward, but does not give us something universally applicable. If I ask the oracle to prove Fermat's Last Theorem it will give me that answer, but this does not turn me into a creative mathematician, able to prove any other theory. You can test this by typing a mathematical question into the Google search box. Does obtaining an answer make you better at mathematics? In any case, an oracle is not and cannot be a machine, so it does not lead us any further in our quest to build something super-Turing. HOUSE_OVERSIGHT_015968

Hyper-Computing 279 The Weird and Wonderful There are some really weird and wonderful proposals for machines capable of super-Turing thought. Let’s take a bit of a flight of fantasy. If we could make a spaceship survive the inhospitable environment near a spinning black hole, it might be possible to send information backward in time. We could see the answer to a calculation before we had to go to the trouble of calculating it in the first place. 1 i j Black Hole Malament-Holgarth Space HOUSE_OVERSIGHT_015969

280 Are the Androids Dreaming Yet? David Malament and Mark Hogarth of the University of California, Irvine have proposed a form of space-time called the Kerr Metric. This allows a machine to break the Turing limit, but has the drawback that as it does so it falls through the event horizon and is sucked into the black hole. We might discover new information but are now trapped inside the event horizon unable to communicate it — a form of cosmic censorship. Candidates for a hyper-computer that could fit inside a human brain include mathematical curiosities which stretch the concept of infinity. The easiest to understand is the Zeno machine. In a Zeno machine a computer runs each successive step of a calculation in half the time of the previous step. The computer can pack an infinite quantity of computation into each finite time interval and can therefore outperform a Turing machine. This theory fails at a practical level because we simply cant build such a machine. There are numerous weird suggestions for mathematical super- Turing machines, and many are described on the Internet. They all fit broadly within the two models above: modifications to space-time or peculiar mathematical paradoxes. The inspiration for the true solution to super-Turing thought may lay in there somewhere, but there are some more plausible proposals to look at next. Plausible Ideas I have characterized the next set of ideas as plausible, but they may still be highly controversial. My only criteria for plausibility are that the mechanism must outperform a machine limited to counting numbers, and it might fit inside our skulls. No black holes allowed. One interesting proposal for a super-Turing machine that could fit inside our skulls is the Adaptive Recurrent Neural Network, ‘ARNN’ proposed by Hava Siegelmann of the University of Massachusetts, Amherst. An ARNN is a neural network with real number weights. As you recall, real numbers are equivalent to the continuum infinity, a larger infinity than that of counting numbers. This is the infinity that defeats a Turing machine, and Siegelmann harnesses it as the basis of her computing machine. She argues that, although the machine cannot be programmed as it is impossible to write real numbers down, once it is running, the weights diverge and real numbers will be used within the network. These real numbers allow the machine to compute using numbers that are not, themselves, computable HOUSE_OVERSIGHT_015970

Hyper-Computing 281 and this is where the machine's greater power comes from. Of course such a thing might easily fit inside our skulls, and the physics within our brains are certainly capable of using real analogue values. The biggest stumbling block for Siegelmann’s idea is the information that gives her machines their power is fine-grained and easily destroyed by noise in the environment. This is not just from the sort of electrical noise we hear when our cell phones interfere with the radio, but the precision required by her machines is so exacting that anything might interfere with them. For example, gravitational waves caused by the motions of nearby stars would disturb calculations at only the fiftieth decimal place. Since it is these digits that constitute the difference between an ARNN and a regular Turing machine, most people conclude ARNNs can’t work. There is one effect stemming from the quantum world which might come to the rescue. The potential to do something in the quantum world is sufficient to modify the behavior of a system even if the system does not actually do that specific thing. This is called a counterfactual process. The possibility an ARNN might perform infinite precision calculations may be enough to give the machine the edge, even though in practice it is disturbed by noise. This is speculation upon speculation, but interesting nevertheless. \) Dendrites (S) Microtubule Neurofibrils = SET Synaptic vesicles , Neurotransmitter a) Synapse (Axoaxonic at - Synaptic cleft Axonal terminal ~ Rough ER (Nissl body} Palyribosomes Node of Ranvier Ribosomes Golgi apparatus Myelin Sheath (Schwann cell) Nucleus Nucleolus Membrane Microfilament _ ~Microtubule ™ Axon Dendrites Neurons and Microtubules HOUSE_OVERSIGHT_015971

282 Are the Androids Dreaming Yet? Roger Penrose is fascinated by such counterfactual experiments and is inspired to think such effects might have a role in non-computable thought. It is his ‘machines’ we will look at next. Penrose-Hameroff Machines, aka Brains Roger Penrose of Oxford University and Stuart Hameroff of the University of Arizona have proposed a very different way to understand the workings of the brain. They focus on the much smaller scale structures within neurons called tubulin microtubules. If you watch a brain form, the dendrites grow towards each other, twisting and turning rather like the growth of a plant as viewed in a slow motion nature film. This motion is controlled by micro-tubular structures formed of a protein called tubulin. Tubulin is made from peanut-shaped polar molecules that self- assemble into helical tubes with a radius of just seven molecules. The tubes bundle together to form the backbone of neurons. The peanut- shaped molecules are bipolar switches and can flip between two states. This allows them to bend into different shapes and, in the most extreme example, to flap fast enough to propel small organisms such as paramecia. It is also, interestingly, the protein that unzips the double helix when a cell divides, and so plays a fundamental role in our evolution. Penrose and Hameroff suggest these tubes form the true processing element in our brains. The walls of the tubes are formed of successive alpha and beta tubulin molecules. Each of the tubulin molecules can flip between two states, propagating a ripple along the tube wall. The scale is small enough for quantum effects to matter, and Hameroff suggests quantum error correction keeps the ripples from decohering too fast. Because the processing is happening at a molecular level rather than at the scale of a neuron, the brain would be considerably more powerful than a count of its neurons would suggest. They propose increased computing power would stem from three sources: There are many more tubulin molecules than neurons; the micro-tubes could perform quantum computation, and the micro-tubes are capable of non- computable, conscious, thought. Measurement of a quantum process is the only candidate we have for a non-deterministic physical process today; all other physical processes are deterministic. Penrose argues that quantum processing in the brain spontaneously collapses in decision making because of the interaction between quantum superposition and gravity. The arguments are put forward in two books: The Emperor’s New Mind and Shadows of the Mind. This theory remains controversial for two main HOUSE_OVERSIGHT_015972

Hyper-Computing 283 reasons. First, most people see no need for super-Turing thought. They believe computers are sufficient. Second, they believe the brain is not a hospitable place for quantum effects: it is too hot and too chaotic. Indeed, until recently people assumed quantum effects would have no place in biological entities, but this orthodoxy has recently been overthrown by the discovery of quantum processes in photosynthesis. The paper by Travis Craddock of Nova and others suggests there may also be quantum structures in the neurons of our brains and we might possess quantum computers after all. But, remember, Penrose and Hameroff don't only need quantum coherence within our brain to explain consciousness. They also need gravitational effects. HOUSE_OVERSIGHT_015973

HOUSE_OVERSIGHT_015974