# Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem

23 results back to index

pages: 210 words: 62,771

Turing's Vision: The Birth of Computer Science by Chris Bernhardt

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

The ACM named the award after Turing because he is considered as one of the founders of computer science. But why? What did he do to help found computer science? The answer is that he wrote a remarkable paper in 1936, when he was just twenty four years old. This paper is Turing’s most important intellectual contribution. However, this paper and its groundbreaking ideas are not widely known. This book is about that paper. The paper has the rather uninviting title, On Computable Numbers, with an Application to the Entscheidungsproblem. But don’t be discouraged by the title, because it contains a wealth of elegant and powerful results. It also contains some remarkably beautiful proofs. Turing wants to show that a leading mathematician’s view of mathematics is wrong. To do this he needs to study computation: What exactly is computation? How can we define it? Are there problems that cannot be solved by computation?

This idea is then extended to Turing machines: there are some Turing machines that accept their encodings and some that do not, but there is no Turing machine that can distinguish these two classes. This, in turn, leads to the the proofs that certain decision problems are undecidable. In particular, we prove that the halting problem and the acceptance problem are both undecidable. Chapter 8 The title of Turing’s paper is On Computable Numbers, with an Application to the Entscheidungsproblem. The connection to the Entscheidungsproblem has now been explained, but computable numbers have not. In this chapter we explain what these numbers are and the basic result concerning them. The chapter starts with Cantor’s idea of cardinality. We look at some basic, but surprising facts, about infinite cardinal numbers. Cantor’s diagonal and general arguments for showing two sets have different cardinalities are given.

However, we know that b is not on the list of computable numbers. The only conclusion is that the list of computable numbers is not something that can be constructed by a computer. If the list could be constructed by a computer, then b would be computable and we would have a contradiction. If it is not possible to construct the list by a computer, then there is no contradiction, so that must be the case. The title of Turing’s paper is “On Computable Numbers, with An application to the Entscheidungsproblem.” This title should now make sense. Turing wanted to show that Hilbert’s view of the Entscheidungsproblem was not correct. To recap: He first needed to give a definition of an effective procedure, or algorithm. This he did through his definition of what we now call Turing machines. Then Turing needed to find a problem that could not be answered by an algorithm.

pages: 523 words: 143,139

Algorithms to Live By: The Computer Science of Human Decisions by Brian Christian, Tom Griffiths

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

“a clever man would put the poison into his own goblet”: The Princess Bride, screenplay by William Goldman; 20th Century Fox, 1987. “anticipating the anticipations of others”: Attributed to Keynes in Gregory Bergman, Isms, Adams Media, 2006. it was the halting problem that inspired Turing: Alan Turing considers the halting problem and proposes the Turing machine in “On Computable Numbers, with an Application to the Entscheidungsproblem” and “On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction.” “poker players call it ‘leveling’”: Dan Smith, personal interview, September 11, 2014. “You don’t have deuce–seven”: This took place at the “Full Tilt Poker Durrrr Million Dollar Challenge,” held at Les Ambassadeurs Club in London, November 17–19, 2009, and was televised on Sky Sports. “only want to play one level above your opponent”: Vanessa Rousso, “Leveling Wars,” https://www.youtube.com/watch?

Tolins, Jackson, and Jean E. Fox Tree. “Addressee Backchannels Steer Narrative Development.” Journal of Pragmatics 70 (2014): 152–164. Tracy, Brian. Eat That Frog! 21 Great Ways to Stop Procrastinating and Get More Done in Less Time. Oakland, CA: Berrett-Koehler, 2007. Turing, Alan M. “On Computable Numbers, with an Application to the Entscheidungsproblem.” Read November 12, 1936. Proceedings of the London Mathematical Society s2-42, no. 1 (1937): 230–265. ______. “On Computable Numbers, with an Application to the Entscheidungsproblem: A Correction.” Proceedings of the London Mathematical Society s2-43, no. 1 (1938): 544–546. Tversky, Amos, and Ward Edwards. “Information Versus Reward in Binary Choices.” Journal of Experimental Psychology 71 (1966): 680–683. Ulam, Stanislaw M. Adventures of a Mathematician.

pages: 362 words: 97,862

Physics in Mind: A Quantum View of the Brain by Werner Loewenstein

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Woodbridge, CT: Ox Bow Press. 12. How to Represent the World The Universal Turing Machine Hofstadter, D. R. 1980. Gödel, Escher, Bach: An Eternal Braid. New York: Vintage Books, Random House. Trakhtenbrot, B. A. 1963. Algorithms and Automatic Computing Machines. Boston: D.C. Heath & Co. Turing, A. 1936. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society (2nd Series) 42:230–265. Turing, A. 1937. On computable numbers, with an application to the Entscheidungsproblem: A correction. Proceedings of the London Mathematical Society 43:544–546. Rendering the World by Computer Deutsch, D. 1985. Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society of London 400:97–117. Deutsch, D. 1997.

