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 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 ↔vark. This solution is obvious; just do the substitutions and you are there. But what if the rules were a little more complex? Gennadií 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. 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 α, β, ζ, and so on. Let us Creative Inoculation 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 Software 261 Jackson 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 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 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 you’d 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 264 Are the Androids Dreaming Yet? 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 Software 265 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, ,SendMail. Before splitting a project between many people, it is worth considering whether you can give it to just one individual. To do this you 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. 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 268 Are the Androids Dreaming Yet? 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 Software 269 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. 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. 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 superprogrammer 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. Chapter 12 HYPER-COMPUTING What’s in a Brain Perpetual Motion from the 1600s “If you are in a spaceship that is travelling at the speed of light, and you turn on the headlights, does anything happen?” Stephen Wright If 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 hypercomputing. 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 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 nondeterministic 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 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. In a 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 for a 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 in a 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 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 hypercomputer, 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. 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. Black Hole Malament-Holgarth Space 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 can’t 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 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. Neurons and Microtubules 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 selfassemble into helical tubes with a radius of just seven molecules. The tubes bundle together to form the backbone of neurons. The peanutshaped 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 noncomputable, 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 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. Chapter 13 HYPER- COMMUNICATION World Wide Communication “The single biggest problem in communication is the illusion that it has taken place.” George Bernard Shaw Each Christmas I buy the Private Eye annual (an English satirical magazine) only to be slightly disappointed when much of the humor falls flat, yet I can watch the TV current affairs quiz ‘Have I Got News for You’ featuring its editor and be reduced to tears of laughter. Being at a live recording of the show is even more powerful. Why is this? Why is the experience and effect so different? Is it just the sense of occasion when I go to a live show or is there something more to shared experience? We appear to learn more from lectures delivered in person than reading the lecturer’s book, or even watching the same lecture recorded on video. Studies show children who are read to by their parents do better than if they are left to follow along with a CD. Two groups of children were tested on two made-up words used in a story. The children read to by their parents had an 80% recall rate, while children who followed the CD only 17%. This is a big disparity. The simplest explanation is that the children who were read to pay more attention. Are there other effects? IMAX 288 Are the Androids Dreaming Yet? Most scientists believe communication between humans is classical: words spoken in proximity have no more power than had we carefully written out what we wanted to say. Body language and tone of voice are simply useful tools to aid the transmission of this information. I’m going to explore the ways in which human face-to-face communication might exceed this traditional classical model. Let us look first at the bandwidth of communication between people. Bandwidth Let me give you a mental picture for what I mean by bandwidth. Imagine I am sitting in a darkened theatre enjoying one of my favorite comedians at the Edinburgh Festival – the biggest arts festival in the world. I phone a friend who is also a fan and let them listen in. Perhaps I even use the camera and surreptitiously point the phone at the comedian. My live experience is digitized, compressed and transmitted over the mobile network to my friend. He gets the same experience but at much-reduced bandwidth. My friend has a similar but qualitatively different experience to mine. He cannot hear the degrees of loud and soft I hear, nor the full range of high and low frequencies forming the timbre of the comedian’s voice; no sense of the smell of old armchairs or the heat of the audience around me. He is spared the strange stickiness my shoes meet on the floor of the auditorium and the occasional slosh of beer that hits me from a slightly inebriated neighbor. For the person at the other end of the phone, their view is of a tiny two-dimensional screen about 4 by 3 inches square. Of course, they can enlarge the picture, but then the pixilation dominates and it looks like an impressionist picture viewed close up. He has nothing like the same intensity of experience. Loss of bandwidth is something we can study mathematically and the reduction is enormous. Video and Audio The image of the comedy show is digitized by the camera and microphone; the video at 384,000 bits per second and the audio at 64,000 bps. Mathematical compression will be applied and the video will shrink to 30,000 while the audio drops down to 4,700. After compression, the whole experience amounts to around 40,000 bits per second. To put it in some perspective, a DVD would be 11.5 million bits per second, nearly 300 times the bandwidth. Hyper-Communication 289 My in-person experience has much higher bandwidth than even a DVD. It may even have infinite bandwidth. Physicists argue whether space-time is quantized but, for now, we will look at what would be needed to reproduce the experience faithfully on modern digital recording equipment. Digitization When something is converted to digital form, it goes through a number of steps. First, some way must be found to chop the thing into small parts in space and time. Then each of these parts is sampled with a sensor to give an electrical signal and, finally, this signal is measured and turned into a number. Old microphones used carbon granules. As the sound waves passed through them, the granules were shaken and made better contact with each other. Connecting a battery across the granules gave a varying voltage. Modern microphones use a variety of technologies. The preference of most recording artists today is the electret microphone. A coil moves inside a magnet generating a varying voltage which is translated into a voltage as before. Next we use a fast running clock and measure the voltage on each tick giving us a sequence of numbers. We have created a near perfect record of the sound, and we can prove this by recreating the sound through a loudspeaker. This is what happens every time you listen to your iPod. To digitize film, each frame must be split in space as well as time. On each tick of the clock, a process scans left to right and top to bottom to form a one-dimensional stream of numbers that records the image. The system cuts the picture up into little elements called pixels, standing for picture elements. Each small square has its average color measured for red, green, and blue content coded as a number. Digitization techniques have become the dominant way electronics work in the home, and digitization circuits are now ubiquitous. Reality How big is reality? Setting aside for a moment the problem that it might be infinite, we need to reproduce all the elements that go to make it up. A normal DVD has an image of 720 by 576 pixels with 16 bits of color depth and a frame rate of 25 frames per second. The eye, however, is considerably better than this and a DVD does not fool it. HD video 290 Are the Androids Dreaming Yet? is 1900 by 1000 pixels with 32 bits of color depth and 100 frames per second. This is a great deal better – if you enjoy watching sport or nature documentaries, the additional resolution is amazing. This still falls far short of reality. An IMAX theatre gives a wrap-around image of about 10,000 by 7,000 pixels and comes closer to the average resolution of the human eye, estimated at about 30,000 by 20,000 pixels. But the eye cheats. It concentrates the rods and cones in the central portion of the retina. Although IMAX achieves the average pixel density of your eye, it comes nowhere near the peak density which is nearly 10,000 times greater. For a truly equivalent experience, we would need about 320 million pixels per eye at a frame rate of 120 frames per second, allowing us full stereo synthesis. At this speed and resolution, we are matching the visual acuity of the eye and should be able to fool it completely. But there is one more problem to overcome: The image is not interactive. Move your head in the real world and the image will change. The objects in the foreground will vary their position in relation to the background, socalled motion parallax. Try it now, move your head and you will see that the book, or screen you are reading moves in relation to the background. In a simple digitized 3D image this will not happen. You will have a 3D image but you will not have a real image, a light field. To create a real image you need to view a hologram or use headtracking technology. A hologram records the light waves given off by an object in multiple directions rather than just the intensity of the light striking the camera through a single focal point. When you shine a laser back through the hologram, it regenerates the light waves as they would have originally come from the object. That light can be viewed from different directions, giving the impression of three dimensions rather than a mere two-dimensional photograph. There is often a limitation in viewing angle because the original photographic plate must wrap all the way around an object to capture the full 3D light field, but the illusion is very convincing. A more effective way to create a real experience – and one with no restriction on viewing angle – is to construct the image in a computer and track the movement of your head. The computer can create the two-dimensional images each eye would see if the scene were truly three-dimensional. Computer software resolves motion parallax and a host of other elements, but to do so the computer must understand a model of the world so it can calculate how the scene would look from a particular angle and in the appropriate lighting. Some recent games such as Activision’s ‘Call of Duty’ do this, and the experience is compelling. Hyper-Communication 291 Hologram There are still problems. The image is stereo but planar. All the light coming into your eye comes from the screen a meter or so away. In the real world objects need you to change the focal length of your eye to bring them into sharp focus depending on their proximity. Try looking at your hand as you move it towards and away from your face, too close and your eye can’t pull focus any further and it will blur. This mismatch between focal depth and the apparent distance implied by motion parallax is one of the reasons you can get headaches watching 3D images. There is something not quite right about them and your eye has to learn a new behavior. Audio Field Our poor friend at the end of the phone is listening to a mere 4700 bits per second rendition of the comedian. A compact disk is 64,000, 16- bit samples per second in stereo, over a million bits per second. So the information content of a mobile phone call is very low. It is a miracle you can understand speech at all over such a narrow channel, but this is made possible by two factors. First, human speech uses a limited range of frequencies. All the information in our voices lies within about two octaves centered on middle C. And, second, you can perform some 292 Are the Androids Dreaming Yet? clever mathematics to generate speech from seed information. For a given speaker the vowel ‘a’ might be 20% middle C, 50% F and 25% A, with a few other things thrown in for good measure. We can transmit this information and ask the computer at the other end to re-synthesize it. This is what happens when you listen to someone on a modern phone. You do not hear their actual speech, you listen to a computer synthesizer make a near approximation. CD is no longer the gold standard for sound. Professional audio has standardized on 24 bit recording which is probably far beyond the limit of the human ear. An audio soundtrack is doing a good job at 2 million bits per second. Sitting perfectly still in the middle of a room, each ear will pick up a different signal if the source is not directly in front of us. The two ears on a human head face a little forward, and the hair on your head slightly absorbs sound. We can calculate the source of the sound by the slight difference in the times at which it strikes each ear, and the variation in frequency content. We can use these two pieces of information to determine the direction from which a sound is coming. It was useful for our ancestors to be able to tell where the saber-tooth tiger was hiding. We can gain more accurate information by turning our heads from side to side. The differences in frequency and timing should vary as we do so and we gain a little more data to perform the calculation. If we walk through the room we sample yet more of the soundscape and this can be used to pinpoint the exact location of the source. As we move, we expect the sounds we hear to change subtly according to the mental model we use for locating objects in the soundscape. To give the illusion of a soundscape modern systems use multiple microphones to capture the sound, so it can be reproduced on multiple speakers. Ideally, we would record a hologram of the sound but it is possible to record on thirty or so microphones and mix the tracks down to 5 or more channels giving us the sound experience we now expect at a modern cinema. What is the Bandwidth of Life? We have not yet talked about the other senses; smell, vibration, temperature, balance, wind chill, and touch. In all, there are over 25 senses that must be stimulated accurately to simulate reality. Just think for a moment how much information must be replayed to reproduce the sensation of bungee jumping off a bridge in the jungle or taking off into Hyper-Communication 293 space, or giving birth. To digitize life completely, we need to stimulate every relevant nerve ending in the human body in real-time – skin, ears, eyes, balance, pain centers, and so on. At the low end, a ‘perfect’ IMAX production would require 360 degree stereoscopic projection and the generation of a full sound field. This would take 3 Gigabits per second for the audio field and 5,600 terabits per second for the video field. This could be substantially reduced if the person wears virtual reality glasses to track their head and eye movements, but then you are substituting resolution with computer power. At the high end, a team at the US Department of Energy’s Fermilab estimate reality needs one hundred trillion samples per inch for a ‘simple’ quantum representation. If we look at the many worlds view of quantum mechanics, each photon hitting our eye can’t be fully described by a single number. The photon may be entangled with other realities we should keep track of. This causes our picture of reality to become wildly complex. Everything we might see and experience is in some way a combination of possibilities, and these possibilities all interact. Real life is very complex. Symbolic Communication Computers have no concept of an in-person meeting. They communicate using purely symbolic methods in binary numbers. These have the same meaning whether communicated over a short piece of wire or using a fiber optic cable half way around the world. Computers never have to communicate understanding to each other because they use programs and a program can be perfectly transmitted. Body language is, of course, completely alien to them! We know there are non-computable things; functions, numbers, musical melodies, and mathematical puzzles. Why would there not also be a place for non-computation in communication? David Deutsch has suggested human creativity is used to guess the ‘program’ running in someone’s mind, and evolved so we can learn skills. Instead, might faceto-face communication be important because it lets us impart knowledge in a non-symbolic manner? Hyper-communication As with hyper-computing, hyper-communication is controversial. We instinctively know human communication is very different to computer communication. Face-to-face communications have a qualitatively 294 Are the Androids Dreaming Yet? different feel to them. My question is this. Is there more to face-to-face communication between human beings than the simple exchange of symbolic information? Let us propose an experiment. I erect a 3D screen with a hi-fi surround sound system in a university lecture hall and deliver a lecture to a camera in the adjacent hall. Half the students see the lecture directly, and half remotely. With modern screens, it might be possible to set up the experiment so well that is difficult to tell which hall I am actually in. Is the experience of the remote students the same as the ones sitting in direct proximity with me? Do mirror neurons fire more strongly and pick up more information when you see me in the flesh, or is the feeling that a lecture is better when you are ‘physically there’ an illusion? You are perhaps less likely to fall asleep in my lecture if you are physically there because you are afraid I might walk over and hit you! What possible nonclassical effects could be in play when you see an event or communicate in person that might make the communication different? Here are two potential differences: Information in a face-to-face encounter is continuous, not digitized. Continuous information is infinite in nature and does not have the finite limitation of digitized data. Of course, if we have digitized the sound at 24 bits and replayed it with extreme fidelity, there should not be any loss in information, but the interactivity of the soundscape is hard to simulate. Light entering your eye contains information that could be quantum entangled with the object you are viewing. You become part of the system rather than merely an independent observer. It is difficult to see why this would produce a different quality of communication but it is testable. Set up the lecture experiment and measure the quality of understanding communicated between the parties. If we believe our brains are super-Turing, then considering there might be some similar effects involved in human communication is not unreasonable, perhaps quantum effects play a role in communication. If we conclude our brains think classically, then we probably communicate classically. Chapter 14 CREATIVITY Thomas Edison, his wife and a Light Bulb “Creativity is allowing yourself to make mistakes. Art is knowing which ones to keep.” Scott Adams “Invention is 1% inspiration and 99% perspiration.” Thomas Edison “Creativity is just connecting things. When you ask creative people how they did something, they feel a little guilty because they didn’t really do it, they just saw something. It seemed obvious to them after a while. That’s because they were able to connect experiences they’ve had and synthesize new things.” Steve Jobs The ancient Greeks believed there was no such thing as creativity. Our job, as humans, was to look at the earth and discover things about it. When we looked at light passing through water or built a boat to travel on it, we were discovering, not inventing. Shipwrights did not invent boats they were simply building inevitable forms. Everything there was to know already existed, we just hadn’t realized it yet. Of course, Greek playwrights were busy ‘creating’ the first plays; tragedies, comedies and the like, but serious thinkers thought of them as documenting the human condition. It wasn’t until the Renaissance, 1500 years later, that humans began to appreciate that they create knowledge, and this started us on our quest to understand creativity. One of my childhood memories is sitting on the kitchen floor with a glass of water and surrounded by knives and milk bottles. I was trying to solve one of the problems from Edward de Bono’s book on lateral thinking, A Five-day Course in Thinking. De Bono, now in his 80s, is a prolific writer with over 60 publications to his name – all aimed at making us more creative. His books pose a series of practical problems, each needing progressively greater creative intelligence. The particular problem I was trying to solve was to balance a glass of water on knives suspended from four milk bottles. It took me after 2 hours. Steve Jobs shows the iPhone 298 Are the Androids Dreaming Yet? Except for De Bono there is not much written about creativity in books or on the Internet, but if you dip into the video archive, the discussion really opens up. Perhaps this is a feature of creativity; it’s easier to explain in person. Of course, I have taken on the writing task with this book but I have the benefit of modern day resources such as multimedia, interactivity, and the web. Some people appear to have creativity in abundance and the things they create are truly wonderful. I’m thinking here of Picasso, Einstein, Mozart, Edison, or Maxwell, but a precise definition of creative thinking is hard to pin down. Here are some generally accepted categories: Divergent Thinking The first sort of creative thinking we recognize is divergent thinking, often called brainstorming. This is the art of coming up with ideas – lots of them. A quick way to test your skill is to take a minute, and list all the possible uses for a paperclip. Try it! In 60 seconds write down all the uses for a paper clip you can think of. Time yourself. ddd Creativity 299 ANSWER WITHOUT READING ON This is the classic test of creativity developed by J.P. Guilford in 1967. It is called the Alternative Uses Task. You can try the task with many objects: bricks, chairs, even water. How did you do on your first attempt? 8 to 10 uses is about average, 20 is extremely good. It’s possible to teach most people to get near twenty and I’ll show you how to do this in a moment. Another test of idea generation is to draw 30 things in 30 circles. Thirty is such a large number it forces us to come up with some nutty ideas and break our natural tendency to self-censor. For example, I’d like you to create logos or logo ideas, for a new coffee company in your circles. The test is best done without a time limit so now is the time to break off reading and make yourself a coffee. Then come back and draw 30 circles on a piece of paper. Fill in the circles. MAKE A COFFEE, THEN START DRAWING. ddd The aim of brainstorming is to remove our inhibitions and get us to generate a mass of ideas. In normal life, we tend to suppress ideas even before we are consciously aware of them. Sir Ken Robinson has researched creativity in children and found the ability to brainstorm reduces linearly with age. At five or six, children given one of these divergent thinking tasks come up with many creative solutions: fold the paper clip into a dinosaur, and use it to attack your friends, get two and use them as chop sticks. As adults, we tend to disqualify ideas. You could never fold a paperclip that tightly or accurately, we said, “a” paper clip not two. But, you can fold a paper clip tightly, and the room you are doing the test in has thirty paper clips and thirty people in it so just team up with a friend. I never said this was a solo task! Do you see how you impose nonexistent rules on your thinking, particularly the implied rule of not working with others? I did not say this test was subject to examination conditions. The first twenty years of our lives teaches us to work alone on intellectual tasks, yet when we get to the workplace we can, and indeed must collaborate to succeed. Now you have an idea how to ace the paper clip test: don’t censor yourself and don’t imply rules I have not imposed! 300 Are the Androids Dreaming Yet? TRY THE PAPER CLIP TEST AGAIN! ddd Divergent thinking is rarely the final goal; it is rather a jumping off point for the creation of something new, like a solution to a mathematical puzzle, a painting, or a novel invention. The exercises allow us to explicitly see one of the early creative steps – idea generation before the pruning step. But most creative people often just create, they don’t follow a scripted process. The term ‘the creative process’ is a great misnomer. There is no process that actually creates. Process merely puts us in the right frame of mind to do so. Processes are useful for framing a problem and ensuring we have all the right tools at our disposal: good crayons, some nice art paper, a hot cup of coffee. But process must be put to one side at the moment of actual creation. Convergent Thinking Convergent thinking is the opposite of divergent thinking. It focuses on discovering the final solution to a problem rather than generating precursor ideas. Some creative people only use this method, avoiding laborious processes such as brainstorming. Tests of skill for convergent thinking generally pose puzzles where there is only one correct answer, but one that requires a non-linear step. Here’s a really simple convergent thinking puzzle to try. It only requires a piece of paper and pen. Draw a circle on a piece of paper with a dot in the center. It should look like this. Do NOT take the tip of the pen off the paper until you are finished. Creativity 301 TRY ANSWERING IN YOUR OWN TIME ddd Another famous, but clichéd, problem is of you to draw four straight lines through these nine points without lifting the pen from the paper. Can you do it? TRY ANSWERING IN YOUR OWN TIME ddd I won’t put the answers here, or even a hint. It’s quite famous and many of you will be familiar with them. The answers are buried on the website, and for those of you who already know the solution, there are some alternative problems. If you can’t immediately solve a problem, think about it overnight. It’s worth seeing what your brain will do while you are asleep! The Science of Creativity The first person to theorize about the creative process was Graham Wallas, the co-founder of the London School of Economics. In his book The Art of Thought, he proposed a five-step model for creative thinking. First preparation, when you become fully acquainted with the problem and its domain. Then incubation; walk the dog or make a cup of tea. After the meditative incubation phase you may get a gut feeling that a solution is on its way. Wallas called this third step intimation. It’s left out of many modern versions of his theory, but I think it’s an important step. Shortly 302 Are the Androids Dreaming Yet? Eureka after this you get that Eureka moment – illumination or insight where the creative idea bursts forth into your conscious awareness. The idea must finally be verified. Many of our ideas will turn out to be mistakes, but that’s part of creativity. In the nearly hundred years of investigation since Wallas proposed this theorem, we have not moved much further forward in understanding creativity. Alan Turing described his thoughts on the science behind creativity in a short piece he wrote about decision making: “When making a decision of minor importance, I have always found it advantageous to consider all the pros and cons. In vital matters, however, such as the choice of a mate or a profession, the decision should come from the unconscious, from somewhere within ourselves. In the important decisions of personal life, we should be governed, I think, by the deep inner needs of our nature.” Creativity 303 Later in his career he came to believe machines would become intelligent and this sort of intuitive thinking could be effectively performed by a computer. As you know, I don’t agree with his later viewpoint. Another person who has thought long and hard about creativity is John Cleese, the comedian and actor. He describes the process wonderfully in a number of talks which you can find on YouTube. He finds a lot of his creativity emanates from his unconscious rather than conscious thought processes. To optimize this he needs large uninterrupted blocks of quiet John Cleese on Creativity 304 Are the Androids Dreaming Yet? time. Often, if a problem seems impossible, he will sleep on it. When he wakes the next morning, he will frequently find the problem has solved itself and a solution is ready at hand. Art The final class of creative thinking we generally recognize is artistic skill. This is probably a form of convergent thinking, except both the problem and the solution are open. Good artists are considered highly creative and most people tend to agree on what constitutes good art. There are some arguments but they are usually more about genres. I might not appreciate modern installation art, even to the point of declaring it, “not art.” But, when forced to ignore their prejudices most people tend to agree on the distinction between good and bad. Painting, sculpture, music, architecture and poetry are the traditional fine arts. There is often some argument over architecture: is it not too ‘functional’ to be considered an artistic endeavor? After all, art is not supposed to have any purpose other than to be, well, art. This definition inevitably leads to arguments about whether bad art is still ‘art’. Art should be artful and how do you arrange a pile of used tires artfully? But this is a very narrow definition. I prefer to define art as something that provokes an emotional response in the beholder. Using this definition, the fact that a pile of tires disgusts and annoys you is exactly the point. Perhaps a more ‘enlightened’ viewer than you is intrigued by the clever use of materials. Regardless, we consider art to be a creative endeavor and we can measure it using the criteria of novelty and quality. Since most people agree on these measures for a given piece of art, we can use the wisdom of crowds to give us a scientific scale. That does not mean there won’t be art that you love but which leaves me cold. That is the joy of it. Novelty and quality are not the same as joy and pleasure, far less the tingle factor. ddd A quick test for artistic skill is to take a pen and paper and turn to the person sitting on your left and try to sketch them. TRY IT! Creativity 305 If you tried, you and your neighbor would probably find the results rather humorous. But, most likely, you did not follow my instruction. This is a form of social self-censorship. I asked you to do something rather difficult and embarrassing, but very creative and likely to enlighten you. Sadly most people – I am no exception – tend to censor their creativity for fear of embarrassment. Children, of course, do not sensor themselves as much as adults. Now you know how to be more creative. Find your inner child and don’t censor yourself too much! What Sparks Creativity As an inventor, I’m often asked what makes me creative. How do I do it? The answer is, I have no real process. After all, a process is mechanical and this entire book has been about exploring how creativity is a nonmechanical task. However, there are many things you can do to unleash your creative potential. New ideas are often sparked through linking disparate ideas. Expose yourself to as many ideas as you can, read widely, attend conferences, visit customers. Creativity requires peace and quiet. I personally get up early every morning. This gives me a good two hours of uninterrupted time every day. It’s also the part of the day when my brain works best. Others prefer to work late into the night. Pressure, for me and for many people, is a great incentive. Tales of the Polish Enigma code breakers, Douglas Adams’ writing deadlines and the fear of impending death in shark attack stories all force people to think in an accelerated way. This appears to help many people defeat the human tendency to prevaricate. On the other hand avoid panic. While a level of pressure can help, panic is unproductive. There is a sweet spot between having enough time to get properly acquainted with a problem and an impending deadline to force the crystallization of ideas. This balance varies from person to person and is something you need to test for yourself. You need time off. Once you have a well thought out idea, you may need to leave it alone for a while to allow your subconscious to work. Time off does not need to be two weeks at the beach. Charles Darwin and Benjamin Britten used to go for long walks. You can walk in Darwin’s footsteps at Down House in Kent. Others such as John Cleese 306 Are the Androids Dreaming Yet? like to ‘sleep on it’. Stephen Hawking distracts himself by working on a different problem for a while. Anything that avoids focusing directly on the problem itself seems to allow our creative freewheel run. Environment can be important. The campuses created by Steve Jobs for both Apple and Pixar are designed to foster creativity. The physical environments build team behavior but also cause people to bump into each other. Cross-pollination drives creativity. There are also some myths to dispel about creative people. Inventors are portrayed as eccentric and hopelessly disorganized, but Feynman kept notes of every idea he ever had. I have kept a series of notebooks, now computer based, since I left university. I still have almost all of these on a shelf at home. Creative people may be a little mad, but the successful ones are rarely disorganized. You must allow your brain to free wheel. J.K. Rowling has said the characters in the Harry Potter novels write themselves. I come to my computer each morning having not thought too much overnight and just write. Creation is just that; you must allow yourself to do it. It’s not a process. The Innovator’s Dilemma Why don’t big companies create? In 1997, Clayton Christensen of Harvard Business School wrote The Innovator’s Dilemma, the seminal work on creativity within organizations. In it, he shows us why established companies tend not to innovate and why startups exist. Christiansen’s academic research examines how companies handle discontinuous change in technology, focussing on the hard disk industry. You might not think this a very sexy sector. Microprocessors and game consoles would be more fun, but the great advantage with the hard disk is there is a single industry journal that has tracked the progress of every player over 30 years, collecting detailed annual data on every facet of their business. For an academic, this is gold dust. IBM invented the hard disk drive in their research center near Winchester, England. The first prototypes were, consequently, called Winchester Drives. When Christiansen examined the industry, he found something very strange. As the size of disks reduced first from 8” to 5¼” and then from 5¼” to 3½”, the dominant players in the previous era went out of business and new startups colonized the market. This fallout was not confined to a few small companies. It affected large, wellestablished, publicly-listed organizations, too. They failed en masse at each discontinuity. At first this made no sense to him. Surely a skilled Creativity 307 Hard Drives hard drive manufacturer would be the obvious group to construct the next generation. But it seemed that not only did incumbent players not construct the next generation, they ran their businesses into the ground while ignoring the technology discontinuity. Despite their legions of Ivy League graduates and business school MBAs, they all went bankrupt. As he looked around the economy, he found a similar pattern in other sectors. Minicomputer companies failed to make the jump to personal computers. Further back in time, buggy whip companies – in the Fortune 100 at the turn of the 20 th century – failed to make the transition to the motor vehicle economy. The only exception he could find was IBM. IBM had successfully navigated some transitions but at that time was fighting for survival as companies transitioned from mainframes to Linux based servers and their survival was in question. Why was this so? Christensen’s conclusion is that established companies tend to concentrate too much on their existing revenue streams while ignoring potential new ones. This is no surprise. When the disc drive industry made the move from 8” disks to 5¼”, the only customers for these new new smaller models were unheard of manufacturers of personal computers. Some were based in the dorms of MIT and Harvard – Dell and Compaq – not in the existing powerhouses of computing – Digital 308 Are the Androids Dreaming Yet? Equipment and Wang. New technology often underperforms the existing forms. 5¼” drives were slower, less reliable, and cost more per bit than their 8” predecessors but, of course, in one respect they were better. They were smaller and lighter and could fit in portable computers. The new technologies did a different thing in a different way, and overcame their disadvantages later. This chain of events is repeated many times over: Yellow Pages overtaken by Google, Borders by Amazon, Blockbusters by Netflix. Disruptive innovation changes the rules of the game as well as the pieces in the game. Christensen’s advice to companies is to separate your innovators from the existing business because their priorities will differ too greatly. Modern companies build entirely new divisions to create new products, or set up innovation labs to incubate ideas that would otherwise never get enough resources. Reward for Creativity There’s no doubt society values creativity very highly. One of the first tasks Thomas Jefferson undertook when he became President of the United States was to set up a patent system. He remained head of the patent office for over ten years. These days, the protection of creative Harold Cohen, Computer Art Creativity 309 ideas through patents, copyright, and trade secret is big business and combines to form the practice of ‘intellectual property’. Societies with the best protection of intellectual property are often the most successful. The USA is the unassailed leader, with Asian countries rapidly catching up. Poor old Europeans have struggled with an almost unworkable patent system for nearly 30 years; a genuine Europe-wide patent only came into effect in 2013. Creativity in the economy is now extremely important, and nothing emphasizes the point more than the job market. During the 60s finding a job was easy. There was an almost unlimited range of mechanical jobs on offer. In the post-industrial age, almost all the mechanical jobs have gone. Today we need to be experts in a field, able to solve problems creatively. You can’t expect to walk into a job and be profitably productive on the first day. Finding a job is harder and the cost of employing someone is greater. Why did we Evolve Creativity? Roger Penrose wonders why mathematical creativity evolved in humans since it only became useful in ancient Greece a few thousand years ago. He believes it must have been useful for something before this. But what? David Deutsch thinks creativity developed to allow one human to understand the thoughts of a fellow human being. We can’t precisely communicate the ‘programs’ we run in our heads. We are unable to download a detailed thought and put it on a memory stick. He thinks our creative capacity developed to help us pass skills from one to another. The ability to paint and sculpt is an accidental by-product of this adaption. It’s my view we evolved creativity to deal with new situations and puzzles in our daily lives. We use creative thought processes and ingenuity to come up with novel solutions for when we can’t rely on programming or a store of rules. Otherwise, the very first unforeseen situation could kill us! Computer Creativity Humans find creativity difficult. It requires peace and quiet, detailed study and input of caffeine. How does a computer fare? I have argued that computers cannot be creative above the logic limit, so this does not preclude them from creating within the narrow confines of a particular solution space. But a human still needs to set the rules for this space. The level of creativity we should see from computers is convincing within 310 Are the Androids Dreaming Yet? a limited conceptual area. Computers are not going to wake up one morning and decide to compose a breathtakingly beautiful symphony, but if we give them rules they can make a convincing version. Many computer systems have been designed to tackle creativity. We have already met the composer Emily Howell and Douglass Hofstadter’s computation program. Here are two more examples: Jape and AARON, which create jokes and art, respectively. Jape – Joke Analysis and Production Engine – is a program created by Graeme Ritchie and Kim Binsted. It generates puns, the sort of things you might find in an English Christmas cracker or children’s joke book. I’ll let the output speak for itself. Q: “What is the difference between leaves and a car?” A: “One you brush and rake, the other you rush and brake.” Q: “What do you call a spicy missile?” A: “A hot shot!” One of the most enlightening examples of computer creativity is AARON – refreshingly not an acronym. His machine is depicted here and you should look up some works on the web, such as Adam and Eve, and Aaron’s Garden. The program encodes rules about figures, objects AARON – Harold Cohen, Automatic Painting Machine Creativity 311 and perspective. Once coded the program takes off and is remarkably creative in its compositions, without any further human intervention. However, each new capability must be hand-coded by its creator, Harold Cohen. These paintings give a good visual interpretation for the sort of latitude imposed by the logic limit. AARON can do some very impressive things, but always in a mechanical – albeit beautiful – way, within the rules set by Harold Cohen, the true artist. AARON will not suddenly awake one morning and independently decide to experiment with the color blue! To give an idea of what I mean by ‘mechanical elaboration’ in a musical context, imagine you were using a Casio synthesizer. These machines have all sorts of fun settings. You can program them to play drum tracks, fill in chords, and add a jazzy, syncopated harmonization to your melody. But none of this is truly innovative. It’s mechanical elaboration of your artistic material. Jape, AARON and Emily Howell all do the same thing within their domain. They mechanically elaborate the artistic creation of their human masters. AARON does an extremely good job of this. The Myth of the Design Tradeoff An important consequence of the non-linearity of creativity is we are not constrained by tradeoff laws. Let me explain. Volkswagen Polo 312 Are the Androids Dreaming Yet? How often do you hear the phrase, “It’s down to tradeoffs,” or “It’s a matter of priorities”, or even “You can’t have your cake and eat it.” These stock statements misunderstand the infinitely complex nature of creativity and problem solving. Let us take a concrete example: the car. My first car was a Volkswagen Polo. It was a great little car, quite nippy, cassette-radio, and four seats. The most recent Polo has antilock brakes, airbags, NCAP 5-star crash resistance, smarter styling, and a low emission engine. Shall I go on…? The doctrine of tradeoffs says I would have to give up something to gain these new features. But, I have not. The newer Polo is cheaper in real terms than my original, as well as being better designed. Problems always have at least two dimensions of freedom. We can trade one feature for another or we can innovate to both have our cake and eat it! We are never constrained to simple on-the-one-hand, on-theother-hand type decisions. Creativity is unconstrained by linear rules and tradeoffs. Process versus Creativity How many times have you heard the words, “We must create a process for this!” In its place, process is good; It makes things consistent, repeatable and predictable. You can follow a process by rote without error. Processes are also easy to document and communicate because they are symbolic. But process is limited. It is, after all, a set of prescribed rules for solving a particular problem – and, because of this, it falls into the same trap. A process cannot solve a problem that requires creative thought or logic more complex than the logic limit. Logical processes are useful for tracking lists. I am reassured when I get on an airplane and know the pilot has been through a preflight checklist. I would not want to fly in an airplane where the pilot announced he was taking a creative approach to the preflight check. Process is a perfect tool for organizing the steps around being creative, but it won’t do the creating for you. Chapter 15 FREE WILL Dilbert Ponders Free Will “We have to believe in free will - we have no choice.” Isaac Singer “Time really is an illusion - lunchtime doubly so.” Douglas Adams child grows up in poverty, their father absent, mother a drug addict. Riots break out and the child defends the local convenience store. Another child born on the same road, but from a better background, loots the store and is arrested. This scene played out on the streets of London during the summer of 2011, but similar incidents happen all across the world. People choose different moral paths; one person makes a good decision; the other, a bad one. Did they make these decisions freely or was their behavior inevitable, dictated at the dawn of time? Free will is at the heart of our justice system. It requires a crime to be intentionally committed by a person of sound mind. If I kill you in an accident or because I am mentally incapacitated, I am innocent. Of course, if I mentally incapacitate myself with alcohol I would be guilty of manslaughter, perhaps even murder. Our justice system requires a crime to be intentionally committed by a person of sound mind. Whenever we see something bad in the world we trace the events back to the thought processes which led up to it. It seems we punish the decisions in our brains leading to a crime, not the crime itself. But, in a deterministic Universe my thoughts could never be at fault. They are inevitable. “The Universe made me do it!” You need not worry about the fabric of society falling apart in a deterministic Universe. The whole of existence will play out according to a predetermined script, complete with lawyers, trials, drama and pathos. The judge, jury and executioner would also have no free will. It would look as if you paid the price for the choices you made, but this would be an illusion. The whole thing would be like one enormous screenplay. The concept of determinism goes against our conscious experience. We all have a strong sense of free will. I certainly think I have it! And this presents a problem, because the classical laws of physics say our Universe is entirely deterministic, and that free will is an illusion. I should briefly mention ‘compatibilism’, a branch of philosophy that claims determinism is not at odds with free will. It argues that if I feel free and my actions do not appear constrained, then I am free even though my future might be inevitable: a sensation of freedom is sufficient. This seems rather feeble. I am seeking an explanation for how we might be truly free to choose our actions, not some linguistic trick to argue freedom is subjective. I believe true free will is a physical principle with observable effects on the Universe that would not be seen in a determined one. 316 Are the Androids Dreaming Yet? Domino Toppling Determinism To firmly grasp the idea of determinism let’s look at a fun example, domino toppling. If I arrange a set of dominoes on their edge in a long line and push over the first it will fall, knock over the next, then the next, and so on until all the dominoes have fallen. It is inevitable, and fun to watch. The same is thought to happen with particles in our Universe, albeit at a much smaller scale. The laws of physics governing these particles describe precisely what will happen as they interact. Our Universe could be thought of as a mechanical clock, wound and set at the Big Bang, or a fractal equation generating the wonders we see around us. When I push over the first domino it should be possible to capture all the information about the particles in the dominoes, my hand, the table, and the surrounding environment to precisely determine what will happen next. Will all the dominoes fall perfectly, or is there a break in the pattern – one domino just a tiny bit out of alignment – which will spoil the fun? All the information is there in front of me and I should be able to predict it perfectly. The laws of physics, as we understand them, are not only deterministic, they are reversible. This means if we know the position and momentum of every particle in the dominoes and the surrounding environment, we can extrapolate their motion back into the past. It should be possible to trace back the path of each particle to reconstruct the past history of the dominoes. If we were to cast a wide enough net, and collect all the available information, we could go back and see the events in the factory where the dominoes were made, or even see the trees that was felled to make them. We would need a lot of information and huge computing power, but we could do it! With a sufficiently powerful computer we could travel Free Will 317 back in time, albeit as a simulation, and relive past events. This would have no effect on the events themselves as it would be like watching a movie, but we could see every aspect of the past from any viewpoint. To perform this time travel trick for real, we would have to gather information from an enormously wide area. Information spreads out at the speed of light. One minute after the dominoes topple, the information about the event will have spread one light minute – that is over a sphere forty-million kilometers across – half way to Venus. An hour later and it would be outside the solar system. If you were to cast your net that wide, and gathered up all the information within the sphere, you could still perfectly model the moment when the dominoes were toppled. The wider you cast the net, the more information you have and the further backward in time you can travel. If you take the idea of collecting information to its logical conclusion you could gather all the information in the Universe at a moment in time. In 1814, Laplace put this idea in an essay. He proposed an immensely powerful being observes the position and momentum of every particle in the Universe. Armed with any snapshot of the Universe and the laws of physics, the entire future and the past of the Universe. The being was nicknamed Laplace’s Daemon and the idea has influenced philosophy ever since. If the Universe is predictable, our concept of time needs to be rethought. A common sense notion is that things in the future are unknown and things in the past are known. But, in a deterministic Universe a daemon or a supercomputer could keep track of all the information and tell you what is inevitably going to happen. The conscious feeling we have of moving through time would be just an illusion. Past and future have no meaning and there would just be a solid, permanent block of spacetime. If you stood outside the Universe and looked at this block of spacetime, everything that is going to happen and has already happened is set. This is sometimes called the Block Universe Hypothesis and is the logical conclusion of any theory that imagines an entirely determined Universe. One thing that seems to throw doubt on this Block Universe Hypothesis is our personal conscious experience of the world. We experience the Universe unfolding over time. (Of course, we could have this conscious experience in a determined Universe if someone had programmed it that way. All we can say is that it seems unlikely someone would go to the trouble of giving us a completely fictitious experience. There are an infinite number of possible Universes, why pick one where we think time flows, but it does not.) 318 Are the Androids Dreaming Yet? Uncertainty If you know a little of quantum mechanics you might imagine Heisenberg’s Uncertainty Principle comes to our rescue. Heisenberg’s principle is often misunderstood. People sometimes try to explain it as an experimental problem. If I want to measure the position of a particle I am going to need to shine a light on it. The photons I use to illuminate the particle will knock it out of position so the act of measurement disturbs the system. This is not the Uncertainty Principle. It is a different but related effect, called the measurement problem. The muddle is really Heisenberg’s own fault. When he tried to produce a layman’s explanation he used the analogy of disturbing the particle with the photon. This is wrong. A photon would not disturb a particle enough to explain the uncertainty we find; particles are fundamentally uncertain even before we measure them. Heisenberg’s Uncertainty Principle is a quantum property, which means it makes no sense and there is no analogy I can give you to properly explain it! Here is the closest thing I can find. Imagine I am playing a musical note on a guitar. You might want to know two things about it; where exactly is the string and what pitch, or note, am I playing? The problem with these two measurements is they can’t be stated at the same time. Pitch is dictated by the rate of oscillation over time: the number of times a string vibrates back and forth per second. Position is the exact location of the string at a given moment in time. If I state the position precisely this has no pitch because pitch needs a time interval. If I allow a time interval the string will move during that time and it won’t be precisely in one place. The best I can say is the string is about two millimeters above the fret board and two-thirds of the way across it. So, I hear you cry, this Uncertainty Principle means our Universe is not deterministic because it is uncertain. Unfortunately, the principle only prevents us from measuring the position and momentum of a particle at the same time, it does not prevent the Universe knowing the information it needs to allow the particle to go about its business in an entirely deterministic fashion. There is a perfectly reliable and predictable wave function that governs the motion of every particle, just as there is an entirely predictable equation for the motion of a string on a musical instrument. If both the classical and quantum laws of physics are deterministic where does the freedom come from to make our Universe nondeterministic? There is just one place to look: you and me. Free Will 319 The Observer I am looking out of my office window. It is a sunny autumn day and I have a beautiful view over London, but if I squint a little I can also see my reflection. The window in front of me is not perfect. Although it is mostly transparent, the glass also reflects some of the light. If you think of light as particles, the majority of the photons go through. But some bounce back. I’m going to show you that the behavior of these photons is governed by the observer – me! The laws governing light, and most of the strange and wonderful effects it has, were first stated by Isaac Newton. Newton was an extraordinary man. He discovered many of the physical principles we use today, and his view of the Universe reigned unchallenged until Einstein’s discovery of relativity. He was also, by many accounts, a nasty piece of work. Not only was he a famous academic, he also head of the Royal