An unsolvable problem of elementary number theory. American Journal of Mathematics 58:345–363. Gödel, K. 1931. On formally undecidable propositions of Principia Mathematica and related systems I. Monatsschrift für Mathematik und Physik 38:131–198. Prigogine, I. 1980. From Being to Becoming: Time and Complexity in Physical Sciences. San Francisco: Freeman. Turing, A. M. 1936/1937. On computable numbers, with an application to the entscheidungsproblem. Proceedings of the London Mathematical Society Series 2 42:230–265 and 43:544–546. A Note about Reality Carroll, Lewis. (1871) 1982. Through the Looking Glass and What Alice Found There, Chapter VII. New York: Avenel Books. 14. Information Processing in the Brain Cell Organization in the Brain Braak, H. 1976. On the striate area of the human isocortex.

pages: 239 words: 64,812

Geek Sublime: The Beauty of Code, the Code of Beauty by Vikram Chandra

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Gnoli and Abhinavagupta, The Aesthetic Experience According to Abhinavagupta, XLIX. 30. Muller-Ortega, The Triadic Heart of Śiva, 46. Chapter 10: Application.Restart() 1. Muller-Ortega, “Seal of Sambhu,” 574. 2. “Fwd: Amar Chitra Katha Comics in Samskritam: Participate in Readership Survey—Google Groups.” 3. Singh, “New Life, Old Death for Sanskrit in Uttarakhand.” 4. Toole, Ada, the Enchantress of Numbers, loc. 2867–870. 5. Turing, “On Computable Numbers, with an Application to the Entscheidungs-problem (1936).” 6. Toole, Ada, the Enchantress of Numbers, loc. 2131–133. 7. Gleick, The Information, loc. 2048–052. 8. Cabanne, Dialogues with Marcel Duchamp, 18–19. 9. Fishwick, “Aesthetic Computing.” 10. Hessel, Goodman, and Kotler, “Hacking the President’s DNA.” 11. Kotler, “Synthetic Biology for Dummies, Investors or Both …”; Carlson, “The Pace and Proliferation of Biological Technologies.” 12.

New York: The Feminist Press at CUNY, 1993. “The International Obfuscated C Code Contest.” Iocc.org. Accessed February 3, 2013. http://www.ioccc.org/. Toole, Betty Alexandra. Ada, the Enchantress of Numbers: Poetical Science. Sausalito: Critical Connection, 2010. Kindle Edition. Torvalds, Linus. “Re: Stable Linux 2.6.25.10.” Gmane.org, July 15, 2008. http://article.gmane.org/gmane.linux.kernel/706950. Turing, Alan. “On Computable Numbers, with an Application to the Entscheidungs-problem (1936).” In The Annotated Turing: A Guided Tour through Alan Turing’s Historic Paper on Computability and the Turing Machine, by Charles Petzold. Indianapolis: Wiley, 2008. Urban, Hugh B. The Economics of Ecstasy: Tantra, Secrecy, and Power in Colonial Bengal. New York: Oxford University Press, 2001. ______. The Power of Tantra: Religion, Sexuality and the Politics of South Asian Studies.

pages: 372 words: 101,174

How to Create a Mind: The Secret of Human Thought Revealed by Ray Kurzweil

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

“Overcoming Artificial Stupidity,” WolframAlpha Blog, April 17, 2012, http://blog.wolframalpha.com/author/stephenwolfram/. Chapter 8: The Mind as Computer 1. Salomon Bochner, A Biographical Memoir of John von Neumann (Washington, DC: National Academy of Sciences, 1958). 2. A. M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society Series 2, vol. 42 (1936–37): 230–65, http://www.comlab.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf. A. M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem: A Correction,” Proceedings of the London Mathematical Society 43 (1938): 544–46. 3. John von Neumann, “First Draft of a Report on the EDVAC,” Moore School of Electrical Engineering, University of Pennsylvania, June 30, 1945. John von Neumann, “A Mathematical Theory of Communication,” Bell System Technical Journal, July and October 1948. 4.

pages: 903 words: 235,753

The Stack: On Software and Sovereignty by Benjamin H. Bratton

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

In twelfth century Majorca, Ramon Llull described logical machines, influencing Gottfried Leibniz, who developed a predictive calculus and a biliteral alphabet that, drawing on the I Ching, allowed for the formal reduction of any complex symbolic expression to a sequence of discrete binary states (zero and one, on and off). Later, the formalization of logic within the philosophy mathematics (from Pierre-Simon Laplace, to Gottlob Frege, Georg Cantor, David Hilbert, and so many others) helped to introduce, inform, and ultimately disprove a version of the Enlightenment as the expression of universal deterministic processes (of both thought and physics). In 1936, with his now-famous paper, “On Computable Numbers, with an Application to the Entscheidungsproblem,” a very young Alan Turing at once introduced the theoretical basis of modern computing and demonstrated the limits of what could and could not ever be calculated and computed by a universal technology. Turing envisioned his famous “machine” according to the tools of his time to involve an infinite amount of “tape” divided into cells that can store symbols, moved along a stationary read-write “head” that can alter those symbols, a “state register” that can map the current arrangement of symbols along the tape, and a “table” of instructions that tells the machine to rewrite or erase the symbol and to move the “head,” assuming a new state for the “register” to map.

The photo I describe is from the same series as that used on the cover of the posthumous collection of Deleuze's writings, Desert Islands and Other Texts, 1953–1974 (Cambridge, MA: MIT Press, 2004). Readers may reference the image at this book's companion website, thestack.org. 5.  Originally conceived in 1936 by twenty-four-year-old Alan Turing and called an “a-machine” (for “automatic machine”), it describes a hypothetical universal computer, which, given enough time and energy, would be capable of calculating any “computable” problem. In that paper, “On Computable Numbers, with an Application to the Entscheidungs Problem,” Proceedings of the London Mathematical Society, Ser. 2 42 (1937), Turing demonstrates the range of problems that in fact are not computable. The figure of the Turing machine, as a philosophical and machinic hypothesis, stands for the technology of universal computation and for the ultimate limits of computation within mathematics. 6.  Nicholas Gane and Stephen Sale, “Interview with Friedrich Kittler and Mark Hansen,” Theory, Culture, and Society 24 (2007): 323–329. 7.

See also User AI User, 277–279 algorithmic hardware, 348–349 animal User, 274–277 as co-User, 276–277, 349 designing for, 339 enrollment and motivation, 297–298 identifying, 345 machine User, 279–284 rights of, 345 nonpersonhood, 173–175 nonplace, end of, 16 non-state actors with nation-state functions, 10–11 nonvisual interfaces, 341, 424n41 Nortel patent bid, 134 North American Free Trade Agreement, 443n23 North Sea wind farms proposal (OMA), 181 No-Stop City project (Archizoom), 149–151, 160, 178–179 notational systems, 383n4 NSA/CSS Threat Operations Center, US, 441n8 Obama, Barack, 98, 180, 322 Obi-Wan Kenobi, 176 object identifiers, universal, 214–215 object-instruments, computational, 227 objects addressability, 214–215 agency of, 131 defined, 402n59 essentials of, 260 identifiers, digital, 207, 214–215 interface design, 230–235 memory of, 212, 215 non-citizen User, 188 object-to-object communication, 197, 210, 212, 216, 338 object-to-object spam, 216 reordering by, 206 semantic relations, 202–203 SPIME designation for, 201–204 as symbolic artifacts, 212 ocean exploration, 30 oceanic data centers, 113–114, 140 Oculus, 127 Office of Metropolitan Architecture (OMA), 53, 99, 170, 178, 180–181 offshoring, 443n23 oil geopolity, 99 Oklahoma City Bombing guidelines, 322 “On Computable Numbers, with an Application to the Entscheidungsproblem” (Turing), 78 One57, New York, 311 One Riverside Park, New York, 311 OOZ (Jeremijenko), 276 Open, The (Agamben), 273 OpenFlow, 437n58 open government movement, 121 Open Stack, 174 open systems interconnection (OSI) network model, 61–63 Operation Centurion, Dr. Manuel de la Pila housing block, 312 opinionlessness, state of, 240–241, 426n47 O’Reilly, Tim, 121 Oreskes, Naomi, 457n10 Organized Chaos, forces of, 445n37 Ouroboros energy grid, 92–96, 294–295 Outer Space Treaty, 456n7 “Outline of a Doctrine of French Policy” (Kojève), 109 “Overexposed City, The” (Virilio), 155 ownership competitive, 332 of data, 203, 285, 345–346 economics of, 282 owner-Users, 285–286, 345–346 Page, Larry, 134, 139, 281, 315 Page Mill Road, 57 “PageRank” (Franceschet), 332 PageRank algorithm, 134, 332 Pakistan-India border, 97, 309 Palace of the Soviets, 181 Palantir, 121, 287, 360, 459n20 Palestine, 120 Panopticon effect, 363 paper envelope, 46 parametricism, 160–161, 162–163 parastates, 446n39 Parker, Sean, 126 Parnet, Clare, 393n50 Parsons, Talcott, 385n25 partition in architecture, 391n30 Patriot Act, US, 120, 363 peer-to-peer networking, 206, 215 Peirce, Charles Sanders, 211, 223 Perec, Georges, 75 persona design, 254, 255 personality, 277–278 personal mapping technologies, 86, 236, 243, 431n70 personal mobility systems.

pages: 855 words: 178,507

The Information: A History, a Theory, a Flood by James Gleick

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

An example of an intellectual object that could be called mechanical was the algorithm: another new term for something that had always existed (a recipe, a set of instructions, a step-by-step procedure) but now demanded formal recognition. Babbage and Lovelace trafficked in algorithms without naming them. The twentieth century gave algorithms a central role—beginning here. Turing was a fellow and a recent graduate at King’s College, Cambridge, when he presented his computable-numbers paper to his professor in 1936. The full title finished with a flourish in fancy German: it was “On Computable Numbers, with an Application to the Entscheidungsproblem.” The “decision problem” was a challenge that had been posed by David Hilbert at the 1928 International Congress of Mathematicians. As perhaps the most influential mathematician of his time, Hilbert, like Russell and Whitehead, believed fervently in the mission of rooting all mathematics in a solid logical foundation—“In der Mathematik gibt es kein Ignorabimus,” he declared.

Alan Turing to Claude Shannon, 3 June 1953, Manuscript Division, Library of Congress. ♦ “NO, I’M NOT INTERESTED IN DEVELOPING A POWERFUL BRAIN”: Andrew Hodges, Alan Turing: The Enigma (London: Vintage, 1992), 251. ♦ “A CONFIRMED SOLITARY”: Max H. A. Newman to Alonzo Church, 31 May 1936, quoted in Andrew Hodges, Alan Turing, 113. ♦ “THE JUSTIFICATION … LIES IN THE FACT”: Alan M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society 42 (1936): 230–65. ♦ “IT WAS ONLY BY TURING’S WORK”: Kurt Gödel to Ernest Nagel, 1957, in Kurt Gödel: Collected Works, vol. 5, ed. Solomon Feferman (New York: Oxford University Press, 1986), 147. ♦ “YOU SEE … THE FUNNY LITTLE ROUNDS”: letter from Alan Turing to his mother and father, summer 1923, AMT/K/1/3, Turing Digital Archive, http://www.turingarchive.org

.: IEEE Computer Society, 1998. Toole, Betty Alexandra. “Ada Byron, Lady Lovelace, an Analyst and Metaphysician.” IEEE Annals of the History of Computing 18, no. 3 (1996): 4–12. ———. Ada, the Enchantress of Numbers: Prophet of the Computer Age. Mill Valley, Calif.: Strawberry Press, 1998. Tufte, Edward R. “The Cognitive Style of PowerPoint.” Cheshire, Conn.: Graphics Press, 2003. Turing, Alan M. “On Computable Numbers, with an Application to the Entscheidungsproblem.” Proceedings of the London Mathematical Society 42 (1936): 230–65. ———. “Computing Machinery and Intelligence.” Minds and Machines 59, no. 236 (1950): 433–60. ———. “The Chemical Basis of Morphogenesis.” Philosophical Transactions of the Royal Society of London, Series B 237, no. 641 (1952): 37–72. Turnbull, Laurence. The Electro-Magnetic Telegraph, With an Historical Account of Its Rise, Progress, and Present Condition.

pages: 696 words: 143,736

The Age of Spiritual Machines: When Computers Exceed Human Intelligence by Ray Kurzweil

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

., Computer Models of Thought and Language (San Francisco: W H. Freeman, 1973). 15 Haneef A. Fatmi and R. W Young, “A Definition of Intelligence,” Nature 228 (1970): 97. 16 Alan Turing showed that the essential basis of computation could be modeled with a very simple theoretical machine. He created the first theoretical computer in 1936 (first introduced in Alan M. Turing, “On Computable Numbers with an Application to the Entscheinungs Problem,” Proc. London Math. Soc. 42 [1936]: 230-265) in an eponymous conception called the Turing machine. As with a number of Turing’s breakthroughs, he would have both the first and last word. The Turing machine represented the founding of modern computational theory. It has also persisted as our primary theoretical model of a computer because of its combination of simplicity and power.The Turing machine is one example of the simplicity of the foundations of intelligence.

Tufte, Edward R. The Visual Display of Quantitative Information. Cheshire, CT: Graphics Press, 1983. _______. Visual Explanations: Images and Quantities, Evidence and Narrative. Cheshire, CT: Graphics Press, 1997. Turing, Alan. “Computing Machinery and Intelligence.” Reprinted in Minds and Machines, edited by Alan Ross Anderson. Englewood Cliffs, NJ: Prentice-Hall, 1964. ________. “On Computable Numbers, with an Application to the Entscheidungsproblem ” Proceedings, London Mathematical Society, 2, no. 42 (1936). Turkle, Sherry. The Second Self: Computers and the Human Spirit. New York: Simon and Schuster, 1984. Tye, Michael. Ten Problems of Consciousness: A Representational Theory of the Phenomenal Mind. Cambridge, MA: MIT Press, 1995. Ullman, Shimon. The Interpretation of Visual Motion. Cambridge, MA: MIT Press, 1982.

pages: 528 words: 146,459

Computer: A History of the Information Machine by Martin Campbell-Kelly, William Aspray, Nathan L. Ensmenger, Jeffrey R. Yost

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

In short, the Turing Machine embodied all the logical capabilities of a modern computer. Alan Turing was born in 1912 and at school he was drawn to science and practical experimenting. He won a scholarship to King’s College, Cambridge University, and graduated in mathematics with the highest honors in 1934. He became a Fellow of King’s College and, in 1936, published his classic paper “On Computable Numbers with an Application to the Entscheidungsproblem” in which he described the Turing Machine. Turing showed that not all mathematical questions were decidable, and that one could not always determine whether or not a mathematical function was computable. For nonmathematicians this was an obscure concept to grasp, although later—after World War II—Turing explained the idea in an article in Science News.

See NCR National Defense Research Committee (NDRC), 66, 72, 74, 145 National Science Foundation (NSF), 292 National Semiconductor, 221 Nature, 41, 59, 299–300 Nautical Almanac, 4, 7, 47, 52–53 Navigation tables, 4, 47, 53 NCR accounting machines, 31, 38, 53, 117 acquisition of CRC, 117 business software, 122 business strategies of, 30, 34, 123–124, 132 cash registers, 31–32 computer industry and, 98 digital computing machines, 54 as IBM competitor, 133 non-IBM-compatible computers of, 132 postwar business challenges, 103 punched-card systems, 21, 38 role in computer industry, 21, 117 sales strategies of, 30, 31–32, 36 scanning technology, 164 as software contractors, 177 technical innovation by, 31 user training, 30 Nelson, Ted, 234–235, 237, 279, 286 Netiquette, 285 Netscape Communications Corporation, 289–290 Network analyzers, 48, 50 Network protocols, 285 Networks, 275 New Communalists, 234 New Deal projects, 39 New Product Line (IBM), 126–128, 129 Newman, Max, 82 Nokia, 297, 298 Non-IBM-compatible computers, 132 Norris, William, 99, 124, 249 Northrop Aircraft Corporation, 101, 102, 105, 116 Notation, programming, 168 Notebook computers, 296, 298 Noyce, Robert, 219–221, 222, 231, 249 Noyes, Eliot, 120 Nuclear weapons, 65, 74, 78, 109, 127, 149 Numerical meteorology, 50–52 Office machine industry. See Business machine industry Office of Naval Research (ONR), 147–148, 150 Office of Scientific Research and Development (OSRD), 49, 65–66, 74 Office systematizers, 19, 134 Olivetti, 197, 251 Olsen, Kenneth, 217–218 Omidyar, Pierre, 295 “On Computable Numbers with an Application to the Entscheidungsproblem” (Turing), 60 Opel, John, 246 Open-source software, 215, 288, 296 Operating systems for mainframe computers, 179–182, 205, 206, 210, 212–215 for mobile devices, 297, 298 for personal computers, 242–243, 246–247, 253–254, 257–258, 264–267 See also specific operating systems Optical character recognition, 164 OS/2 operating system, 265, 266 OS/360 operating system, 179–182, 183, 212 Osborne 1 computer, 198 (photo), 296 Outsourcing of components and software, 245–246, 247 Oxford English Dictionary, 3 Packaged software programs, 186–188, 254 Packard, David, 249 Packet-switching technology, 281–282 Page, Larry, 294 Palm, Inc., 297, 298 Palo Alto Research Center (PARC), 260, 261, 280, 296 Papian, Bill, 150 Parker, Sean, 301 Pascal programming language, 185 Passages from the Life of a Philosopher (C.

pages: 405 words: 117,219

In Our Own Image: Savior or Destroyer? The History and Future of Artificial Intelligence by George Zarkadakis

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

., and Pitts, W. (1943), ‘A logical calculus of the ideas immanent in nervous activity’, in: Bulletin of Mathematical Biophysics (5), pp. 115–33. 6Dehaene, N., and Naccache, L. (2001), ‘Towards a cognitive neuroscience of consciousness: basic evidence of a workspace framework’, in: Cognition, 79 (1–2), pp. 1-37. 7Artificial Intelligence split from cybernetics in the summer of 1956 with its inaugural conference in Dartmouth, New Hampshire, one year before von Neumann’s death. 8Turing, A. M. (1936), ‘On Computable Numbers, with an Application to the Entscheidungsproblem’, Proceedings of the London Mathematical Society, 2 (1937), 42, pp. 230–65. 9To be more accurate, Gödel encoded metamathematical statements within ordinary arithmetic. 10The incomplete manuscript and notes based on a series of lectures given by von Neumann at the University of Illinois in 1949 was assembled and edited by Arthur Burks and published ten years after von Neumann’s death. 11New findings in epigenetics show that the mechanism of passing hereditary features to future generations is more complex than previously thought, and probably involves other systems in the cell beyond DNA replication. 12The human mind may be beyond logical coding (as Gödel has indirectly showed) but it is not beyond computation.

That was the actual statement that Gödel ‘formalised’. 14To be more precise, Gödel proved that for any computable axiomatic system that is powerful enough to describe arithmetic of the natural numbers (e.g. the Peano axioms) the consistency of the axioms cannot be proven within the system. 15Heisenberg’s uncertainty principle essentially states that we can never know everything about a quantum phenomenon. Therefore, nature will remain forever at least partially unknown to us. 16Turing, A. M. (1936), ‘On Computable Numbers, with an Application to the Entscheidungsproblem’, in: Proceedings of the London Mathematical Society, 1937, Vol. 2, No. 42, pp. 230–65. 17The American mathematician Alonzo Church independently published his proof of the Entscheidungsproblem for the American Mathematical Society using a method called ‘lamda calculus’, and therefore the solution is known as the Turing-Church theorem. (Church, A. (1936), ‘An unsolvable problem of elementary number theory’, in: American Journal of Mathematics, 1936, Vol. 58, pp. 345–63. 18Penrose, R. (1989), The Emperor’s New Mind: Concerning Computers, Minds and the Laws of Physics.

pages: 158 words: 49,168

Infinite Ascent: A Short History of Mathematics by David Berlinski

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

And so again it is again. Some years after Gödel presented his results, the American logician Alonzo Church defined what he called the lambda-computable functions. And to roughly the same point since the recursive and the lambda-computable functions, although quite different, did the same thing and carried on in the same way. In 1936, Alan Turing published the first of his papers on computability, “On Computable Numbers with an Application to the Entscheidungsproblem,” and so gave the idea of an algorithm a vivid and unforgettable metaphor. An effective calculation is any calculation that could be undertaken, Turing argued, by an exceptionally simple imaginary machine, or even a human computer, someone who has, like a clerk in the department of motor vehicles or a college dean, been stripped of all cognitive powers and can as a result execute only a few primitive acts.

pages: 236 words: 50,763

The Golden Ticket: P, NP, and the Search for the Impossible by Lance Fortnow

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Trakhtenbrot, “A Survey of Russian Approaches to Prebor (Brute-Force Search) Algorithms,” Annals of the History of Computing 6, no. 4 (October 1984): 384–400. Warren McCulloch and Walter Pitts, “A Logical Calculus of the Ideas Immanent in Nervous Activity,” Bulletin of Mathematical Biology 5, no. 4 (1943): 115–33. Panel discussion, Complexity of Computer Computations 40, no. 4 (1972): 169–85. Alan Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society 42 (1936): 230–65. S. Yablonsky, “On the Impossibility of Eliminating PEREBOR in Solving Some Problems of Circuit Theory,” Doklady Akademii Nauk SSSR 124 (1959): 44–47. Y. Zhuravlev, “On the Impossibility of Constructing Minimal Disjunctive Normal Forms for Boolean Functions by Algorithms of a Certain Class, Doklady Akademii Nauk SSSR 132 (1960): 504–6.

pages: 253 words: 80,074

The Man Who Invented the Computer by Jane Smiley

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Andrew Hodges, Turing’s biographer, points out that Turing’s idea “was not only a matter of abstract mathematics, not only a play of symbols, for it involved thinking about what people did in the physical world … His machines—soon to be called Turing Machines—offered a bridge, a connection between abstract symbols and the physical world. Indeed, his imagery was, for Cambridge, almost shockingly industrial.” In May 1936, Alan Turing submitted his paper, entitled “On Computable Numbers, with an Application to the Entscheidungsproblem,” to the Proceedings of the London Mathematical Society and then applied unsuccessfully for a Procter Fellowship at Princeton. As far as anyone in England knew, only Turing and the American Alonzo Church had come up with answers to the Entscheidungsproblem. No mathematician in England was equipped to referee either Turing’s or Church’s paper. Atanasoff and Turing, in their different ways, understood that counting was the future of computing, but the differences between them could not have been more clear—Atanasoff had to invent an actual, physical machine that when turned on would perform a useful function.

pages: 229 words: 67,599

The Logician and the Engineer: How George Boole and Claude Shannon Created the Information Age by Paul J. Nahin

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

And second, because of the arbitrarily long length of the tape, a Turing machine has the ability to “remember” what has happened in the arbitrarily distant past. In developing this view of a computing machine, Turing was not suggesting it as a practical design for an actual machine. Rather, as a mathematician he used his machines as a conceptual framework in which to study the limits on just what mechanistic devices can actually compute. Indeed, the title of his 1936 paper, “On Computable Numbers, with an Application to the Entscheidungsproblem’’—that final tongue-twister translates as “the decision problem’’—clearly shows Turing’s intent. His great accomplishment was to show that not all the numbers we can imagine are in fact actually computable. That is, Turing showed there are limits to what a computer—any computer—can do. I’ll return to the concept of a computable number in the final section of this chapter. 9.2 TWO TURING MACHINES As my first specific example of a Turing machine, consider the following state-transition table for a Turing machine that adds any two non-negative integers m and n that are placed on the tape, leaves their sum on the tape, and then halts.

pages: 440 words: 109,150

The Secrets of Station X: How the Bletchley Park codebreakers helped win the war by Michael Smith

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Throughout 1942, the work on the Tunny material had to be done by hand and, although some useful material was gained on the German campaign against Russia and from the links between Italy and North Africa, many of the messages took several weeks to decypher. Max Newman, one of the mathematicians working in the Testery, was a thin, bald academic from Manchester University, who like Tutte had worked in Tiltman’s research section. He had been Turing’s tutor at one stage. It was Newman’s suggestion that machines might be able to prove mathematical statements that had led Turing to write his ground-breaking paper ‘On Computable Numbers, with an Application to the Entscheidungsproblem’, and Newman who had ensured that it was published. Newman became convinced that, using similar principles to those advocated by Turing, it would be possible to build a machine that, once the patterns of the wheels had been worked out in the Testery, would find the settings of the first row of wheels, thereby making the codebreakers’ task immeasurably easier.

pages: 370 words: 94,968

The Most Human Human: What Talking With Computers Teaches Us About What It Means to Be Alive by Brian Christian

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid (New York: Basic Books, 1979). 8 Mark Humphrys, “How My Program Passed the Turing Test,” in Parsing the Turing Test, edited by Robert Epstein et al. (New York: Springer, 2008). 9 V. S. Ramachandran and Sandra Blakeslee, Phantoms in the Brain: Probing the Mysteries of the Human Mind (New York: William Morrow, 1998). 10 Alan Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, 1937, 2nd ser., 42, no. 1 (1937), pp. 230–65. 11 Ada Lovelace’s remarks come from her translation (and notes thereupon) of Luigi Federico Menabrea’s “Sketch of the Analytical Engine Invented by Charles Babbage, Esq.,” in Scientific Memoirs, edited by Richard Taylor (London, 1843). 12 Alan Turing, “Computing Machinery and Intelligence,” Mind 59, no. 236 (October 1950), pp. 433–60. 13 For more on the idea of “radical choice,” see, e.g., Sartre, “Existentialism Is a Humanism,” especially Sartre’s discussion of a painter wondering “what painting ought he to make” and a student who came to ask Sartre’s advice about an ethical dilemma. 14 Aristotle’s arguments: See, e.g., The Nicomachean Ethics. 15 For a publicly traded company: Nobel Prize winner, and (says the Economist) “the most influential economist of the second half of the 20th century,” Milton Friedman wrote a piece in the New York Times Magazine in 1970 titled “The Social Responsibility of Business Is to Increase Its Profits.”

pages: 387 words: 111,096

Enigma by Robert Harris

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

His possessions from his previous address had been delivered to her door that same morning: two boxes of personal effects and an ancient iron bicycle. The bicycle she wheeled into the back yard. The boxes she carried upstairs. One carton was full of books. A couple of Agatha Christies. A Synopsis of Elementary Results in Pure and Applied Mathematics, two volumes, by a fellow named George Shoobridge Garr. Principia Mathematical, whatever that was. A pamphlet with a suspiciously Germanic ring to it—On Computable Numbers, with an Application to the Entscheidungs problem—inscribed 'To Tom, with fond respect, Alan'. More books full of mathematics, one so repeatedly read it was almost falling to pieces and stuffed full of markers—bus and tram tickets, a beer mat, even a blade of grass. It fell open at a heavily underlined passage: there is one purpose at any rate which the real mathematics may serve in war. When the world is mad, a mathematician may find in mathematics an incomparable anodyne.

pages: 481 words: 125,946

What to Think About Machines That Think: Today's Leading Thinkers on the Age of Machine Intelligence by John Brockman

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Nick Bostrom, Superintelligence: Paths, Dangers, Strategies (New York: Oxford University Press, 2014). 5. G. K. Chesterton, Heretics (New York: John Lane, 1905). 6. I. J. Good, “Speculation Concerning the First Ultraintelligent Machine,” Advances in Computers, vol. 6, 1965. 7. Kevin Kelly, “The Technium,” Edge, entry February 3, 2014, https://edge.org/conversation/the-technium [accessed July 21, 2015]. 8. Alan Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proc. Lond. Math. Soc. 42, series 2 (1936–7): 230–65. 9. Steven Pinker, comment on “The Myth of AI,” Edge, entry November 14, 2014, http://edge.org/conversation/the-myth-of-ai#25987 [accessed July 21, 2015]. 10. Hannah Arendt, The Life of the Mind, vol. 1 (New York: Harcourt Brace, 1978). 11. Nick Bostrom, “Existential Risks,” Jour. Evol. & Technol. 9, no. 1 (2002), at http://www.nickbostrom.com/existential/risks.html. 12.

pages: 463 words: 118,936

Darwin Among the Machines by George Dyson

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

.: Open Court, 1902), 254. 53.Leibniz to Caroline, Princess of Wales, ca. 1716, in Alexander, Correspondence, 191. CHAPTER 4 1.Alan Turing, “Computing Machinery and Intelligence,” Mind 59 (October 1950): 443. 2.A. K. Dewdney, The Turing Omnibus (Rockville, Md.: Computer Science Press, 1989), 389. 3.Robin Gandy, “The Confluence of Ideas in 1936,” in Rolf Herken, ed., The Universal Turing Machine: A Half-century Survey (Oxford: Oxford University Press, 1988), 85. 4.Alan Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, 2d ser. 42 (1936–1937); reprinted, with corrections, in Martin Davis, ed., The Undecidable (Hewlett, N.Y.: Raven Press, 1965), 117. 5.Ibid., 136. 6.Kurt Gödel, 1946, “Remarks Before the Princeton Bicentennial Conference on Problems in Mathematics,” reprinted in Davis, The Undecidable, 84. 7.W. Daniel Hillis, The Difference That Makes a Difference (New York: Basic Books, forthcoming). 8.Malcolm MacPhail to Andrew Hodges, 17 December 1977, in Andrew Hodges, Alan Turing: The Enigma (New York: Simon & Schuster, 1983), 138. 9.Allan Marquand, “A New Logical Machine,” Proceedings of the American Academy of Arts and Sciences 21 (1885): 303. 10.Charles Peirce to Allan Marquand, 1866, in Arthur W.

The Science of Language by Noam Chomsky

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Cambridge University Press. Tomalin, Marcus (2003) “Goodman, Quine, and Chomsky: from a grammatical point of view.” Lingua 113: 1223–1253. Tomalin, Marcus (2006) Linguistics and the Formal Sciences: The Origins of Generative Grammar. Cambridge University Press. Tomalin, Marcus (2007) “Reconsidering Recursion in Linguistic Theory.” Lingua 117: 1784–1800. Turing, Alan (1937) “On Computable Numbers, with an Application to the Entscheidungsproblem.” London Mathematical Society, Series 2 42: 230–265. Turing, Alan (1950) “Computing Machinery and Intelligence.” Mind 59: 433–460. Turing, Alan (1992) Collected Works of Alan Turing: Morphogenesis. Ed. P. T. Saunders. Amsterdam: North Holland. Tversky, Amos and Daniel Kahneman (1974) “Judgment under Uncertainty.” Science, New Series 185 (4157): 1124–1131.

The Singularity Is Near: When Humans Transcend Biology by Ray Kurzweil

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

See the exponential growth of computing graphs in chapter 2 (pp. 67, 70). 26. Alfred N. Whitehead and Bertrand Russell, Principia Mathematica, 3 vols. (Cambridge, U.K.: Cambridge University Press, 1910, 1912, 1913). 27. Gödel's incompleteness theorem first appeared in his "Uberformal unenscheiderbare Satze der Principia Mathematica und verwandter Systeme I," Monatshefte für Mathematik und Physik 38 (1931): 173–98. 28. Alan M. Turing, "On Computable Numbers with an Application to the Entscheidungsproblem," Proceedings of the London Mathematical Society 42 (1936): 230-65. The "Entscheidungsproblem" is the decision or halting problem—that is, how to determine ahead of time whether an algorithm will halt (come to a decision) or continue in an infinite loop. 29. Church's version appeared in Alonzo Church, "An Unsolvable Problem of Elementary Number Theory," American Journal of Mathematics 58 (1936): 345–63. 30.

The Dream Machine: J.C.R. Licklider and the Revolution That Made Computing Personal by M. Mitchell Waldrop

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

"History of the Design of the SAGE Computer-The AN/FSQ7." Annals of the H15tory ofComput- zng 5 (1983). -. "A Perspective on SAGE: Discussion." Annals of the H15tory ofComputzng 5 (1983). -. "RelIabilIty of Components (Interview with Jay W. Forrester)." Annals of the H15tory ofComputzng 5 (1983). -. "Origin of the Term Bit." Annals of the History ofComputzng 6 (1984). Turing, Alan M. "On Computable Numbers, with an ApplIcation to the Entschldungsproblem." Pro- ceedzngs of the London Mathematical Soczety 2, no. 42 (1937). -. "Computing Machinery and Intelligence." Mind 59, no. 236 (1950). Reprinted In The Mznd's I: Fantaszes and ReflectIOns on Self & Soul, edited by Douglas R. Hofstadter and Daniel C. Dennett. New York: BasIC Books, 1981. Turkle, Sherry. The Second Self: Computers and the Human Spznt.

pages: 1,351 words: 385,579

The Better Angels of Our Nature: Why Violence Has Declined by Steven Pinker

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Trivers, R. L., & Willard, D. E. 1973. Natural selection of parental ability to vary the sex ratio of offspring. Science, 179, 90–91. Tuchman, B. W. 1978. A distant mirror: The calamitous 14th century. New York: Knopf. Tucker, G. R. & Lambert, W. E. 1969. White and Negro listeners’ reactions to various American-English dialects. Social Forces, 47, 465–68. Turing, A. M. 1936. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42, 230–65. Turing, A. M. 1950. Computing machinery and intelligence. Mind, 59, 433–60. Turkheimer, E. 2000. Three laws of behavior genetics and what they mean. Current Directions in Psychological Science, 5, 160–64. Turner, H. A. 1996. Hitler’s thirty days to power: January 1933. New York: Basic Books.