universal Turing machine

Turing's Vision: The Birth of Computer Science
by Chris Bernhardt
Published 12 May 2016

At each stage there was just one thing that had to be done next. Consequently, universal Turing machines are not necessarily complex, highly intelligent machines. They can be relatively simple things. In the previous section we considered a universal Turing machine U taking 〈M, I〉 as input and then running M on the input I. The machine U can be quite simple and it is often the case that M is much more complicated. In other words, it can be harder to design an algorithm than to design a machine to run it. By now you are probably wondering if it is possible to draw a diagram of a universal Turing machine. The answer is that it is, but a fair amount of work has to be put in to explain exactly what each state of the machine is doing.

…

Now that Turing had algorithms written as strings of numbers, he could describe a Universal Computer. This is a computer that can take both an algorithm and data as input and then run the algorithm on the data. This is an extremely important idea. A universal Turing machine can simulate any other Turing machine. Consequently, a universal Turing machine can do any computation that can be done by any other Turing machine — it can run any algorithm. All modern computers are stored-program computers — where the data and programs are treated in exactly the same way. This idea originated with Turing. As we progress through Turing’s argument we will be doing computations.

…

Now by the Church-Turing thesis we know that there exists a Turing machine for every algorithm, so we obtain: There is a Turing machine, U, that will take any 〈M, I〉 as input and give the answer accept if M accepts I, give the answer reject if M rejects I, and never halt if M does not halt on I. This machine U is able to simulate any Turing machine on any input. Machines that can do this are called universal Turing machines. Modern computers are universal Turing machines. (There is a slight technicality here concerning the finite memory of a computer. We will say a little more about this later.) We can think of M as representing a program and I as the data. Then 〈M, I〉 corresponds to the program and data after both have been converted to binary strings.

Complexity: A Guided Tour
by Melanie Mitchell
Published 31 Mar 2009

Von Neumann also was able to show that his cellular automaton was equivalent to a universal Turing machine (cf. chapter 4). The cell update rule plays the role of the rules for the Turing machine tape head, and the configuration of states plays the role of the Turing machine tape—that is, it encodes the program and data for the universal machine to run. The step-by-step updates of the cells correspond to the step-by-step iteration of the universal Turing machine. Systems that are equivalent in power to universal Turing machines (i.e., can compute anything that a universal Turing machine can) are more generally called universal computers, or are said to be capable of universal computation or to support universal computation.

…

See Shannon information Shannon information (or entropy), 51–55, 57, 169 in explanation of Zipf’s law, 271 as measure of complexity, 96–98 relation to statistical complexity, 102 Shaw, George Bernard, 71 Shaw, Robert, 293 Sigmund, Karl, 220 Simon, Herbert, 109–110, 272 sine map, 36 six degrees of separation, 228 Slagle, James, 223 slippage, conceptual, 188, 191–193, 196–197, 202, 206 small-world networks, 236–239 examples of, 247–252 simplifying assumptions about, 254–255 See also small-world property small-world property, 238, 245, 248, 251 formal definition of, 318 Smith, Adam, 10, 76 Smith, Eric, 94, 287 social networks, 227–230, 234–236, 238 social norms, 218–219, 220, 222 space-filling fractals, 266 spatial dimension, 107–108 statistical complexity, 102–103 statistical mechanics, 47–51 influence on Stuart Kauffman’s work, 286 Stein, Myron, 28, 35–36 Stein, Paul, 28, 35–36 stomata networks, 168 Stoppard, Tom, 15 strategy for majority classification task, 165 for norms model, 218 for Prisoner’s dilemma, 216–217 for Robby the Robot, 131–132 string theory, 210, 293 Strogatz, Steven, 230, 232, 236–239, 301 surface hypothesis, 260, 266, 268 survival instinct in Copycat, 208 as requisite for life, 116, 127 Sutton, Walter, 89 switches, genetic, 278–280 synchronization, 248 Synergetics, 298 Synthesis, Modern, 81–84 challenges to, 84–87 system science, 297–298 Szilard, Leo, 45–47, 125, 169 Tattersall, Ian, 83, 87 T cells, 9, 172, 174–175 regulatory, 176 teleology, 296 Teller, Edward, 125 thermodynamic depth, 101 thermodynamics, 41–42, 48, 51, 258, 298, 302 “fourth law” of, 286 as inspiration for information theory, 55 laws of, 42 second law of (see second law of thermodynamics) Thoreau, Henry David, 188 three-body problem, 21–22 tipping points, 253, 257 TIT FOR TAT strategy, 217–218 topology, algebraic, 21 tragedy of the commons, 214 trajectory, 31–32, 36 of states in random Boolean network, 284 transcription (genetic), 90–93, 249 in alternate splicing and RNA editing, 275 in gene regulation, 278–279 noise in, 249 transfer RNA, 91–93, 122 translation (genetic), 91–93 Tresser, Charles, 38 tRNA, 91–93, 122 Turing, Alan, 60–61, 63–65, 68–70, 209 solution to the Entscheidungsproblem, 65–68 Turing machines, 60–63 as definition of definite procedures, 63–64 in definition of logical depth, 100 encoding of, 64–65 example of, 62 as example of idea model, 211 meaning of information in, 171 simulation of in Game of Life, 150 in solution to the Entscheidungsproblem, 65–68 universal (see universal Turing machine) Turing statement, 66 two-body problem, 21 two-person game, 214 Ulam, Stanislaw, xi, 28, 149 uncertainty principle, 20 uncomputability, 60, 158 of the Halting problem, 65–68 See also noncomputable problem (or process) unified principles. See universal principles unimodal map, 35, 36, 38 universal computation in cellular automata, 149–150, 156 in defining complexity, 102, 156 definition of, 149 in nature, 157–158 See also universal Turing machine universal computer. See universal Turing machine universal principles (of complex systems), 95, 292–295 examples of proposals for, 294–295 skepticism about, 293–295, 299 universal properties of chaotic systems, 34–38 universal Turing machine, 64–65, as blueprint for programmable computers, 65, 69 cellular automata equivalent to, 149–150, 156 in defining complexity, 102, 156 Varela, Francisco, 298 variable (in computer program), 119 von Neumann, John, 28, 117–118, 124–127, 146, 149, 156, 209, 211–212, 294, 296–297 invention of cellular automata, 149 self-reproducing automaton, 122–124, 156 von-Neumann-style architecture, 146, 169–171, 209 Wang, Hao, 69 Watson, James, 89, 93, 274 Watts, Duncan, 230–231, 236–239, 257 Web (World Wide), 10, 12, 186 coevolution with search engines, 10 degree distribution of, 240–245, 265, 318 network structure of, 12, 229–230, 235–236, 240–245, 252–253, 265 resilience of, 245 search engines for, 239–240 West, Geoffrey, 263–267, 269, 294, 300 Wiener, Norbert, 209, 296–297 Wigner, Eugene, 125 Wilkins, Maurice, 93 Willinger, Walter, 269 Wolfram, Stephen, 102, 151–159, 168, 294, 303 work (as related to energy), 41–43, 51 in evolution, 72, 79 in Maxwell’s demon, 43–47 World Wide Web.

…

Turing machines were put forth as the definition of “definite procedure,” hitherto a vague and ill-defined notion. When formulating these ideas, Turing didn’t build any actual machines (though he built significant ones later on). Instead, all his thinking about Turing machines was done with pencil and paper alone. Universal Turing Machines Next, Turing proved an amazing fact about Turing machines: one can design a special universal Turing machine (let’s call it U) that can emulate the workings of any other Turing machine. For U to emulate a Turing machine M running on an input I, U starts with part of its tape containing a sequence of 0s, 1s, and blanks that encodes input I, and part of its tape containing a sequence of 0s, 1s, and blanks that encodes machine M.

Tools for Thought: The History and Future of Mind-Expanding Technology
by Howard Rheingold
Published 14 May 2000

The instructions, not the symbols that keep track of the way they are carried out -- the rules, not the markers -- are what make the Turing machine work. Universal Turing machines are primarily symbol manipulators. And digital computers are universal Turing machines. It isn't easy to think of the rules of a game as a kind of machine. The task is somewhat easier if you think about "mechanical processes" that are so clearly and specifically defined that a machine can perform them by referring to an instruction table. All universal Turing machines are functionally identical devices for following the program specified by an instruction table. The instruction tables can differ, and they can turn the universal Turing machine into many different kinds of machine.

…

When the machine stops, you count the Xs in the final tape configuration. The list of instructions is what turns the universal Turing machine into the doubling machine. Mechanically, there is no difference between the two machines. The particular instructions described by the code are what the universal Turing machine operates upon. If you can describe, in similarly codable instructions, a machine for tripling, or extracting square roots, or performing differential equations, then your basic, dumb old universal Turing machine can imitate your tripling machine or square root machine. That ability to imitate other machines is what led to computers.

…

The instruction tables can differ, and they can turn the universal Turing machine into many different kinds of machine. For this reason, the programs are sometimes called "virtual machines." The distinction between a universal Turing machine and the many different Turing machines it is able to imitate is a direct analogy to digital computers. Like universal Turing machines, all digital computers are functionally identical. At the most basic level, every digital computer operates in the way our doubling machine did with the squares and Os and Xs. Instead of building a different physical machine to solve different problems, it is more practical to describe to an instruction-following machine different virtual machines (programs) that use this one-square-at-a-time mechanical instruction-following process to solve complicated problems through a pattern of simple operations.

Physics in Mind: A Quantum View of the Brain
by Werner Loewenstein
Published 29 Jan 2013

Complex and simple cells in cortex, 193, 194–196 Computation, parallel. See Parallel computation Computation process classical versus quantum, 256–258 of Universal Turing Machines, 138–140 Computation time for gestalt recognition, 229 as a measure of complexity, 205, 206 saving, 273 See also Logical depth Computer-generated images, 140–142, 165 Computers and consciousness, 217 operational mode of, versus the brain’s, 184–185, 186, 187 protein demons as computers, 147–148 See also Universal Turing Machines Computing operations, 257 Conditional gate, 260, 261 Cones, 68, 72, 73 (fig.), 165, 166 (fig.) Conscious experience feelings and emotions, 223–226 gut feelings, 226–227 holistic aspects of, 221–223 and memory, 216, 218–219 multicellular involvement in, 159, 247 neural synchrony and, 227–228 and the passing of time, 216, 217–218 unconscious thinking, 219–221 Consciousness, xiii, 2–3, 95n, 184, 216 and the brain hemispheres, 184 competition for access to, 231–232, 233 (fig.)

…

Time spans, evolutionary, 15, 18 (fig.), 33, 35 Tononi, Giulio, 303 Top-down processing, 179 Transducers, 49–51 Transmogrification. See Protein transmogrification Trellis. See Neuron trellis Tunnel diodes, 103 Tunneling, electron, 125–126 Turing, Alan, 137, 138, 140, 250 Turing machines. See Universal Turing Machines Twain, Mark, 107 Ultraviolet rays, 22, 50, 59 (fig.), 109–110, 111 Unconscious thinking, 219–221 Unification theories, 13, 156 Universal computers, 108, 140, 252, 257 Universal Turing Machines, 137–140, 142n, 143, 206, 250 Universe developmental time chart of, 17, 18 (fig.) expansion of the, 6–7, 17, 20 (fig.), 21, 155 initial information state of the, 20, 21, 23 (fig.) organizational units, 21 origin, 19 See also Big Bang Unwin, Nigel, 37 (fig.)

…

3The Second Coming The Demons for Fast Information Transmission The Sensory Demons A Generalized Sensory Scheme The Demon Tandem How the Demon Tandems Censor Incoming Information 4The Sensors The Sensory Transducer Unit A Lesson in Economics from a Master The Silent Partner How Electrical Sensory Signals Are Generated 5Quantum Sensing The Quantum World Our Windows to the Quantum World Coherent Quantum Information Transmission The Advantages of Being Stable Why We See the Rainbow The Demons Behind Our Pictures in the Mind: A Darwinistic Physics View Why White Is White The Quantum View Again, Why White Is White Lady Evolution’s Quantum Game Plan Quantum Particles That Don’t Cut the Mustard 6Quantum into Molecular Information Boosting the Quantum A Consummate Sleight of Hand The Ubiquitous Membrane Demon 7Molecular Sensing A Direct Line from Nose to Cortex A Thousand Information Channels of Smell Mapping, Coding, and Synonymity Molecular Sensory Synonymity Why Sensory Synonymity Quantum Synonymity Harmless Double Entendres 8Electronic Transmission of Biological Information Evolution’s Favorite Leptons Electronic Information Transmission: A Development Stumped Two Old Batteries 9The Random Generators of Biomolecular Complexity Genuine Transmogrification A Quantum Random Generator of Molecular Form The Heuristics of Transmogrification The Random Generator and Our Genetic Heritage An Algorithm Is No Substitute for a Demon The Second Generator of Biomolecular Form Complexity as a Windfall Ikats 10The Ascent of the Digital Demons Quantum Electron Tunneling The Electronic Cul-de-Sac The Rise of the Digital Demons Do Plants Have Digital Demons, Too? 11The Second Information Arrow and Its Astonishing Dénouement: Consciousness The Structure of Time The Evolutionary Niche in the Structure of Time: A Hypothesis Forecognition 12How to Represent the World The Universal Turing Machine Rendering the World by Computer The Neuronal Virtual-Reality Generator Our Biased World Picture Computing by Neurons Correcting Our World Picture Flying the Coop of Our Senses 13Expanded Reality A Fine Bouquet Mathematics and Reality The Neuron Circuitry of Language The Feathers of the Brain Mathematics and Forecognition The Reluctant Sensory Brain The Limits of Knowledge A Note About Reality 14Information Processing in the Brain Cell Organization in the Brain Cortical Information-Processing Units Cortical-Cell Topography and Worldview A Last-Minute Change in Worldview Retrieving a Lost Dimension Information Processing in the Brain from the Bottom Up Being of One Mind Two Minds in One Body?

Turing's Cathedral
by George Dyson
Published 6 Mar 2012

Gödel was well aware that Turing’s Universal Machine and von Neumann’s implementation of it were demonstrations, if not the direct offspring, of his, Gödel’s, ideas. “What von Neumann perhaps had in mind appears more clearly from the universal Turing machine,” he later explained to Arthur Burks. “There it might be said that the complete description of its behavior is infinite because, in view of the non existence of a decision procedure predicting its behavior, the complete description could be given only by an enumeration of all instances. The universal Turing machine, where the ratio of the two complexities is infinity, might then be considered to be a limiting case.”53 Leibniz’s belief in a universal digital coding embodied his principle of maximum diversity: infinite complexity from finite rules.

…

All books owe their existence to previous books, but among the antecedents of this one should be singled out (in chronological order) Beatrice Stern’s History of the Institute for Advanced Study, 1930–1950 (1964), Herman Goldstine’s The Computer from Pascal to von Neumann (1972), Nicholas Metropolis’s History of Computing in the Twentieth Century (1980), Andrew Hodges’s Alan Turing: The Enigma (1983), Rolf Herken’s The Universal Turing Machine: A Half-Century Survey (1988), and William Aspray’s John von Neumann and the Origins of Modern Computing (1990). Julian Bigelow and his colleagues designed and built the new computer in less time than it took me to write this book. I thank Martin Asher, John Brockman, Stefan McGrath, and Katinka Matson for their patience in allowing this.

…

Turing then demonstrated the existence of a Universal Computing Machine that, given sufficient time, sufficient tape, and a precise description, could emulate the behavior of any other computing machine. The results are independent of whether the instructions are executed by tennis balls or electrons, and whether the memory is stored in semiconductors or on paper tape. “Being digital should be of more interest than being electronic,” Turing pointed out.6 Von Neumann set out to build a Universal Turing Machine that would operate at electronic speeds. At its core was a 32-by-32-by-40-bit matrix of high-speed random-access memory—the nucleus of all things digital ever since. “Random access” meant that all individual memory locations—collectively constituting the machine’s internal “state of mind”—were equally accessible at any time.

The Road to Conscious Machines
by Michael Wooldridge
Published 2 Nov 2018

And that is what Turing did. His next trick was to show that his machines could be turned into general-purpose problem-solving machines. He designed a Turing machine that will follow any recipe that you give it. We now call these general-purpose Turing machines Universal Turing Machines:4 and a computer, when stripped down to its bare essentials, is simply a Universal Turing Machine made real. The programs that a computer runs are just recipes, like the one for prime numbers that we discussed above. Although it isn’t central to our story, it is worth at least mentioning how Turing settled the Entscheidungsproblem using his new invention – apart from the fact that it was extraordinarily ingenious, it also has some bearing on the question of whether AI is ultimately possible.

…

Dealing with uncertainty is therefore a fundamental topic in AI. See also Bayes’ Theorem and Appendix C. undecidable problem A problem that we know, in a precise mathematical sense, cannot be solved by a computer (or, more exactly, by a Turing machine). Universal Turing Machine A general type of Turing machine, which provided the template for the modern computer. While a Turing machine encodes just one specific recipe/algorithm, a Universal Turing Machine can be given any recipe/algorithm. (unsound) reasoning In logic, where we derive conclusions that are not warranted by the premises. See also (sound) reasoning. Urban Challenge A 2007 follow-on to the DARPA Grand Challenge, in which autonomous vehicles were required to autonomously traverse a built-up urban environment.

…

A neat alternative called the Sieve of Eratosthenes has been known since antiquity. 4. At this point I’ll stop distinguishing between Universal Turing Machines and Turing Machines, and simply refer to ‘Turing Machines’. 5. Turing shares the glory for the Entscheidungsproblem with Princeton mathematician Alonzo Church, who independently obtained a very different proof of the result just before Turing. However, Turing’s proof is regarded as the definitive one: it is more direct, more complete and more accessible – and its implications, through the invention of the Universal Turing Machine, were world-changing. 6. Strictly speaking, an algorithm is a recipe, and a program is an algorithm that has been encoded in an actual programming language like Python or Java.

The Man From the Future: The Visionary Life of John Von Neumann
by Ananyo Bhattacharya
Published 6 Oct 2021

‘Bertus’ 22, 149, 150 Budapest anti-Semitism 2, 5 Jewish population 2 Kann-Heller 2 Lenin Boys 13 Romanian occupation 13–14 von Neumann’s life in 1–9, 5, 7 Budapest, University of 6–7, 11, 25, 65 Burks, Arthur 125, 130, 231, 235, 243, 258, 265 Burroughs, William S. xiv Bush, Vannevar 77, 107 California Institute of Technology 184, 245 Cambridge, University of, King’s College 70 Cantor, Georg 20, 20–21 carbon dioxide emissions 283 cardinality 23 Carleton University, Ottawa 225 Carter, Jimmy 264 causality 29, 48–9, 51, 60, 76, 298n63 Cayley, Arthur 32 cellular automata see self-reproducing automata Cellular Automata Machine 245 chain reaction, nuclears, Monte Carlo bomb simulations 8, 80, 81–2, 87–8, 133–4 Champernowne, David 151 Champlain, SS 77 chance 144–5 Chandrasekhar, Subrahmanyan 79 Chebyshev polynomials 12–13, 295n32 chess 4, 142–3, 144, 162–3, 164, 257, 289–90n8, 313n51 China 209 Church, Alonzo 118–9 Churchill, Winston 80, 90 cities, segregation 270, 271, 272 ‘clanking replicators’ 261–3, 262 Clauser, John 57 Cliff, Rodger 2654 climate change 283, 284 Clippinger, Richard 135 closed subroutine, the 138 Cockcroft, John 301n23 Codd, Edgar 258 Cold War 218–20183, 203, 208–12 counterforce strategy 222 doctrine of preventive war 208–10 game theory analysis 212–16 ICBM threat 216–18 kill-or-be-killed paranoia 203 little wars strategy 222–4 nuclear deterrence 212–16, 221–224 paranoia 203 preventive war 208–10 Soviet aggression 222 Soviet Union hydrogen bomb test 216–17 VNs view of 208–9 Collbohm, Frank 185–6, 217 Columbia University 78, 213, 214 Communist Party of Germany (KPD) 99 Compleat Strategyst, The (Williams) 189 Computer and the Brain, The (von Neumann) 275–6 computer programmer job born 131–2 ‘low class individuals’ 278 Neumann, Klára Dán von, as one of the first 133, 135, 136–138 computer science, foundations of 70, 121 computers xiii approach to programming 134–5 Atanasoff–Berry 127 Automatic Computing Engine (ACE) 121, 125 Automatic Sequence Controlled Calculator (ASCC) see Harvard Mark I birth of 16, 28, 102–40 closed subroutine 138 coding 115–16 comparison to the brain 273–6 delay-lines 124–5 differential analysers 107–8 earliest 73 quantum 59 women’s role 85–6, 108–9, 120–1 differential analyser 107–8 EDVAC patent dispute 125–6, 127–8 EDVAC report 121–7 see First Draft of a Report on the EDVAC (von Neumann) ENIAC xi, 1054–11, 106, 120, 123, 124, 126, 127–8 ENIAC conversion 130–5, 309–10n68 First Draft of a Report on the EDVAC (von Neumann) 111, 121–7111 for-loops 116 Gödel’s contribution 111–18 Harvard Mark I 104 human 120–1 IAS project 127, 128–30, 131, 138–9, 140, 193 IBM 701 14039 JOHNNIAC 193, 194 Manchester Baby 138 MANIAC I 137, 139, 310n77 origin of 28 program-controlled 119–20 Project PY 1101 proliferation 272–3 RAND Corporation and 192–3 size 106 Small-Scale Experimental Machine (SSEM) see Manchester Baby 138 storage capacity 123 stored-program 120, 121, 122 see also First Draft of a Report on the EDVAC subroutines 119 Turing’s contribution 118–21 the universal Turing machine 118–21, 306–7n35, 307n37 virus, first 236 VNs contribution 122, 125–76, 129–130, 131, 139–140, 308n48 VNs early interests in 79–80, 103–5 von Neumann architecture 123, 128, 275 von Neumann bottleneck 123 Conan Doyle, Arthur, ‘The Final Problem’ 153–4, 165–6, 165, 314n52 Conferences on Cybernetics 227 Connes, Alain 62 Conus textile sea snail 249 Conway, John Horton 237–41, 243 hexagonal packing of circles 237, 238 Life 239–41, 239, 240, 242, 243, 244, 245, 257 Universal Turing Machine within 241, 243 survey of life forms 240 Universal Turing machine 241, 243 cooperative game theory 172–3, 176, 178, 196–7 Copeland, B.

…

In the last part of Computable Numbers Turing argues that his machines are capable of carrying out any algorithmic process that can be performed by their human counterparts. Conversely, a human may compute anything a Turing machine can – assuming the human in question does not die of boredom first – but nothing that the machine cannot. The universal Turing machine is now considered an abstract prototype of a general-purpose ‘stored program’ computer – one that can, like any laptop or smart phone today, execute an application in the computer’s memory. The older machines ‘could only play one tune … like a music box,’ says Klári. ‘In contrast, the “all purpose” machine is like a musical instrument.’38 From the 1950s onwards, the universal machine has been appropriated as a foundation stone of theoretical computer science.

…

Three hundred years earlier, when the philosopher René Descartes declared ‘the body to be nothing but a machine’ his student, the twenty-three-year-old Queen Christina of Sweden, is said to have challenged him: ‘I never saw my clock making babies’.8 Von Neumann was not the first person to ask the question ‘can machines reproduce?’ but he would be the first to answer it. At the heart of von Neumann’s theory is the Universal Turing machine. Furnished with a description of any other Turing machine and a list of instructions, the universal machine can imitate it. Von Neumann begins by considering what a Turing-machine-like automaton would need to make copies of itself, rather than just compute. He argues that three things are necessary and sufficient.

The End of Theory: Financial Crises, the Failure of Economics, and the Sweep of Human Interaction
by Richard Bookstaber
Published 1 May 2017

See also Russell, Bertrand; Whitehead, Alfred North radical uncertainty, 12, 18; defined as, 50–51; economists’ view of, 197; and heuristics, 68; and the Library of Babel, 63 (see also Library of Babel); and the limits to knowledge, 52; and the nature of humanity, 60; and risk management, 121; in unknown state versus unknown probabilities, 198; and warfare, 117, 121 railroads, 4 rational expectations, 86 Rational Expectations Hypothesis (REH); fallibility and, 175; and reflexivity, 175; reflexivity, comparison to, 115 rationality, 87 reflexivity, 58, 60, 113; and complexity, 115, 122; and the cognitive function, 114, 137–138; and elements in modeling, 114; and fallibility, 59; and heuristics, 115; manipulative function in, 114, 137–138; time-and-context in, 183 regime shift, 105 regularity conditions, 29 regulators, 15 representative agent, 81–82 reproduction, 72–73 Reynolds, Craig, and boids, 37 Ricardo, David, 3–4, 91, 188 risk management: radical uncertainty in, 121 (see also radical uncertainty); in warfare, 121 risk transformations, 131 Rome, 131 Rorty, Richard, 178 Rothschild, Baron, 4 Royal Society, 52 Rumsfeld, Donald, 50 Russell, Bertrand, 52–53 Saari, Donald, 29 Samuelson, Paul, 84 Sartre, Jean-Paul, 77 Sargent, Thomas, 71, 103 Saturday Night Live, 144 Say, Jean-Baptiste, 4 Securities and Exchange Commission (SEC), 147–148 securities lenders, 136 self-fulfilling prophecy, 113 self-referential systems, 57, 60 self-replication, 31 Shackle, G.L.S., 85 Sharpe, William, 85 Shereshevsky, Solomon, 76–77 Simon, Herbert, 110 SIVs, 161, 165 Slick, Grace, 50 Smith, Adam, 3–4, 188 Societie Generale (SocGen), 164 Solow, Robert, 92 Soros, George, 83, 115, 137; and reflexivity, 58–59 stampede: and emergence, 35–36; Hajj, example of, 34–36 Standard & Poor’s, 160 stock market crash (October 1987): and the New York Stock Exchange (NYSE), 145–147; and portfolio insurance, 145–147 (see also portfolio insurance); and the S&P 500, 145–147 subprime mortgages, 160–161 Sun Pin, 117 Syll, Lars, 138 Thomas Theorem, 108 tight coupling, 112 Turing, Alan: and David Hilbert’s program, 54 (see also halting problem); and the halting problem, 31, 55; and the printing problem, 55; and Turing test, 196; and the universal Turing machine (UTM), 54 (see also universal Turing machine) Tversky, Amos, 45–47 Unbearable Lightness of Being, The, 60–61 uncertainty principle, 56–57; and the limits to knowledge, 51 universal Turing machine (UTM), 32, 54–56 University of Chicago, 3 Victorian England, 3–4 Volcker Rule, 156, 158 Walras, Leon, 194 Washington Mutual, 11 white night, 131 Whitehead, Alfred North, 52–53 Wittgenstein, Ludwig, 40 Wolfram, Stephen, 26–27 A NOTE ON THE TYPE This book has been composed in Adobe Text and Gotham.

…

See MGonz Chernobyl, nuclear accident of, 112 Church, Alonzo, 54 Citigroup, 11, 166 Clower, Robert, 85 cockroach, 68, 74; defense mechanism of, 66; and omniscient planner, 66–67 Coleman, Henry, 5 collateral: haircuts and, 131; risk reduction of, 204; transformations of, 131 commercial paper, 136 Commodity Futures Trading Commission (CFTC), 147–148 complexity: and chaos theory, 110–111; in comparison to computational irreducibility, 108, 122; description of, 109–112; and emergence, 108, 122; and ergodicity, 111, 122; and financial crises, 112 (see also financial crises); and informational irreducibility, 109–110; investigation of by Gotfried Wilhelm Leibniz, 109; and neoclassical economics, 123–124 (see also neoclassical economics); and network theory, 110; and nonlinear systems, 110–111; and the OODA loop, 122 (see also OODA Loop); and radical uncertainty, 112, 122; and strategic complexity, 122–124 computational irreducibility, 12, 18, 33; crises and, 105; and heuristics, 65; and the Library of Babel, 62–63; and maps, 26; and mathematical shortcuts, 26; and neoclassical economics, 83 (see also neoclassical economics); and three-body problem, 27–28 (see also three-body problem); and Turing’s halting problem, 55 computers, and the universal Turing machine, 54. See also universal Turing machine Conway, John, 30. See also Conway’s Game of Life Conway’s Game of Life: as an agent-based model, 32–33, 122–123; and boids, 37; and computational irreducibility, 32; and context, 122–124; in the context of radical uncertainty, 123–124; emergence in, 32; rules of, 30–31; self-replication features of, 32; and Turing’s halting problem, 55 credit default swaps, 163–165 Cruise, Tom, 94 Darwin, Charles, 72–73 Dawkins, Richard, 181 decimalization, 149 deduction, 15, 107, 124, 180–183, 188–189 degenerative research program, 90–91 Demon of Our Own Design, A, 108, 157 Department of Defense, 158 Deutsche Bank, 165 diversification, 15–16 Dodd-Frank Act, 156–157 Dostoyevsky, Fyodor, 116 Duffie, Darrell, 152–153 dynamic stochastic general equilibrium model, 92 efficient market hypothesis, 116 emergence, 12; and boids, 37; and complexity, 38; and crises, 105; flock of birds movement, example of, 37; and Hajj stampede, 35–36; and heuristics, 65; and limits to knowledge, 52; and neoclassical economics, 83 (see also neoclassical economics); school of fish movement, example of, 36; and stability, 39; stampedes, example of 127–128; traffic example, 95, 97–98; and traffic flow, 17, 94 enclosures, 5 equilibrium, crises of, 104–105 ergodicity, 12, 17–18, 41, 196; context of, 40; history of, 40; and limits to knowledge, 52; and MGonz, 44; and neoclassical economics, 84 (see also neoclassical economics); in physical systems, 40; in physical versus social sciences, 85; testing models of, 177 essayism, 178 eternal recurrence, 60 fallibility, 59, 115, 117; and the rational expectations hypothesis, 175 Feynman, Richard, 54, 90 financial crises: fire marshal analogy, 127–129; financial crisis of 1987, 90; financial crisis of 2008, 92 (see also financial crisis of 2008); structure of, 129 financial crisis of 2008, 157; an agent-based view, 160; contagion during, 160; leverage and, 156, 176; liquidity and, 156; market-to-market difficulties and, 159–164; regulation and, 156; role of AIG in, 163–165; role of Bear Stearns Asset Management (BSAM) in, 161–162 (see also Bear Stearns Asset Management); role of Goldman Sachs in, 163–164 financial institutions: agents of, 99, 106; interactions between, 128–131 financial markets: complexity of, 108–109, 157; crisis in, 14–16, 108–109; environment of, 100–101; fire marshal analogy, 127–128; and Flash Crash, 147–151; and liquidity, 206; and reflexivity, 59; structure of, 128; weather analogy 113, 185–186 Financial Stability Oversight Council, 158 financial system: fire marshal analogy, 129; flows of, 131; multilayer schematic of, 131, 134; schematic system of, 129; structure of, 129, 131 fire sale, 107; asset-based, 138; funding-based, 139 Flash Crash, 147; effect of decimalization on, 149–150; effect of high-frequency trading on, 150; The Price is Right analogy, 148–150 Flaubert, Gustave, 116 Freudianism, 58 Frydman, Roman, 175 funding, 131, 134; cash providers of, 136; and collateral, 137; flows within financial system, 137; and hedge funds, 136; securities lenders for, 136 funding runs, 138–139 Funes, the Memorious, 75–78 Game of Life.

…

Like any other cellular automaton, Life can be thought of as a computational device: the initial state of the cells before running the game can be thought of as an input string, the instruction set for the computation. As the process runs, the state of the cells can be looked at as an output string.12 What can Life compute? It turns out that Life can compute everything a universal Turing machine can and therefore can function as a general-purpose computer: with the right selection of initial conditions, let Life loose and it will be capable of carrying out any computational procedures. The Game of Life is also a stylized version of an agent-based model. The cells are agents that operate based on a simple heuristic laid out by the four rules.

The Fabric of Reality
by David Deutsch
Published 31 Mar 2012

problem 337 Life of Johnson (Boswell) 86 light ������bending of 37�40 ������ductility of 38 ������laser 34, 40 ������speed of 44, 99, 105, 107, 125, 160, 348 ������spreading 34, 38 ������white 38�9, 39 ������see also photons logic 20, 161, 168, 229, 231, 248�9 Aristotelian 254 ������law of the excluded middle 232�3 ������limitations of 225 ������and mathematical intuition 231, 232 ������rules of inference see rules of inference symbolic 230 ������logical positivism see positivism logically possible/impossible see under environment; experience master builder 13�15, 358�9 mathematical intuition see under intuition mathematical questions ������computable 132, 133 ������non�computable 132�3 mathematical theorems 146, 227�8, 230, 234, 236, 247 mathematics 20, 199, 221, 228, 236, 256 ������and the behaviour of physical objects 133, 253�5 ������certainty in 224, 226, 230, 233�4, 236, 238, 240 ������creativity as central to 236, 240 ������and explanation 253 ������and nature 73, 74, 76, 94 ������the objective of 253 ������as the study of absolutely necessary truths 253 ������and the theory of computation 98 ������understanding in 10 ������and virtual reality 120, 131 Maxwell, James Clerk 9 medicine, specialization in 16 memes 171, 187, 193, 336, 346, 360 Mercury 56 meta�mathematics see proof theory Milky Way 177 mind 11, 90, 352 ������as a computer program 352, 353 ������and mathematical certainties 236 ������and problem�solving 71, 72, 76 ������and solipsism 58, 70, 80, 82, 83 ������and time travel 310 ������and virtual reality 106, 111�12 ������see also thought morality 359�63, 364, 365�6 ������must be objective 364 motion, laws of 20, 24�7, 213, 337, 338 multiverse 46, 47, 48, 53, 58, 95, 185, 187, 190, 191, 206, 207, 211, 212, {381} 212, 275�80, 277, 281, 283, 287, 305, 330. 335, 338, 339, 366 ������causes and effects in 276, 286 ������and DNA 189, 190, 190 ������as a jigsaw puzzle 285 ������and the omega point 352, 364 ������and parallel spacetimes 289�90 ������and parallel universes 54 ������and philosophical problems 339�40 ������and physically possible processes 105, 135 ������and quantum theory 50 ������reality as a 54, 288 ������and time travel 306, 307, 308, 310, 312, 316, 318 ������and virtual reality 103, 357 mutation 68, 188, 189 The Myth of the Framework (Popper) 323 natural numbers see under numbers natural selection 315, 332, 333 nature laws of 255, 337; see also laws of physics ������and mathematics 73, 74, 76, 94 ������as physics 169 ������quantum computation harnesses 195, 221 Neptune, discovery of 56 Newton, Isaac 2, 3, 17, 56, 85, 93, 266�7, 269, 324, 337, 344 ������concept of time 266�7 niches 68, 121, 172, 174, 175, 179, 181, 182, 187, 188, 193, 315, 316, 333 nuclear physics 18, 23, 182 numbers ������arabic notation 9 ������and the diagonal argument 126 ������factorization 104, 199�200, 215�16 ������imaginary 227�8 ������infinite 228 ������multiplying large 198�9 ������natural 223, 226, 228, 231, 232�3, 242 ������negative 227 ������prime 133, 199, 215, 223, 224, 228 real 227�8 ������Roman numerals 9�12 numerology 63 observation(s) 76, 224 ������and arguments 69, 147 ������and the Copenhagen interpretation 327�8 ������and explanation 75, 224, 225 ������extrapolating 59, 60�61, 71 ������and inductivism 59, 60, 61, 69, 149 ������and justification of theories 59, 60, 156 ������and prediction 60, 61, 75, 141 ������and reality 74 ������and theories 59�62, 69, 71, 77, 141, 224, 225 ������unexpected 62�3 ������virtual reality and 225 Occam's razor 78, 96, 137, 160 omega�point theory 347�59, 364, 365 'On the Infinite' (Hilbert) 250 On the Plurality of Worlds (Lewis) 340 The Open Society and its Enemies (Popper) 344 oracle ������and experimentation 4, 5 ������and instrumentalists 4, 6 ������physical world as an 5�6 ������and theories 4, 5, 6 organism ������DNA 173, 175 ������life�style 175 ������niche of 172 ������as part of the environment of replicator's 175, 176 ������rendered 178�9 ������not a replicator 175�6 origin of species 315, 316, 332, 333 {382} Page, Don 278 paper 120, 131, 246, 252�3 paradigm 321, 330, 331, 334, 342 ������succession 323�4, 327, 332 parallel axiom 247 parallel universes 53, 57, 60, 89, 95, 136�7, 207, 221, 305, 308, 353 ������and Bohm's theory 93�4 ������as distinguished only by what happens in them 307 ������and Dr Johnson's criterion 88�9 ������existence revealed 32�3 ������and genes 187�191, 190 ������and interference 59, 168, 213 ������and the multiverse 46, 54 ������quantum computation and 195, 220 ������quantum theory of 51 ������and randomness 202�4 ������rendering of 300, 357 ������stacked 211 ������and the weather 202 ������and time 278, 305 particle accelerators 5, 19 particle physics 8 past, changing the 309�10 Penrose, Roger 132, 236�40, 255, 331 penumbras 36, 37, 37, 38, 39, 42 perception 57; ������see also sensations perfect accuracy see under accuracy photons 4, 35, 35, 38, 41�4, 53, 88, 89, 188, 202, 204, 205, 206, 207, 209, 218, 219; ������see also light physically possible/impossible see under environment; virtual�reality generators physics ������classical, and chaos theory 201 ������and complexity 21, 197 ������geometry incorporated into 17�18 ������laws of see laws of physics ������nature as 169 ������Newtonian 169, 268, 270 ������split into specializations 8 ������subatomic 27, 169 ������swallows up hitherto unrelated ������subjects 344 ������and the theory of everything 21 ������and the Turing principle see under Turing principle The Physics of Immortality (Tipler) 347 Planck time 284, 312 planetarium 77�8, 91, 92, 95, 136 planets 68, 107 ������motions of the 1�4, 12, 13, 56, 60, 66, 78�9, 85�9, 92, 201, 240, 337 ������and stars 55 ������wandering 60, 62, 63 Plato 226, 227, 231, 236, 240�43, 245, 255 Popper, Karl/Popperian v, 76, 141�9, 151, 154, 157, 158, 165�6, 322, 323, 331, 334, 345, 365 ������and artificial intelligence 331 ������and corroboration 145 ������critics of Popperian epistemology 340 ������and explanations leading to new problems 139 ������and the future growth of knowledge 359 ������on history 344 ������and induction 144, 146, 156 ������and justification 156 ������and the theory of evolution 341 ������theory of scientific knowledge 62, 68, 315, 335�6 positivism 6, 29�30, 48, 75, 84, 341 ������and the Copenhagen interpretation 328 Post, Emil 131, 133, 252 pragmatic instrumentalism 48, 329 prediction 48, 85 ������in astronomy 2, 3, 4, 56�7, 73, 185 ������by an oracle 4, 5 ������conflicting 65 ������correct 65, 145�9 ������and explanation 5, 6, 8, 11, 62, 64�5, 66, 76 {383} ������false 7, 65, 142 ������and inductivism 69 ������and instrumentalism 3, 21 ������justification of 146, 147, 161�2, 164 ������and laws of motion 20, 25, 26 ������limitations in classical physics 201 ������limitations in quantum physics 202�3 ������in the multiverse 283 ������and Newtonian physics 270 ������and observation 60, 61, 75, 141 ������as part of the characteristic method of science 6 ������and positivism 6 ������in pre�quantum physics 270 ������in principle 2 ������probabilistic 280, 281; ������see also probability ������and quantum theory 25, 44, 50�51, 203�4, 280, 329 ������theories and 2, 3, 4, 6�7, 30, 60, 117, 118, 147, 156, 162 ������and the theory of everything 18�19, 22, 235 ������and the theory of evolution 362 predictive emergence 362 prime pair 133 Principia (Newton) 266�7 principle of increasing entropy see thermodynamics, second law of 'principle of induction' see under induction prions 171 probability 18, 22, 59, 116, 203�4, 280�81 307 problem 62, 64, 65, 70, 141 ������backtracking 67 ������emergent properties of 68 ������of induction see induction ������new 62�3, 64, 65 ������scientific 70 ������variants of 67 problem�situation 148, 153, 154, 156, 157, 161, 315 problem�solving 55�72, 80, 323 ������by the brain 238 ������and reality 76 ������science and 62, 65, 70, 76 proof 131, 224, 227, 244, 256 ������and certainty 224, 225, 227, 256 ������and experiment 224 ������and explanation 236 ������methods of 227, 229, 230, 233, 239, 246, 256�7 ������new types of 136 ������number of steps 249�50, 251 ������as a physical process 246, 248 ������quantum 251�2 ������role in mathematics 224 ������and syllogisms 229�30 ������traditional definition 245 ������as a type of computation 246 proof theory 229�30, 231, 234, 248, 344 proteins 171 Ptolemaic system 9; ������see also geocentric theory public�key cryptography 215, 217, 219 punctuated equilibrium theory 334, 335 Pythagoras 226, 238 quantization 35�6, 54, 127 quantum computation see under computation quantum computers see under computers quantum cosmology 330, 335 quantum cryptography 218 quantum factorization engine 215�16, 217, 220 quantum gates 214 quantum mechanics ������and the 'butterfly effect' 202, 203 ������Copenhagen interpretation 327�8, 329, 335, 342 ������interpretation of 335 ������intractability in 203 ������and parallel universes 319 {384} ������and 'snapshots' 317 ������and tossing a coin 282 ������unpredictability in 203 ������see also quantum theory quantum optics 32 quantum physics 32�54, 194�221, 258�88, 289�320, 321�43, 344�66 ������links with epistemology and computation 344 quantum theory 8, 23�4, 32�54, 53, 157, 211, 228, 313, 328�9, 338 ������as about the 'interaction of the real with the possible' 48 ������of computation see under computation ������determinism of 281 ������and discrete steps 250 ������and the general theory of relativity 134, 177 ������and a multiverse 50, 328 ������and the nature of time 27, 278 ������as one of the four main strands of explanation 24, 28, 30�31 ������and parallel universes 51 ������and prediction 25, 44, 50�51, 203�4, 280, 329 ������and quantization 35�6, 54, 127 ������and reality 24, 50 ������and the theory of evolution 190�93 quantum theory of gravity 24, 277 quantum/quanta 35 quasars 12�13 Quirk, Randolph 258, 260 randomness ������explaining unpredictable events 8, 22 ������and free will 338 ������multiverse view of 203, 279�82 ������random DNA sequences 173, 188 ������see also probability rationality 80, 86, 169, 240, 328, 329, 331, 335 ������incompatible with faith 169 ������principles of 156, 161, 162, 163, 331 ������see also reason realism 74, 85, 96, 329 ������and common sense 74, 83, 84 ������solipsism disguised as 84, 97 reality ������as bigger than it seems 45, 136 ������and Bohm's theory 93�4 ������comprehensible 138, 140 ������criteria for 73�97 ������Dr Johnson's criterion for 86�93, 97, 101 ������existence of entities in 222 ������Galileo's conception of 94 ������and 'kicking back' 86�90, 92, 97, 101, 223 ������and multiverse 46 ������of natural numbers 222 ������not affected by 'the possible' 48 ������objective 240 ������physical 24, 74, 168, 186, 255, 267, 272, 275, 291, 297, 298, 327 ������Platonic 226�7 ������quantum theory and 24, 50 ������as quantum�mechanical 201 ������reason and 81 ������and reductionism 25 ������and scientific reasoning 97 ������self�similarity of 95, 98, 134, 140 ������and solipsism 58, 83 ������and substantial computation 92 ������understanding the whole of 117 ������a unified conception of 29, 30 ������virtual see virtual reality reason ix, 72, 74, 76, 81, 227; ������see also rationality red giant 183, 184, 186, 353 reductionism 19, 21, 27, 30, 84, 169, 176, 345 ������and explanation 21, 24 ������extended sense of 347 ������and holism 21 ������and mathematics 235 {385} ������and reality 25 ������science as reductionist 19 ������and the theory of everything 20 ������world�view 23, 343 refutation 65, 150, 332 ������experimental 65 ������and the growth of knowledge 68 ������of inductivism see induction ������of intuitionism 231�3 ������and Hilbert's tenth problem 234 ������of obsolete theories 335 ������of solipsism 85 ������of theories see under theories relativity, general theory of 2�3, 12, 56, 89, 145, 157, 159, 228, 238, 239, 247, 268, 312, 344 ������Einstein's equations 311�12 ������incorporates geometry into physics 17�18, 344 ������'unphysical' solutions 311 ������������see also gravity relativity, special theory of 290 rendering see virtual reality repertoire ������of abstract computers 132, 133�4 ������of image generator 105�11 ������and internal experiences 104 ������of master builder 14 ������of Turing machines 132 ������of universal quantum computer 210 ������of virtual�reality generators see under virtual�reality generators replicator(s) 170�71, 188, 192, 334 ������adaptation to its niche 174, 177, 180 ������contributes causally to its own copying 172, 173, 274 ������highly adapted 174, 340 ������variants 174, 274 ������see also genes; memes resurrection of the dead 357�8 retrodiction 270, 282 Reviews of Modern Physics 328 Rivest, Ronald 215 RNA 171, 192 Roman numerals 9�10, 11, 12 rotation 224 roulette wheel 115�16 RSA cryptosystem 215, 216 rules of inference 163, 229, 230, 233, 234, 236, 237, 245, 250, 251, 256 rules of thumb 14�15, 16, 253 Russell, Bertrand 60, 61, 230, 254 Schwarzschild, Karl 311 Sciama, Dennis 335 science ������'normal' 322 ������problem�solving in 62, 65, 70, 76 ������purpose of 4, 7, 71, 117 ������and reductionism 19, 20, 21 ������'revolutionary' 322, 334 ������and virtual reality 117�18, 135 scientific discovery compared with biological evolution 68, 71 ������the course of 65, 67 ������and experimental tests 65 ������and an unexpected observation 62�3 scientific methodology 6�7, 65, 70, 73, 143, 144, 147, 149, 332, 340 ������in practice 325�7 scientific reasoning and inaccurate experiences 136 ������reliability of 94, 97 ������and virtual reality 101 self�similarity 95�8, 96, 134, 135, 140, 47 The Selfish Gene (Dawkins) 176, 334 'selfish gene' theory 334, 340 sensations 52, 87, 92, 105�10, 254 sensory isolation 104�5, 125, 128 sets 224, 228, 230, 231, 254 shadow particles/photons 43�9, 52, 53, 88, 93 shadows 32�55, 58, 59, 168, 206, 207 ������penumbras of 36�7, 37 {386} ������umbras of 36, 37 Shakespeare, William 258, 259, 314, 315 Shamir, Adi 215 Shor, Peter 215 Shor's algorithm 215, 216�17 snapshots see under time sociobiology 360 solipsism 58, 70, 80, 81, 137, 287 ������and the angel theory of planetary motion 88 ������central thesis of 81 ������defence of 81�2 ������and explanation 97, 142, 233 ������as indefensible 82, 84 ������and intuitionism 231, 232, 233 ������joke 81 ������as realism disguised 83�4, 97 ������refutation of 97, 102 ������variants 85 sound reproduction 109�10 space ������curved 3, 4, 12, 23, 56, 57, 86, 89 ������three�dimensional 267�8 ������and time 268 spaceflight simulators 107 spacetime 267, 268, 268, 288, 355 ������as the 'block universe' 268, 270 ������curvature 159, 161 ������and 'Faraday's death in 1830' premise 274�6 ������as a four�dimensional entity 268 ������as incompatible with the existence of cause and effect 274 ������omega�point 349�50 ������parallel spacetimes 289�90 ������shuffled 271, 272, 282�3 ������as unchanging 338 spacetime physics 269, 270, 274, 275, 279, 283, 285, 288, 309, 338 special�purpose quantum computer ������see under computers specialization 8�9 ������in medicine 16 spectral types 185 stellar evolution 182�3, 185 The Structure of Scientific Revolutions (Kuhn) 321 subatomic particles 18, 20, 21, 23, 96 Sun ������control of 183�4, 353 ������future development 183, 184, 186, 353 ������heliocentric theory 9, 56, 73, 96, 169 ������and the 'Inquisition's theory' 77 ������and the solar system 177 source of energy 182 superconductivity 214 superfluidity 214 supermarkets, virtual�reality 101 superstring theory 23 survival of the fittest 333 syllogisms 229, 230 symbolic logic see under logic symbols ������and abstract entities 245, 246 ������as physical objects 127, 241 tangible particles 43�7, 48, 49, 52, 53, 53 theories 9 ������amended 64, 68 ������becoming deeper 13, 14�15, 16, 17, 30 ������becoming fewer 13, 14�15, 17 ������becoming more general 13, 14�15, 16, 17, 30 ������as conjectural 64, 69, 71, 141 ������corroboration of see corroboration ������demotion of 11, 13 ������and evolution 68 ������explanation and 2�3, 4, 7, 60, 66, 71, 76, 80�81, 117, 118, 157, 332 ������genes as 315 ������as imperfect 17 ������implicit 9 ������inborn 121, 136 ������justification of see justification {387} ������languages as 153 ������logical relationships between 28 ������and observations 59�62, 69, 71, 77, 141, 156, 224, 225 ������and an oracle 4, 5, 6 ������postulating anomalies 155, 156 ������and predictions 2, 3, 4, 6�7, 30, 60, 117, 118, 147, 156, 162 ������as programs 121 ������proposed new 64 ������refutation of 142, 147�51, 321, 335 ������rejection of 7, 64�7, 147, 152, 160 ������rival 65, 148 ������selection of 68, 69, 71, 142 ������superseding old ones 9, 17�18, 30, ������unconscious 121 ������unifying two old ones 9 ������variants of 68, 150 Theory of Everything 17, 19 ������as the first fully universal theory 18 ������and the four main strands of ������explanation 28�9, 30�31, 345 theory of everything 19, 20, 21, 22, 23, 169 ������and explanation 19 ������and the initial state 19, 24 ������particle physicists and 18, 30 ������and prediction 18�19, 22, 235 ������and a quantum theory of gravity 24 thermodynamics 8, 164 ������second law of (principle of increasing entropy) 286, 345 thought(s) ������as an emergent phenomenon 21 ������and the fabric of reality 3 ������and machines 238 ������and solipsism 83 ������virtual�reality renderings 352 ������and a wider universe 138 ������see also mind time ������breakdown of sequence of 283�5 ������common�sense concept of, see under common sense ������as a continuum 267 ������dilation 290�91 ������'flow' of 141, 258, 261, 263�6, 269, 270, 284, 287, 287, 288, 309 ������as a fourth dimension 267 ������mystery of 258, 260 ������Newtonian concept 266�7 ������and physical intuition 253�4 ������the present moment ('now') 258�65, ZS9, 260, 262 ������quantum concept of 257, 278, 287, ������305, 310, 319 ������and quantum theory 27 ������'snapshots' 259, 260, 260, 261, 263, 265, 267, 270�72, 276�86, 288, 290, 291, 300, 304, 305, 309, 310, 316, 318 ������and virtual�reality generators 125 ������see also clocks and calendars; spacetime time machines 289, 292�301, 299, 304�8, 310, 313, 314�15, 317, 318, 319 'time stamps' 272, 278, 283 time travel 288, 289�320, 319, 320, 344 ������attempt to enact a paradox 305�6, 306, 311, 317 ������collision avoidance 299�300, 314 ������and epistemology 315 ������and evolution 315 ������future�directed 290, 291, 312, 319 ������grandfather paradox 293, 319 ������and inter�universe travel 310 ������knowledge paradox 314, 315, 316, 319 ������multiple copies of the time traveller 299, 299, 301�8, 311 ������paradoxes of 293, 294, 295, 307, 312, 314, 315, 319 ������past�directed 290, 291, 293, 295�6, 298, 310, 312�13, 319 ������physically possible 311 {388} ������present�directed 291 ������spacetime path 296 Tipler, Frank 185�6, 347, 349, 351, 353�8, 364�5, 366 Toffoli, Tomasso 346 tractability 196, 198, 220 Turing, Alan v, 133, 325 ������and Cantgotu experiments 128 ������and classical mechanics 210, 211 ������modern theory of computation 126, 131, 132, 252, 335, 336, 339, 366 ������see also Church�Turing conjecture Turing machines 131�2, 140, 194, 195, 210, 213, 218, 250, 252 ������universal 132, 134, 140 Turing principle 132, 134, 140, 193, 197, 193, 340, 341 ������as the best theory of the foundations of computation 350 ������as a fundamental principle of nature 354 ������and the laws of physics 136, 181, 197 ������links physics and the theory of computation 340 ������and the omega�point theory 348, 351 ������Penrose and 132, 237, 240 ������and the physical embodiment of knowledge 181, 182 ������and self�similarity 347 ������strong form 134, 135, 136 ������universal computer/computation 132, 221, 330�31, 353, 354 ������universal virtual�reality generator 134, 135, 163�4, 292, 303, 348 ������virtual reality first realized in nature 181�2, 193 ������see also Church�Turing conjecture umbra 36, 37, 38, 39 unconsciousness 104 understanding 342 ������everything that is understood 1, 8, 9, 10, 13, 16�17, 30 ������explanations and 11, 224 ������extended into new areas 15 ������and the four main strands of explanation 28 ������implicit 11�12 ������increased understanding with less learning 9 ������in mathematics 10, 234 ������as the motivation for science 4 ������and observation 224 ������of quantum interference 168 ������and unifications 18 ������and world�view shifts 18 universal auditory sensation generator 110 universal image generators 109�11, 121, 129, 134 universal quantum computer see under computers universal quantum simulator 210 universal Turing machine 132, 134, 139 universal virtual�reality generator 130�31, 134, 135, 137, 139 universality ������computational 97, 195�6, 197, 108, 221, 239, 252, 350 ������and explanations 29 ������and intractability 208 ������quantum computers and 219 ������of the universal Turing machine 134 ������and virtual�reality generators see under virtual�reality generators universe 46, 169 ������block see spacetime ������colonizing 353 ������as a computer 346 ������expanding 311, 348 ������experience of a single 136, 141 ������finite in space and time 348�9 ������initial state 25, 26, 27 ������life affecting the structure of 186 ������and reality 45, 52, 54, 74 ������recollapse of 162, 355 {389} ������������see also multiverse; parallel universes unpredictability 203, 208, 220; ������see also probability utilitarianism 361, 362, 363 variation and selection 68, 182, 188, 331 Venus, phases of 77 video games, virtual�reality 100, 103, 127�8, 137 virtual reality 98�122, 255 ������based on the wrong laws 136 ������and future�directed time travel 290 ������as interactive 113, 114 ������and living processes 175 ������and mathematical truths 255, 257 ������and science 117�18, 135 ������and observation 225 ������and proof 224 ������and rendering logically possible environments 129 ������theory of 243 ������ultimate limits of 105, 196 virtual�reality generators 99, 102, 103, 104, 111, 116, 117, 225, 297�8, 300�304, 306�8 ������and the brain 121, 124�5, 126 ������and Cantgotu environments 128 ������and externally elapsed time 125 ������and the laws of physics 243�4 ������and past�directed time travel 291, 293 ������physically possible 126, 133, 135 ������principal components 112 ������rendering 118�19, 179, 243, 244, 245, 291, 295, 297, 298�9, 307 ������repertoire 105, 122, 124, 126, 128�9, 130, 134, 135, 140, 164 ������and time machines 318 ������and the Turing principle 134, 135, 163�4, 181 ������ultimate 123�6, 129 ������universal 124, 130�31, 134, 135, 137, 139, 163�4, 197, 291, 191, 303, 310, 340, 348 ������'working memory' 123�4 war 22, 184, 185 Watkins, John 144 weather 6, 63, 98, 200�201, 202 weightlessness 106, 107, 108 Weinberg, Steven ������pointlessness of the universe 346 ������unimportance of explanation 3�4 Wheeler, John Archibald 328 'Why Both Popper and Watkins Fail to Solve the Problem of Induction' (Worrall) 143�4 Wickramasinghe, Chandra 333 Wooters, William 278 world�view 62, 75, 83, 97, 159, 161, 169, 318�19, 321, 331, 335 ������Darwin and 337 ������ever greater changes in 57 ������and misleading phenomena 103 ������and moral values 359, 361 ������and the multiverse 48 ������Newtonian 56, 58 ������Penrose and 239, 240 ������positivism rejected as a 84 ������and problem�solving 68 ������reductionist 23, 345, 347 ������single�universe 93, 217 ������and a Theory of Everything 18 ������unified 366 Worrall, John 143�4 Zeno of Elea 249 {390} * * * * In Freedom and Rationality: Essays in Honour of John Watkins

…

His abstract computer, the Turing machine, was abstracted from the idea of a paper tape divided into squares, with one of a finite {131} number of easily distinguishable symbols written on each square Computation was performed by examining one square at a time moving the tape backwards or forwards, and erasing or writing one of the symbols according to simple, unambiguous rules. Turing proved that one particular computer of this type, the universal Turing machine, had the combined repertoire of all other Turing machines. He conjectured that this repertoire consisted precisely of 'every function that would naturally be regarded as computable'. He meant computable by mathematicians. But mathematicians are rather untypical physical objects. Why should we assume that rendering them in the act of performing calculations is the ultimate in computational tasks?

…

The mathematician Roger Penrose has suggested that it should be called the Turing principle: The Turing principle (for abstract computers simulating physical objects) There exists an abstract universal computer whose repertoire includes any computation that any physically possible object can perform. Turing believed that the 'universal computer' in question was the universal Turing machine. To take account of the wider repertoire of quantum computers, I have stated the principle in a form that does not specify which particular 'abstract computer' does the job. The proof I have given of the existence of Cantgotu environments is essentially due to Turing. As I said, he was not thinking explicitly in terms of virtual reality, but an 'environment that can be rendered' does correspond to a class of mathematical questions whose answers can be calculated.

The Computer Boys Take Over: Computers, Programmers, and the Politics of Technical Expertise
by Nathan L. Ensmenger
Published 31 Jul 2010

This means that in theory at least, all computers are functionally equivalent: any given computer is but a specific implementation of a more general abstraction known as a Universal Turing Machine. It is the Platonic ideal of the Universal Turing Machine, and not the messy reality of actual physical computers, that is the true subject of modern theoretical computer science; it is only by treating the computer as an abstraction, a mathematical construct, that theoretical computer scientists lay claim to their field being a legitimate scientific, rather than merely a technical or engineering, discipline. The story of this remarkable self-construction and its consequences is the subject of chapter 5. The idealized Universal Turing Machine is, of course, only a conceptual device, a convenient fiction concocted by the mathematician Alan Turing in the late 1930s as a means of exploring a long-standing puzzle in theoretical mathematics known as the Entscheidungsproblem.

…

By abstracting the logical design of the digital computer from any particular physical implementation, von Neumann took a crucial first step in the development of a modern theory of computation.55 His was not the only contribution; in 1937, for example, Turing had described, for the purposes of demonstrating the limits of computation, what would become known as the Universal Turing Machine. Eventually, the Universal Turing Machine would become an even more fundamental construct of modern computer science. According to the Church-Turing thesis, first articulated in 1943 by the mathematician Stephen Kleene, any function that can be physically computed can be computed by a Universal Turing Machine. The abstraction of the technology of computing in the theoretical construct of the Turing Machine mirrored the shift toward software that was occurring in the larger commercial computing industry.

…

As a computing device, the Turing Machine is deceptively simple; as a conceptual abstraction, it is extraordinarily powerful. As it turns out, the table of instructions for any Turing Machine can be rewritten to contain the instructions for building any other Turing Machine. The implication, as articulated in the Church-Turing thesis, is that every Turing Machine is a Universal Turing Machine, and by extension, every computing machine is essentially equivalent. In the real world, the appealingly egalitarian abstractions of the Church-Turing thesis quickly break down in the face of the temporal and spatial constraints of the physical universe. To implement even the simplest computations on an archetypal paper tape–based Turing Machine, for example, would require an enormous and prohibitive amount of resources.

The Secret War Between Downloading and Uploading: Tales of the Computer as Culture Machine
by Peter Lunenfeld
Published 31 Mar 2011

In it, he proposed the questions that still remain central to the discipline decades later. Turing suggested that it should be possible to make a “Universal Machine,” a computer that could simulate the performance of any other device. The fact that the analog machines of the late 1930s and early 1940s were far too slow to function as Universal Turing Machines did not affect his faith that such devices would come into existence. And with the stimulus of the war effort, they did. Within a decade, Turing was working on the Manchester Mark I computer—one of the first machines recognized as being a direct antecedent to the computers we use now. Turing proposed a universal machine that functioned as a stored program computer; in this setup, the programs, or software, could be swapped and modified, improved and abandoned, just as the hardware could and would be.

…

He assisted Christopher Strachey in producing what was probably the first artwork made with a computer: the love letter generator of 1952. 5 Strachey, working from a thousand-line piece of software (the longest yet written for the Mark I), created a program that randomly produced such sentimental and vaguely meaningless missives as: 18 STICK Y Darling Sweetheart, You are my avid fellow feeling. My affection curiously clings to your passionate wish. My liking yearns for your heart. You are my wistful sympathy: my tender liking. Yours beautifully M. U. C. Here, the Universal Turing Machine simulates mawkish Victorian sentimentality by choosing from a database of prewritten phrases that it then arranges into syntactically correct but stilted English. This trifle, inspired at least in part by the renown of Christopher’s uncle Lytton Strachey’s 1918 portrait of a generation, Eminent Victorians, is the product of a stored program computer, and as such may well be the first aesthetic object produced by the ancestors of the culture machine.

…

Congress and, 90 violations of, 92–93, 95 Web n.0 and, 88–95 Corian, 64 Creative Commons, 173, 189n12 bespoke futures and, 123 Mickey Mouse Protection Act and, 90 Computers (continued) Aquarians and, xv, 24, 144, 152, 157, 159–169 challenge to television of, 2 as culture machine, xiv, xvi, xv–xvi, 5 (see also Culture machine) distribution and, xiii dominance of, xii–xiii, xiv as dream machines, xiii emergence of, xii–xiii first, 146 hackers and, 22–23, 54, 67, 69, 162, 170–173 historical perspective on, 143–178 Hosts and, xv, 144, 167, 175 Hustlers and, xv, 144, 156, 162–167 intelligence test for, 19 as “Man of the Year,” xii Moore’s law and, 156, 195n13 mouse for, 158–159 participation and, xvi, 15–17, 27–35, 54, 66–67, 74–80, 98–99, 120– 121, 129, 143–147, 151, 156–165, 170, 175–178 Patriarchs and, xv, 143–144, 147–153, 156–157, 162–163, 166–168 personal, 152, 161–167 Plutocrats and, xv, 144, 152–159, 163–166, 170 production and, xiii relationship with data and, 32 Searchers and, xv–xvi, 144, 167, 174–178 simulation and, xvi, 2 (see also Simulation) Sterling on, 101–102 symbiosis and, 151–152 systems theory and, 151 ubiquity and, xiii, 22–23, 39, 57–59, 62, 74, 81–82, 87, 92–93, 125, 128, 144, 166, 177–178 Universal Turing Machine and, 18–19 201 INDEX Creative Commons (continued) open source and, 90–93, 123, 173 purpose of, 91 Web n.0 and, 90–93 Creatives, 30 Credit cards, 76 Crenshaw district, 105 Critical inquiry, 14 Cuban Missile Crisis, xi Cubism, 44, 79, 117 Cultural issues commercialism and, 4–5, 8 (see also Commercial culture) diabetic technologies and, 3–5 dominance of television and, xii, 2–5, 7–10 fan culture and, 28–32, 48, 49, 87 free culture and, 75, 92, 98–99 Freud and, 43–44 hierarchies and, 1, 24, 29, 93, 114 junk culture and, 5–10 mass/pop culture and, 13, 31, 39–40, 47–48, 53, 56–58, 61–63, 107, 109, 184n16 mechanization and, 44–45 open source and, 36, 61, 69, 74–75, 91–92, 116, 121–126, 144, 170– 173, 177, 189n12 psychology and, 16, 21–22, 42–44, 56, 151, 161 secular culture and, 133–139 Slow Food and, 5–7 stickiness and, 28–32 (see also Stickiness) Culture machine, 5 Aquarians and, xv, 24, 144, 152, 157, 159–169 bespoke futures and, 97–101, 116, 123–133, 137–138 design and, 139, 150, 160, 165, 167, 171–172, 176 development of, 143–178 downloading and, 143, 168 gaming and, 70–74 Hosts and, xv, 144, 167, 175 Hustlers and, xv, 144, 156, 162–167 information and, 46, 143–149, 152– 153, 163, 167–168, 172, 176–178 networks and, 143–144, 152, 167– 168, 172–175, 178 participation and, 15–17, 143–147, 151, 156–165, 170, 175–178 Patriarchs and, xv, 143–144, 147–153, 156–157, 162–163, 166–168 Plutocrats and, xv, 144, 152–159, 163–166, 170 postmodernism and, 39–40 Searchers and, xv–xvi, 144, 167, 174–178 simulation and, 15–17, 143–144, 147– 152, 156–160, 166–168, 175–178 stickiness and, 15–19, 27, 32, 35 technology and, 143–163, 173–174 unimodernism and, 39, 42, 46–60, 67–76 uploading and, 143, 168, 173, 175 Warriors and, 146–147 Web n.0 and, 79–85, 90–93 Cut-up fiction, 52 Cyberpunk, 68, 87, 110 Czechoslovakia, 104 Dada, 79, 186n8 Danger Mouse, 54–55 Dare, Dan, 108 Darth Vader, 90 Darwin, Charles, 133 Davis, Miles, 25–26 Dawkins, Richard, 143 Death and Life of Great American Cities, The (Jacobs), 84–85 Deconstruction, 29–31 DeLanda, Manuel, 189n8 De.lic.ious, 75 202 INDEX Design bespoke futures and, 102, 105–106, 110–111, 115–116, 119–120, 124–125, 137 control over form and, 111 culture machine and, 139, 150, 160, 165, 167, 171–172, 176 future as client and, 110–113 futurists on, 101–102 graphic, 31, 45, 64, 102, 181n7 Gropius and, 36–37 isotypes and, 44, 125, 193n34 mechanization and, 44–45 Moore’s law and, 156 open source, 36, 61, 69, 74–75, 91–92, 116, 121–126, 144, 170– 173, 177, 189n12 play and, 32–34 postmodernism and, 29–30, 39–41, 74, 79, 130, 135 power and, 32–34 tweaking and, 32–35 unimodernism and, 39, 43–46, 49, 55–56, 60, 64–8, 71–74 Design of Everyday Things, The (Norman), 16 Design Within Reach, 46 Desk jobs, 3 Dewey, John, 129 Dewey, Melvil, 80 Diabetes, 3–5, 8 “Diamond Dogs” (Bowie), 62 Dick, Philip K., 9 Difference engine, 149 Digg, 34 Digital Equipment Corporation (DEC), 71, 149, 153, 163, 170 Digital video discs (DVDs), 2, 7–8, 15, 58 Digital video recorders (DVRs), 2, 7, 15, 23, 181n3 Disco, 63 Disney Concert Hall, 39 DIY (do-it-yourself) movements, 67–70 203 Dot-com bubble, 79, 145, 174 Doubleclick, 177 Downloading, xiii–xiv, 180nn1,2 animal kingdom and, 1 bespoke futures and, 97, 123, 132, 138 best use and, 13–14 commercial networks and, 4–5 communication devices and, 15–16 cultural hierarchy of, 1–2 culture machine and, 143, 168 dangers of overabundance and, 7–10 defined, 1 diabetic responses to, 3–5 disrupting flow and, 23–24 figure/ground and, xvi, 42–43, 46, 102 Freedom software and, 22–23 habits of mind and, 9–10 humans and, 1–2 information overload and, 22, 149 info-triage and, xvi, 20–23, 121, 132, 143 as intake, 5 mindfulness and, xvi, 14, 17, 20–24, 27–29, 42, 77, 79, 123, 129, 183n6 patio potato and, 9–10, 13 peer-to-peer networks and, 15, 54, 92, 116, 126 stickiness and, 13–17, 20–23, 27–29, 184n15 surfing and, 20, 80, 180n2 television and, 2 unimodernism and, 41–42, 49, 54–57, 66–67, 76–77 viral distribution and, 30, 56, 169 wants vs. needs and, 13, 37, 57 Web n.0 and, 79, 82–83, 86–87 Duchamp, Marcel, 44, 48, 94 Dymaxion map, 73 Dynabook, 161–162, 196n17 Dynamic equilibrium, 117–120 EBay, 68 Eckert, J.

The Information: A History, a Theory, a Flood
by James Gleick
Published 1 Mar 2011

Free from all the real world’s messiness, free from creaking wheel-work and finical electricity, free from any need for speed, the Turing machine was the ideal computer. Von Neumann, too, had kept coming back to Turing machines. They were the ever-handy lab mice of computer theory. Turing’s U had a transcendent power: a universal Turing machine can simulate any other digital computer, so computer scientists can disregard the messy details of any particular make or model. This is liberating. Claude Shannon, having moved from Bell Labs to MIT, reanalyzed the Turing machine in 1956. He stripped it down to the smallest possible skeleton, proving that the universal computer could be constructed with just two internal states, or with just two symbols, 0 and 1, or blank and nonblank.

…

On the way to its formalization, an obvious difficulty arises: something that can be described simply in one language may not have a simple description in another and it is not clear what method of description should be chosen.♦ That difficulty is solved by using computer language. It does not matter which computer language, because they are all equivalent, reducible to the language of a universal Turing machine. The Kolmogorov complexity of an object is the size, in bits, of the shortest algorithm needed to generate it. This is also the amount of information. And it is also the degree of randomness—Kolmogorov declared “a new conception of the notion ‘random’ corresponding to the natural assumption that randomness is the absence of regularity.”♦ The three are fundamentally equivalent: information, randomness, and complexity—three powerful abstractions, bound all along like secret lovers.

…

Chaitin and Kolmogorov revived Berry’s paradox in inventing algorithmic information theory. An algorithm names a number. “The paradox originally talks about English, but that’s much too vague,”♦ Chaitin says. “I pick a computer-programming language instead.” Naturally he picks the language of a universal Turing machine. And then what does it mean, how do you name an integer? Well, you name an integer by giving a way to calculate it. A program names an integer if its output is that integer—you know, it outputs that integer, just one, and then it stops. Asking whether a number is interesting is the inverse of asking whether it is random.

Silence on the Wire: A Field Guide to Passive Reconnaissance and Indirect Attacks
by Michal Zalewski
Published 4 Apr 2005

The only problem is that every algorithm requires the implementation of a separate set of transition rules and internal states; in other words, we need to build a new Turing machine for every new task, which is not quite practical in the long run. Thankfully, a special type of such a machine, a Universal Turing Machine (UTM), has an instruction set that is advanced enough to implement all specific Turing machines and to execute any algorithm without the need to alter the transition table. This über-machine is neither particularly abstract nor complex. Its existence is guaranteed because a specific Turing machine can be devised to perform any finite algorithm (according to the aforementioned Church-Turing thesis).

…

It is perfectly feasible to assemble such a device with just hundreds of logic gates, even though today’s designs may use many more. As you can see, the notion of building a computer from scratch is not so absurd—even a wooden one. Advancement through Simplicity Coming up with such an unimpressive set of instructions is, of course, not going to make the device fast or easy to program. Universal Turing Machines can do just about everything (in many cases, by virtue of their simplicity), but they are painfully slow and difficult to program, to a degree that even implementing machine-assisted translation from more human-readable languages to machine code is difficult, at least without driving the programmer clinically insane.

…

[50] “Evaluation of VIA C3 Nehemiah Random Number Generator,” Cryptography Research Inc. (2003). [51] Michael A. Hogye, Christopher T. Hughes, Joshua M. Sarfaty, Joseph D. Wolf, “Analysis of Feasibility of Keystroke Timing Attacks Over SSH Con-nections,” CS588 Research Project, School of Engineering and Applied Science, University of Virginia (2001). [52] Yurii Rogozhin, “A Universal Turing Machine with 22 States and 2 Symbols,” Romanian Journal of Information Science and Technology 1 no. 3 (1998). [53] Milena Milenkovic, Aleksandar Milenkovic, Jeffrey Kulick, “Demystifying Intel Branch Predictors,” Electrical and Computer Engineering Department, University of Alabama in Huntsville (2002)

A Thousand Brains: A New Theory of Intelligence
by Jeff Hawkins
Published 15 Nov 2021

There were computers designed for specific tasks. There were analog computers, and computers that could only be repurposed by changing the wiring. There were computers that worked with decimal instead of binary numbers. Today, almost all computers are the universal form that Turing envisioned. We even refer to them as “universal Turing machines.” With the right software, today’s computers can be applied to almost any task. Market forces decided that universal, general-purpose computers were the way to go. This is despite the fact that, even today, any particular task can be performed faster or with less power using a custom solution, such as a special chip.

…

Today’s computers come in many shapes and sizes, from the microcomputer in a toaster to room-size computers used for weather simulation. Despite their differences in size and speed, all these computers work on the same principles laid out by Turing and others many years ago. They are all instances of universal Turing machines. Similarly, intelligent machines of the future will come in many shapes and sizes, but almost all of them will work on a common set of principles. Most AI will be universal learning machines, similar to the brain. (Mathematicians have proven that there are some problems that cannot be solved, even in principle.

…

No one can know how intelligent machines will be used fifty or sixty years from now. When Is Something Intelligent? When should we consider a machine intelligent? Is there a set of criteria we can use? This is analogous to asking, When is a machine a general-purpose computer? To qualify as a general-purpose computer—that is, a universal Turing machine—a machine needs certain components, such as memory, a CPU, and software. You can’t detect these ingredients from the outside. For example, I can’t tell if my toaster oven has a general-purpose computer inside or a custom chip. The more features my toaster oven has, the more likely it contains a general-purpose computer, but the only sure way to tell is by looking inside and seeing how it works.

The Master Algorithm: How the Quest for the Ultimate Learning Machine Will Remake Our World
by Pedro Domingos
Published 21 Sep 2015

They would say that each machine can only do one thing: sewing machines don’t type, and typewriters don’t sew. Then in 1936 Alan Turing imagined a curious contraption with a tape and a head that read and wrote symbols on it, now known as a Turing machine. Every conceivable problem that can be solved by logical deduction can be solved by a Turing machine. Furthermore, a so-called universal Turing machine can simulate any other by reading its specification from the tape—in other words, it can be programmed to do anything. The Master Algorithm is for induction, the process of learning, what the Turing machine is for deduction. It can learn to simulate any other algorithm by reading examples of its input-output behavior.

…

“All humans are mortal” is much more succinct than seven billion statements of mortality, one for each human. Memorization gives us none of these things. Another candidate Master Algorithm is the microprocessor. After all, the one in your computer can be viewed as a single algorithm whose job is to execute other algorithms, like a universal Turing machine; and it can run any imaginable algorithm, up to its limits of memory and speed. In effect, to a microprocessor an algorithm is just another kind of data. The problem here is that, by itself, the microprocessor doesn’t know how to do anything; it just sits there idle all day. Where do the algorithms it runs come from?

…

The same is true of a logician carrying out deductions. According to this hypothesis, intelligence is independent of the substrate; it doesn’t matter if the symbol manipulations are done by writing on a blackboard, switching transistors on and off, firing neurons, or playing with Tinkertoys. If you have a setup with the power of a universal Turing machine, you can do anything. Software can be cleanly separated from hardware, and if your concern is figuring out how machines can learn, you (thankfully) don’t need to worry about the latter beyond buying a PC or cycles on Amazon’s cloud. Symbolist machine learners share this belief in the power of symbol manipulation with many other computer scientists, psychologists, and philosophers.

What Algorithms Want: Imagination in the Age of Computing
by Ed Finn
Published 10 Mar 2017

But of course models always compress or shorthand reality. If the anchor point for the pragmatist’s definition of the algorithm is its indefinable flexibility based on tacit understanding about what counts as a problem and a solution, the anchor point here is the notion of abstraction. The argument for computationalism begins with the Universal Turing Machine, mathematician Alan Turing’s breathtaking vision of a computer that can complete any finite calculation simply by reading and writing to an infinite tape marked with 1s and 0s, moving the tape forward or backward based on the current state of the machine. Using just this simple mechanism one could emulate any kind of computer, from a scientific calculator finding the area under a curve to a Nintendo moving Mario across a television screen.

…

Using just this simple mechanism one could emulate any kind of computer, from a scientific calculator finding the area under a curve to a Nintendo moving Mario across a television screen. In other words, this establishes a computational “ceiling” where any Turing computer can emulate any other: the instructions may proceed more slowly or quickly, but are mathematically equivalent. The Universal Turing Machine is a thought experiment that determines the bounds of what is computable: Turing and his fellow mathematician Alonzo Church were both struggling with the boundary problems of mathematics. In one framing, posed by mathematician David Hilbert, known as the Entscheidungsproblem, the question is whether it’s possible to predict when or if a particular program will halt, ending its calculations with or without an answer.

…

Their responses to Hilbert, now called the Church–Turing thesis, define algorithms for theorists in a way that is widely accepted but ultimately unprovable: a calculation with natural numbers, or what most of us know as whole numbers, is “effectively computable” (that is, given enough time and pencils, a human could do it) only if the Universal Turing Machine can do it. The thesis uses this informal definition to unite three different rigorous mathematical theses about computation (Turing machines, Church’s lambda calculus, and mathematician Kurt Gödel’s concept of recursive functions), translating their specific mathematical claims into a more general boundary statement about the limits of computational abstraction.

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

By 1939, von Neumann must have read Turing’s work on automata and computing machines,8 for he used his approach to study how cybernetic systems could self-replicate. Turing had shown how a machine could code any kind of information – a concept he termed a ‘Universal Machine’. Von Neumann realised that, in essence, this meant the Universal Turing Machine could also code itself. Indeed, modern computers, which are Universal Turing Machines, have exactly this ability. All software stored in your computer can be copied to another computer, by your computer. In fact, copying is what takes place whenever you perform any transaction using a computer. When you ‘send’ an email, for example, nothing actually moves from one place to another: an exact copy of your email is reproduced in the computer of the person you want to communicate with.

…

When you ‘send’ an email, for example, nothing actually moves from one place to another: an exact copy of your email is reproduced in the computer of the person you want to communicate with. Von Neumann was fascinated with this self-copying property of the Universal Turing Machine. In true cybernetic fashion, he set off to formulate a general theory of self-reproduction that would include living organisms as well as machines. He embarked on this quest with a series of lectures in 1948 – four years before Watson, Crick and Franklin discovered the molecular structure of DNA – and thus answered the puzzle of self-replication in living systems.

…

It creates a one-to-one correspondence between two classes of mathematical objects, say between natural numbers and logical signs or operators.9 Thus, the smart mathematician solves an easier problem rather than an impossible one, and becomes famous forevermore. Using logical substitution, von Neumann substituted bits of information (for example, sets of positions on the infinite tape of a Universal Turing Machine, or a ‘program’ as we would call it today) with whole Turing machines, in order to prove his theorem for self-replicating automata. And here’s the deep insight of this substitution: it confirms, in a most profound way, that artificial life can reproduce in exactly the same way as biological life.

On Intelligence
by Jeff Hawkins and Sandra Blakeslee
Published 1 Jan 2004

The box, which today we call a central processing unit (CPU), follows a set of fixed rules for reading and editing the information on the tape. Turing proved, mathematically, that if you choose the right set of rules for the CPU and give it an indefinitely long tape to work with, it can perform any definable set of operations in the universe. It would be one of many equivalent machines now called Universal Turing Machines. Whether the problem is to compute square roots, calculate ballistic trajectories, play games, edit pictures, or reconcile bank transactions, it is all 1's and 0's underneath, and any Turing Machine can be programmed to handle it. Information processing is information processing is information processing.

…

Sure, people do all this with brains and not with the kinds of computers we build, but Turing has shown that it doesn't matter how you implement or manipulate the symbols. You can do it with an assembly of cogs and gears, with a system of electronic switches, or with the brain's network of neurons— whatever, as long as your medium can realize the functional equivalent of a Universal Turing Machine." This assumption was bolstered by an influential scientific paper published in 1943 by the neurophysiologist Warren McCulloch and the mathematician Walter Pitts. They described how neurons could perform digital functions— that is, how nerve cells could conceivably replicate the formal logic at the heart of computers.

…

Many philosophers and cognitive psychologists are sympathetic to this view. They love the metaphor of the mind being like software that's run by the brain, the organic analog of computer hardware. In computers, the hardware level and the software level are distinct from each other. The same software program can be made to run on any Universal Turing Machine. You can run WordPerfect on a PC, a Macintosh, or a Cray supercomputer, for example, even though all three systems have different hardware configurations. And the hardware has nothing of importance to teach you if you're trying to learn WordPerfect. By analogy, the thinking goes, the brain has nothing to teach us about the mind.

The Code Book: The Science of Secrecy From Ancient Egypt to Quantum Cryptography
by Simon Singh
Published 1 Jan 1999

The alterations would be made by inserting carefully selected tapes, which transformed the single flexible machine into a dividing machine, a multiplying machine, or any other type of machine. Turing called this hypothetical device a universal Turing machine because it would be capable of answering any question that could logically be answered. Unfortunately, it turned out that it is not always logically possible to answer a question about the undecidability of another question, and so even the universal Turing machine was unable to identify every undecidable question. Mathematicians who read Turing’s paper were disappointed that Gödel’s monster had not been subdued but, as a consolation prize, Turing had given them the blueprint for the modern programmable computer.

…

Mathematicians who read Turing’s paper were disappointed that Gödel’s monster had not been subdued but, as a consolation prize, Turing had given them the blueprint for the modern programmable computer. Turing knew of Babbage’s work, and the universal Turing machine can be seen as a reincarnation of Difference Engine No. 2. In fact, Turing had gone much further, and provided computing with a solid theoretical basis, imbuing the computer with a hitherto unimaginable potential. It was still the 1930s though, and the technology did not exist to turn the universal Turing machine into a reality. However, Turing was not at all dismayed that his theories were ahead of what was technically feasible. He merely wanted recognition from within the mathematical community, who indeed applauded his paper as one of the most important breakthroughs of the century.

When Einstein Walked With Gödel: Excursions to the Edge of Thought
by Jim Holt
Published 14 May 2018

All I’m after is just a mediocre brain, something like the president of the American Telephone and Telegraph Company.” Turing’s early work had raised a fascinating possibility: perhaps the human brain is something like a universal Turing machine. Of course, the brain looks more like cold porridge than like a machine. But Turing suspected that what made the brain capable of thought was its logical structure, not its physical embodiment. Building a universal Turing machine might thus be the way to erase the line between the mechanical and the intelligent. In 1945, Turing wrote up a plan for building a computer that contained everything from the abstract structure down to the circuit diagrams and a cost estimate of 11,200 pounds.

…

Turing was able to prove that no computing machine of the kind he envisaged could solve the decision problem. Reasoning could not be reduced to computation after all. But the death of Leibniz’s dream turned out to be the birth of the computer age. The boldest idea to emerge from Turing’s analysis was that of a universal Turing machine: one that, when furnished with the number describing the mechanism of any particular Turing machine, would perfectly mimic its behavior. In effect, the “hardware” of a special-purpose computer could be translated into “software” and then entered like data into the universal machine, where it would be run as a program.

…

The code number of one special-purpose Turing machine could even be fed as an input onto the tape of another Turing machine. This led Turing to the idea of a universal machine: one that, if fed the code number of any special-purpose Turing machine, would function as if it actually were that special-purpose machine. For instance, if a universal Turing machine were fed the code number of the Turing machine that performed addition, the universal machine would temporarily turn into an adding machine. That is exactly what happens when your laptop, which is a physical embodiment of Turing’s universal machine, runs a word-processing program or when your smartphone runs an app.

Possible Minds: Twenty-Five Ways of Looking at AI
by John Brockman
Published 19 Feb 2019

In these machines, a linear tape of symbols from a finite alphabet encodes the input for a computational problem and also provides the working space for the computation. A different machine was required for each separate computational problem; later work by others would show that in one particular machine, now known as a Universal Turing Machine, an arbitrary set of computing instructions could be encoded on that same tape. In the 1940s, von Neumann developed an abstract self-reproducing machine called a cellular automaton. In this case it occupied a finite subset of an infinite two-dimensional array of squares each containing a single symbol from a finite alphabet of twenty-nine distinct symbols—the rest of the infinite array starts out blank.

…

The vast majority of computer chips built in the era of Moore’s Law are based on the von Neumann architecture, including those powering our data centers, our laptops, and our smartphones. Von Neumann’s digital-computer architecture is conceptually the same generalization—from early digital computers constructed with electromagnetic relays at both Harvard University and Bletchley Park—that occurs in going from a special-purpose Turing Machine to a Universal Turing Machine. Furthermore, his self-replicating automata share a fundamental similarity with both the construction of a Turing Machine and the mechanism of DNA-based reproducing biological cells. There is to this day scholarly debate over whether von Neumann saw the cross connections between these three pieces of work, Turing’s and his two.

…

See singularity Tegmark, Max, 76–87 AI safety research, 81 Asilomar AI Principles, 2017, 81, 84 background and overview of work of, 76–77 competence of superintelligent AGI, 85 consciousness as cosmic awakening, 78–79 general expectation AGI achievable within next century, 79 goal alignment for AGI, 85–86 goals for a future society that includes AGI, 84–86 outlook, 86–87 rush to make humans obsolescent, reasons behind, 82–84 safety engineering, 86 societal impact of AI, debate over, 79–82 Terminator, The (film), 242 three laws of artificial intelligence, 39–40 Three Laws of Robotics, Asimov’s, 250 threshold theorem, 164 too-soon-to-worry argument against AI risk, 26–27, 81 Toulmin, Stephen, 18–19 transhumans, rights of, 252–53 Treister, Suzanne, 214–15 Trolley Problem, 244 trust networks, building, 200–201 Tsai, Wen Ying, 258, 260–61 Turing, Alan, 5, 25, 35, 43, 60, 103, 168, 180 AI-risk message, 93 Turing Machine, 57, 271 Turing Test, 5, 46–47, 276–77 Tversky, Amos, 130–31, 250 2001: A Space Odyssey (film), 183 Tyka, Mike, 212 Understanding Media (McLuhan), 208 understanding of computer results, loss of, 189 universal basic income, 188 Universal Turing Machine, 57 unsupervised learning, 225 value alignment (putting right purpose into machines) Dragan on, 137–38, 141–42 Griffiths on, 128–33 Pinker on, 110–11 Tegmark on, 85–86 Wiener on, 23–24 Versu, 217 Veruggio, Gianmarco, 243 visualization programs, 211–13 von Foerster, Heinz, xxi, 209–10, 215 Vonnegut, Kurt, 250 von Neumann, John, xx, 8, 35, 60, 103, 168, 271 digital computer architecture of, 58 second law of AI and, 39 self-replicating cellular automaton, development of, 57–58 use of symbols for computing, 164–65 Watson, 49, 246 Watson, James, 58 Watson, John, 225 Watt, James, 3, 257 Watts, Alan, xxi Weaver, Warren, xviii, 102–3, 155 Weizenbaum, Joe, 45, 48–50, 105, 248 Wexler, Rebecca, 238 Whitehead, Alfred North, 275 Whole Earth Catalog, xvii “Why the Future Doesn’t Need Us” (Joy), 92 Wiener, Norbert, xvi, xviii–xx, xxv, xxvi, 35, 90, 96, 103, 112, 127, 163, 168, 256 on automation, in manufacturing, 4, 154 on broader applications of cybernetics, 4 Brooks on, 56–57, 59–60 control via feedback, 3 deep-learning and, 9 Dennett on, 43–45 failure to predict computer revolution, 4–5 on feedback loops, 5–6, 103, 153–54 Hillis on, 178–80 on information, 5–6, 153–59, 179 Kaiser on Wiener’s definition of information, 153–59 Lloyd on, 3–7, 9, 11–12 Pinker on, 103–5, 112 on power of ideas, 112 predictions/warnings of, xviii–xix, xxvi, 4–5, 11–12, 22–23, 35, 44–45, 93, 104, 172 Russell on, 22–23 on social risk, 97 society, cybernetics impact on, 103–4 what Wiener got wrong, 6–7 Wilczek, Frank, 64–75 astonishing corollary (natural intelligence as special case of AI), 67–70 astonishing hypothesis of Crick, 66–67 background and overview of work of, 64–65 consciousness, creativity and evil as possible features of AI, 66–68 emergence, 68–69 human brain’s advantage over AI, 72–74 information-processing technology capacities that exceed human capabilities, 70–72 intelligence, future of, 70–75 Wilkins, John, 275 wireheading problem, 29–30 With a Rhythmic Instinction to Be Able to Travel Beyond Existing Forces of Life (Parreno), 263–64 Wolfram, Stephen, 266–84 on AI takeover scenario, 277–78 background and overview of work of, 266–67 computational knowledge system, creating, 271–77 computational thinking, teaching, 278–79 early approaches to AI, 270–71 on future where coding ability is ubiquitous, 279–81 goals and purposes, of humans, 268–70 image identification system, 273–74 on knowledge-based programming, 278–81 purposefulness, identifying, 281–84 Young, J.

Infinity in the Palm of Your Hand: Fifty Wonders That Reveal an Extraordinary Universe
by Marcus Chown
Published 22 Apr 2019

The crucial thing is that Turing’s machine can be fed a description, encoded in binary, of any other machine and will then simulate that machine. Because of this unprecedented ability, Turing called it a Universal Machine. Today, it is referred to as a Universal Turing Machine. Clearly, it is unrecognizable as a computer. But that is exactly what it is. A Universal Turing Machine is the simplest computer imaginable: the irreducible atom of computing. Ironically, Turing devised his machine-of-the-mind to show not what a computer can do but what it cannot do. As a mathematician, it was the ultimate limit of computers that interested him.

The Secret Life of Bletchley Park: The WWII Codebreaking Centre and the Men and Women Who Worked There
by Sinclair McKay
Published 24 May 2010

Even in the years that followed the war, with all the technological progress that had been made, Turing’s devices tended to fulfil the stereotype of the mad scientist’s invention: a labyrinth of wires trailing everywhere, held together with sticking plaster. Prior to his premature death in 1954, his home in Manchester was filled with extraordinary and sometimes pungent chemical experiments. Turing had fixed upon the idea of a ‘Universal Turing Machine’ in the 1930s; the inspiration had been provided by a mathematical problem posed in Cambridge, concerning the provability of any given mathematical assertion. Turing had the idea of developing a machine that could carry out this task. When first trying to envisage the form of such a machine, Turing thought of typewriters, how they were built to carry out a certain sort of function.

…

According to his biographer Andrew Hodges, he had in his head an idea of a super-typewriter: a machine that could identify symbols; that could write, but could also erase. A machine that could be configured in many ways to carry out many tasks, and yet would be automatic, requiring little or no intervention from a human operator. His argument was that any calculation that a human could perform, a machine could perform as well. The bombes were not Universal Turing Machines. Far from it. Nor were they an extension of the Polish ‘bomba’ machines, from which their name was taken. The British bombe was quite a different thing. In one sense, it was a philosophical response to the nature of Enigma. Despite the daunting number of combinations thrown up by Enigma, it none the less worked via a mechanical process.

…

However, with the lack of enthusiasm for the Delilah system – it seems the Post Office was working upon its own commercial sound encryption techniques – Turing wanted to return to the question that had been haunting him since the 1930s, that of constructing a thinking machine – an electronic brain. A Universal Turing Machine. A machine of such complexity that it could not only speedily handle any kind of mathematical calculation, but also store a memory of the process within itself. In the 1930s, while the theory had been revolutionary, it was difficult to see how the current valve technology could keep pace with such a thing.

Darwin Among the Machines
by George Dyson
Published 28 Mar 2012

.: 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.

…

Barricelli, “On the Origin and Evolution of the Genetic Code: 2. Origin of the Genetic Code as a Primordial Collector Language; The Pairing-Release Hypothesis,” BioSystems 11 (1979): 19, 21. 54.Martin Davis, “Influences of Mathematical Logic on Computer Science,” in Rolf Herken, ed., The Universal Turing Machine: A Half-century Survey (Oxford: Oxford University Press, 1988), 315. 55.Alan Turing, “Computing Machinery and Intelligence,” Mind 59 (October 1950): 456. CHAPTER 8 1.W. Daniel Hillis, “New Computer Architectures and Their Relationship to Physics, or Why Computer Science Is No Good,” International Journal of Theoretical Physics 21, nos. 3–4 (April 1982): 257. 2.Aeschylus, Agamemnon, lines 280–316, trans, and ed.

…

–1003), 212 size, in biology and technology, 15, 174, 208. see also scale Slutz, Ralph, 79, 100, 101 Small, William, 21 Smee, Alfred (1818–1877), 45–48 Smee, William, 45 Smith, Adam (1723–1790), 168 Smithsonian Institution, 142 society. see also collective intelligence; organisms, collective and human intelligence, 71 machines as, 31 modeling of, 182–184 as self-organizing system, 2–3, 168 Society of Friends (Quakers), 87, 193, 194, 196. see also Friends’ Ambulance Unit Society of Mind (Minsky), 72, 168 Society for Psychical Research, 201 software. see also code and coding; languages; programming; symbiogenesis in biology, 29, 32, 112, 123, 160 object-oriented, 123, 128, 185, 189 origins and evolution of, 9–10, 57, 70, 83–84, 90, 112, 124, 160, 180, 185, 188–89 proliferation of, 10–13, 98, 121–24, 126–29, 170, 224–25 and universal Turing machine, 9–10, 57, 90 songs and apes, metaphor (Hillis), 222–25, 227 soul, nature of, and machines, x, 2, 9, 50–51, 53, 136, 172 Southwell, Sir Robert, 160, 171 species. see also Origin of Species collective intelligence of, 18, 27, 115–16, 186–88, 217–18 as composite organisms, 27, 115, 172, 186, 191, 217–18 Erasmus Darwin, on origin of, 18–19, 21 origins and extinction of, in technology, 31, 122 Speculations Concerning the First Ultraintelligent Machine (Good), 72, 170–71 Sperry-Rand, 69, 91 spreadsheets, 11, 86, 214 Sputnik I and II, 146 Stapledon, William Olaf (1886–1950), 35–36, 193–201, 203–204, 209–210, 215, 217–18, 220 and Agnes Miller, 193, 198 on collective intelligence and composite mind, 193, 199–201, 203–204, 209–210, 217–18 on God, mind, and universe, 35–36, 197, 199, 209–210, 215, 217–18 and Leo Myers, 201 and Lewis Richardson, 195–98 on mind and electrons, 198 on radiotelepathy, 193, 199–201, 203–204 and World War I, 193-96, 220 Star Maker (Stapledon), 199, 209–210 Statistics of Deadly Quarrels (Richardson), 87 steam engines, 22, 31, 33, 37, 119, 134 stored-program computers. see also programming; Turing machine and Babbage, 41–42 and Colossus, 67 and delay-line storage, 133 and EDVAC, 90 and ENIAC, 81 at Manchester, 67, 104 and Turing, 68–69, 88 Strategic Missiles Evaluation Committee, 144 Strauss, Lewis, 91 subroutines (computational), 18, 68, 121, 123 miracles as, 41 protein molecules as, 118 Sunbeam Lamp Company, 198 Sussex, University of, 215 Swade, Doron, 41 switching, 8, 9, 89, 109. see also packet switching and Boolean algebra, 44 and coding, 8, 57, 89 and telegraphy, 142 symbiogenesis, 111–25, 128–30, 190 as adjunct to Darwinism, 112, 190 and complexity, 112, 117, 190 and evolution of evolution, 128, 130 and origins of life, 111–13, 117, 129 and parallel processing of genetic code, 115 and proliferation of software, 121–24 symbioorganisms.

Wireless
by Charles Stross
Published 7 Jul 2009

Okay, you’re a research cell working on some ultimate black problem, and you’re using the Farm because it’s about the most secure environment anyone can imagine, and you’re emulating some kind of minimal universal Turing machine using the chessboard. Say, a 2,5 UTM—two registers, five operations—you can encode the registers positionally in the chessboard’s two dimensions, and use the moves to simulate any other universal Turing machine, or a transform in an eleven-dimensional manifold like AXIOM REFUGE—” Godel’s waving frantically. “She’s coming! She’s coming!” I hear doors clanging in the distance. Shit. “But why are you so afraid of the Nurses?”

…

“Or even”—Mandelbrot takes a deep breath—“a brains trust!” “A-ha! AhaHAHAHA! Hic.” Godel covers his mouth, face reddening. “What do you think the rules are?” Cantor repeats, and they’re still staring at me, as if, as if . . . “Why does it matter?” I ask. I’m thinking that it could be anything; a 2,5 universal Turing machine encoded in the moves of the pawns—that would fit—whatever it is, it’s symbolic communication, very abstract, very pared-back, and if they’re doing it in this ultimately firewalled environment and expecting to report directly to the Board, it’s got to be way above my security clearance— “Because you’re acting cagey, lad.

When Things Start to Think
by Neil A. Gershenfeld
Published 15 Feb 1999

In 1936 Turing proved the latter. To do this, he had to bring some kind of order to the notion of a smart machine. Since he couldn't anticipate all the kinds of machines people might build, he had to find a general way to describe their capabilities. He did this by introducing the concept of a Universal Turing Machine. This was a simple machine that had a tape (possibly infinitely long), and a head that could move along it, reading and writing marks based on what was already on the tape. Turing showed that this machine could perform any computation that could be done by any other machine, by preparing it first with a program giving the rules for interpreting the instructions for the other machine.

…

V., 39-40 Reeves, Byron, 54 Reformation, 95-97, 103 religion, 131, 133 research and development, 169-84 applied research, 172, 177, 178, 185 basic research, 172, 174, 177, 178, 185 government role, 171-74 new way to organize inquiry, 180-84 organization in the U.S., 171-74, 180 presumed pathway of, 177 Resnick, Mitchel, 68-70, 146-47, 206 responsibilities in using new technologies, 104 reusable paper, 16-17 Reynolds, Matt, 196, 197 rights: Bill of Things' Rights, 104 Bill of Things Users' Rights, 102 Rittmueller, Phil, 170, 180 Roosevelt, Franklin D., 171, 172 Santa Fe Institute, 118 Satellites, communications, 99-100 Science-The Endless Frontier, 172 search engines, 134 security versus privacy, 57 224 + semiconductor industry, 72 Sensormatic, 153 Shannon,C~ud~5, 128,176,188-90 shoe, computer in a, 50, 52, 102-3, 179 shoplifting tags, 153 Shor, Peter, 158, 159 Silicon Graphics, 140 Simon, Dan, 158 skepticism about technological advances, 122 Small, David, 22-23 Smalltalk, 138 smart cards, 81, 152 smart money, 77-91 cryptography and, 80-81 as digital information, 80 distinction between atom-dollars and bit-dollars, 83-85 freeing money from legacy as tangible asset, 79, 91 global currency market, 83 linking algorithms with money, 86-88 paying-as-you-go, 82 precedent for, 80 standards for, 88-91 smart name badges, 206 Smith, Joshua, 144, 170-71 sociology of science, 119 software, 7, 53, 156 belief in magic bullets, 121 CAD, 73 for children, 138 remarkable descriptions of, 108-9 upgrades, 98, 108-9 Soviet Union, 121-22 speech recognition, 140 spirit chair, 169-70, 179, 193, 202 spread-spectrum coding techniques, 165, 166 standards: computer, 88-90, 126 smart money, 88-91 Stanford Research Institute, 139 INDEX Stanford University, 54 Starner, Thad, 47, 57-58 Steane, Andy, 159 Steelcase, 202, 203, 204 Stradivarius, designing digital instrument to compete with, 32-33,39-42 Strickon, Joshua, 55 Sumitomo, 77 supercomputers, 151, 177, 199 surveillance, 57 Swatch Access watches, 152 Szilard, Leo, 176 technology: Bill of Things' Rights, 104 Bill of Things Users' Rights, 102 daily use of, 58 freedom of technological expression, 103 imposing on our lives, 95, 100-2 invisible and unobtrusive, 44, 200, 211 jargon, 107-22 mature, 10 musical instruments incorporating available, 38 wisdom in old technologies, 19, 24 telemarketing, 95, 101 telephones, 175 access to phone numbers, 100 invasion in our lives, 95, 101 satellite, 99-100 smart cards, 81 widespread dissemination of, 99 television, 10, 99, 202 high-definition, 6 Termen, Lev, 144 Tetzel, Johann, 96 "There's Plenty of Room at the Bottom," 161 thermodynamics, 175, 176 Things That Think, 202-7 privacy and, 207-10 stratification of society and, 210-11 INDEX 3D graphics interface, 141-42 3D printer, 64-65, 70-71 3001: The Final Odyssey (Clarke), 51 Toffoli, Tomaso, 132 transistors: invention of the, 175 study of, 179 Turing, Alan, 127-28, 131, 135, 166 Turing test, 128, 131, 133-34, 135 281, 210-11 Underkoffler, John, 145-46 U.S. Defense Department Advanced Research Projects Agency (DARPA), 79-80, 129 U.S. Department of Energy, 178, 179 U.S. Steel, 78 Universal Turing Machine, 127 van Kempelen, Wolfgang van, 123-24 VCRs, 8 videoconferencing, 59, 207 for educational purposes, 193 videotapes, format of, 6 virtual reality, 49, 109, 110, 112 von Neumann, John, 5, 132 VPL, 49 Watson, Thomas J., 63 wealth, distribution of, 78 wearable computers, 45-61 affective states, perception of, 53-54 Data Glove, 49 disabled and, 58 fashion and, 55-56 + 225 forces behind transition to, 4 7 industry and, 47-48 loss of autonomy and, 57-58 loss of community, fear of, 58-60 most expensive, 54-55 Personal Area Network (PAN), 50-52 privacy concerns, 56-57 in shoes, 50, 52, 102-3, 179 Weigend, Andreas, 118 Widener library, 20, 21 Wiesner, Jerome, 185-86 William and Mary, 98 Windows-and-mice interface, 106, 139, 147 Winston Jewelers, 54-55 wiretaps, 208 workstations, 151 World Bank, 78 World Wide Web, see Internet and World Wide Web wristwatches, new capabilities of, 152 Xerox Palo Alto Research Center, 137, 138-39 Yahoo, 78 Yo-Yo Ma, 27-28, 33-35, 43-44, 109-10, 187 Zimmerman, Thomas, 48-50 

In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation
by William J. Cook
Published 1 Jan 2011

The working assumption that we can equate algorithms and Turing machines is known as the Church-Turing Thesis.3 This thesis is widely Complexity accepted and it gives the formal model of an algorithm that is used to make precise P vs. N P and other complexity questions. Perhaps, one day, exotic computing capabilities will come along to cause us to consider an expanded definition of an algorithm, but for over seventy years Turing has served up just what the research community has needed. Universal Turing Machines There is a fundamental difference between a modern telephone, such as the iPhone, and, say, a pair of shoes. Shoes are designed for the single duty of protecting your feet, whereas the hundreds of thousands of applications available for the iPhone allow it to take on tasks that were not imagined when the hardware was designed.

…

A Turing machine is a great model for describing what we mean by an algorithm, but a Turing machine is designed for a single task, such as adding two numbers. In this sense, Turing machines are closer to a pair of shoes than to an iPhone. A crucial point made by Turing, however, is that one can design a Universal Turing machine capable of simulating every Turing machine. It is possible to invent a single machine which can be used to compute any computable sequence. If this machine U is supplied with a tape on the beginning of which is written the S.D of some computing machine M, then U will compute the same sequence as M.

Darwin's Dangerous Idea: Evolution and the Meanings of Life
by Daniel C. Dennett
Published 15 Jan 1995

Of all the possible moves available, he saw that there was a good reason for this move, so this is what would be discovered. We can get a sense of the magnitude of the leap that such an inference takes by comparing it with a parallel leap that we can make in the Game of Life. Recall that one of the possible denizens of the Life world is a Universal Turing machine composed of trillions of pixels. Since a Universal Turing machine can compute any computable function, it can play chess — simply by mimicking the program of any chess-playing computer you like. Suppose, then, that such an entity occupies the Life plane, playing chess against itself, in the fashion of Samuel's computer playing checkers against itself.

…

For instance, one can set oneself the task of designing some interesting supersystem out of the "parts" that the design level makes available. This is just what Conway and his students set out to do, and they succeeded majestically. They designed, and proved the viability of the design of, a self-reproducing entity composed entirely of Life cells that was also (for good measure) a Universal Turing machine — it was a two-dimensional computer that in principle can compute any computable function! What on Earth inspired Conway and his students to create first this world and then this amazing denizen of that world? They were trying to answer at a very abstract level one of the central questions we have been considering in this chapter: what is the minimal complexity required for a self-reproducing thing?

…

It was von Neumann who had taken Alan Turing's abstract conception of a mechanical computer (now called a "Turing machine") and engineered it into the specification for a general-purpose stored-program serial-processing computer (now called a "von Neumann machine"); in his brilliant explorations of the spatial and structural requirements for such a computer, he had realized — and proved — that a Universal Turing machine (a Turing machine that can compute any computable function at all) could in principle be "built" in a two-dimensional world.6 Conway and his students also set out to confirm this with their own exercise in two-dimensional engineering.7 It was far from easy, but they showed how they could "build" a working computer out of simpler Life forms.

Mastering Ethereum: Building Smart Contracts and DApps
by Andreas M. Antonopoulos and Gavin Wood Ph. D.
Published 23 Dec 2018

, Turing Completeness and Gas implications of, Implications of Turing Completeness Turing, Alan, Ethereum and Turing Completeness tx object, Transaction context tx.origin authentication security threatpreventative techniques, Preventative Techniques vulnerability, The Vulnerability typecasting, Variable Typecasting typographical conventions, Conventions Used in This Book U unchecked CALL return value security threat, Unchecked CALL Return Values-Real-World Example: Etherpot and King of the Etherpreventative techniques, Preventative Techniques real-world example: Etherpot and King of the Ether, Real-World Example: Etherpot and King of the Ether vulnerability, The Vulnerability underflow, Arithmetic Over/Underflows-Real-World Examples: PoWHC and Batch Transfer Overflow (CVE-2018–10299), The Vulnerability unexpected etherpreventative techniques, Preventative Techniques security threat from, Unexpected Ether-Further Examples vulnerability, The Vulnerability-The Vulnerability uninitialized storage pointers security threat, Uninitialized Storage Pointers-Real-World Examples: OpenAddressLottery and CryptoRoulette Honey Potspreventative techniques, Preventative Techniques real-world examples: OpenAddressLottery and CryptoRoulette honey pots, Real-World Examples: OpenAddressLottery and CryptoRoulette Honey Pots vulnerability, The Vulnerability-The Vulnerability Universal Turing machine (UTM), Ethereum and Turing Completeness user interface, as DApp frontend, Frontend (Web User Interface) utilities, EthereumJS helpeth: A Command-Line Utilitydapp.tools, dapp.tools EthereumJS helpeth, EthereumJS helpeth: A Command-Line Utility SputnikVM, SputnikVM utility currency, ether as, Compared to Bitcoin utility tokensdefined, Using Tokens: Utility or Equity equity tokens disguised as, It’s a Duck! issues to consider when using, Utility Tokens: Who Needs Them?-Utility Tokens: Who Needs Them? UTM (Universal Turing machine), Ethereum and Turing Completeness V value field, Transaction Value and Data-Transmitting Value to EOAs and Contracts variable declarations, ordering of, Function and Variable Ordering version pragma, Selecting a Solidity Compiler and Language Version Vickrey auctions, Vickrey auctions view (function keyword), Functions visibility specifiers, Default Visibilities-Real-World Example: Parity Multisig Wallet (First Hack) vulnerabilities, Vulnerabilities and Vyper(see also security; specific attacks/vulnerabilities) Vyper, Introduction to Ethereum High-Level Languages, Smart Contracts and Vyper-Conclusionsclass inheritance, Class Inheritance compilation, Compilation contract vulnerabilities and, Vulnerabilities and Vyper decorators, Decorators defined, Quick Glossary function ordering, Function and Variable Ordering function overloading, Function Overloading modifiers, Modifiers overflow protection, Protecting Against Overflow Errors at the Compiler Level preconditions/postconditions, Preconditions and Postconditions reading/writing data, Reading and Writing Data Solidity compared to, Comparison to Solidity-Preconditions and Postconditions variable ordering, Function and Variable Ordering variable typecasting, Variable Typecasting W wallets, Wallets-Conclusionsbest practices for, Wallet Best Practices-Navigating the HD wallet tree structure browser wallets, Browser Wallets choosing, Choosing an Ethereum Wallet cold-storage wallets, Extended public and private keys creating HD wallets from root seed, Creating an HD Wallet from the Seed defined, Quick Glossary, Choosing an Ethereum Wallet, Wallets deterministic, Wallet Technology Overview, Deterministic (Seeded) Wallets duress wallet, Optional passphrase in BIP-39 Emerald Wallet, Choosing an Ethereum Wallet HD (see hierarchical deterministic wallets) Jaxx, Choosing an Ethereum Wallet, Mobile (Smartphone) Wallets, Jaxx MetaMask (see MetaMask) Mist, Quick Glossary, Mist mnemonic codes (BIP-39), Seeds and Mnemonic Codes (BIP-39), Mnemonic Code Words (BIP-39)-Working with mnemonic codes mobile, Mobile (Smartphone) Wallets MyCrypto, MyCrypto MyEtherWallet, Choosing an Ethereum Wallet, MyEtherWallet (MEW), MyCrypto nondeterministic, Wallet Technology Overview-Nondeterministic (Random) Wallets Parity Multisig Wallet hacks, Real-World Example: Parity Multisig Wallet (Second Hack)-Real-World Example: Parity Multisig Wallet (Second Hack), Real-World Example: Parity Multisig Wallet (First Hack) remote clients compared to, Should I Run a Full Node?

…

Specifically, he proved that the halting problem (whether it is possible, given an arbitrary program and its input, to determine whether the program will eventually stop running) is not solvable. Alan Turing further defined a system to be Turing complete if it can be used to simulate any Turing machine. Such a system is called a Universal Turing machine (UTM). Ethereum’s ability to execute a stored program, in a state machine called the Ethereum Virtual Machine, while reading and writing data to memory makes it a Turing-complete system and therefore a UTM. Ethereum can compute any algorithm that can be computed by any Turing machine, given the limitations of finite memory.

Thinking Machines: The Inside Story of Artificial Intelligence and Our Race to Build the Future
by Luke Dormehl
Published 10 Aug 2016

It is a vastly complex machine, many, many times more complicated than any other machine ever made with hands; but after all a machine. It has been likened to a steam engine. But that was before we knew as much about the way it works as we know now. It really is a gas engine: like the engine of an automobile, a motor boat, or a flying machine. One of Turing’s most significant concepts related to something called the Universal Turing Machine. Instead of computers being single-purpose machines used for just one function, he explained how they could be made to perform a variety of tasks by reading step-by-step instructions from a tape. By doing so, Turing wrote that the computer ‘could in fact be made to work as a model of any other machine’.

…

(TV show) 135–9, 162, 189–90, 225, 254 Jobs, Steve 6–7, 32, 35, 108, 113, 181, 193, 231 Jochem, Todd 55–6 judges 153–4 Kasparov, Garry 137, 138–9, 177 Katz, Lawrence 159–60 Keck, George Fred 81–2 Keynes, John Maynard 139–40 Kjellberg, Felix (PewDiePie) 151 ‘knowledge engineers’ 29, 37 Knowledge Narrator 110–11 Kodak 238 Kolibree 67 Koza, John 188–9 Ktesibios of Alexandria 71–2 Kubrick, Stanley 2, 228 Kurzweil, Ray 213–14, 231–3 Landauer, Thomas 201–2 Lanier, Jaron 156, 157 Laorden, Carlos 100, 101 learning 37–9, 41–4, 52–3, 55 Deep 11–2, 56–63, 96–7, 164, 225 and email filters 88 machine 3, 71, 84–6, 88, 100, 112, 154, 158, 197, 215, 233, 237, 239 reinforcement 83, 232 and smart homes 84, 85 supervised 57 unsupervised 57–8 legal profession 145, 188, 192 LegalZoom 145 LG 132 Lickel, Charles 136–7 ‘life logging’ software 200 Linden, David J. 213–14 Loebner, Hugh 102–3, 105 Loebner Prize 102–5 Lohn, Jason 182, 183–5, 186 long-term potentiation 39–40 love 122–4 Lovelace, Ada 185, 189 Lovelace Test 185–6 Lucas, George 110–11 M2M communication 70–71 ‘M’ (AI assistant) 153 Machine Intelligence from Cortical Networks (MICrONS) project 214–15 machine learners 38 machine learning 3, 71, 84–6, 88, 100, 112, 154, 158, 197, 215, 233, 237, 239 Machine Translator 8–9, 11 ‘machine-aided recognition’ 19–20 Manhattan Project 14, 229 MARK 1 (computer) 43–4 Mattersight Corporation 127 McCarthy, John 18, 19, 20, 27, 42, 54, 253 McCulloch, Warren 40–2, 43, 60, 142–3 Mechanical Turk jobs 152–7 medicine 11, 30, 87–8, 92–5, 187–8, 192, 247, 254 memory 13, 14, 16, 38–9, 42, 49 ‘micro-worlds’ 25 Microsoft 62–3, 106–7, 111–12, 114, 118, 129 mind mapping the 210–14, 217, 218 ‘mind clones’ 203 uploads 221 mindfiles 201–2, 207, 212 Minsky, Marvin 18, 21, 24, 32, 42, 44–6, 49, 105, 205–7, 253–4 MIT 19–20, 27, 96–7, 129, 194–5 Mitsuku (chatterbot) 103–6, 108 Modernising Medicine 11 Momentum Machines, Inc. 141 Moore’s Law 209, 220, 231 Moravec’s paradox 26–7 mortgage applications 237–8 MTurk platform 153, 154, 155 music 168, 172–7, 179 Musk, Elon 149–50, 223–4 MYCIN (expert system) 30–1 nanobots 213–14 nanosensors 92 Nara Logics 118 NASA 6, 182, 184–5 natural selection 182–3 navigational aids 90–1, 126, 127, 128, 241 Nazis 15, 17, 227 Negobot 99–102 Nest Labs 67, 96, 254 Netflix 156, 198 NETtalk 51, 52–3, 60 neural networks 11–12, 38–9, 41, 42–3, 97, 118, 164–6, 168, 201, 208–9, 211, 214–15, 218, 220, 224–5, 233, 237–8, 249, 254, 256–7 neurons 40, 41–2, 46, 49–50, 207, 209–13, 216 neuroscience 40–2, 211, 212, 214, 215 New York World’s Fair 1964 5–11 Newell, Alan 19, 226 Newman, Judith 128–9 Nuance Communications 109 offices, smart 90 OpenWorm 210 ‘Optical Scanning and Information Retrieval’ 7–8, 10 paedophile detection 99–102 Page, Larry 6–7, 34, 220 ‘paperclip maximiser’ scenario 235 Papert, Seymour 27, 44, 45–6, 49 Paro (therapeutic robot) 130–1 patents 188–9 Perceiving and Recognising Automation (PARA) 43 perceptrons 43–6 personality capture 200–4 pharmaceuticals 187–8 Pitts, Walter 40–2, 43, 60 politics 119–2 Pomerlau, Dean 54, 55–6, 90 prediction 87, 198–9 Profound Hypothermia and Circulatory Arrest 219–20 punch-cards 8 Qualcomm 93 radio-frequency identification device (RFID) 65–6 Ramón y Cajal, Santiago 39–40 Rapidly Adapting Lateral Position Handler (RALPH) 55 ‘recommender system’ 198 refuse collection 142 ‘relational agents’ 130 remote working 238–9 reverse engineering 208, 216, 217 rights for AIs 248–51 risks of AI 223–40 accountability issues 240–4, 246–8 ethics 244–8 rights for AIs 248–51 technological unemployment 139–50, 163, 225, 255 robots 62, 74–7, 89–90, 130–1, 141, 149, 162, 217, 225, 227, 246–7, 255–6 Asimov’s three ethical rules of 244–8 robotic limbs 211–12 Roomba robot vacuum cleaner 75–7, 234, 236 Rosenblatt, Frank 42–6, 61, 220 rules 36–7, 79–80 Rumelhart, David 48, 50–1, 63 Russell, Bertrand 41 Rutter, Brad 138, 139 SAINT program 20 sampling (music) 155, 157 ‘Scheherazade’ (Ai storyteller) 169–70 scikit-learn 239 Scripps Health 92 Sculley, John 110–11 search engines 109–10 Searle, John 24–5 Second Life (video game) 194 Second World War 12–13, 14–15, 17, 72, 227 Sejnowski, Terry 48, 51–3 self-awareness 77, 246–7 self-driving 53–6, 90, 143, 149–50 Semantic Information Retrieval (SIR) 20–2 sensors 75–6, 80, 84–6, 93 SHAKEY robot 23–4, 27–8, 90 Shamir, Lior 172–7, 179, 180 Shannon, Claude 13, 16–18, 28, 253 shipping systems 198 Simon, Herbert 10, 19, 24, 226 Sinclair Oil Corporation 6 Singularity, the 228–3, 251, 256 Siri (AI assistant) 108–11, 113–14, 116, 118–19, 125–30, 132, 225–6, 231, 241, 256 SITU 69, 93 Skynet 231 smart devices 3, 66–7, 69–71, 73–7, 80–8, 92–7, 230–1, 254 and AI assistants 116 and feedback 73–4 problems with 94–7 ubiquitous 92–4 and unemployment 141–2 smartwatches 66, 93, 199 Sony 199–200 Sorto, Erik 211, 212 Space Invaders (video game) 37 spectrometers 93 speech recognition 59, 62, 109, 111, 114, 120 SRI International 28, 89–90, 112–13 StarCraft II (video game) 186–7 story generation 169–70 strategy 36 STUDENT program 20 synapses 209 Synthetic Interview 202–3 Tamagotchis 123–5 Tay (chatbot) 106–7 Taylorism 95–6 Teknowledge 32, 33 Terminator franchise 231, 235 Tetris (video game) 28 Theme Park (video game) 29 thermostats 73, 79, 80 ‘three wise men’ puzzle 246–7 Tojan Room, Cambridge University 69–70 ‘tortoises’ (robots) 74–7 toys 123–5 traffic congestion 90–1 transhumanists 205 transistors 16–17 Transits – Into an abyss (musical composition) 168 translation 8–9, 11, 62–3, 155, 225 Turing, Alan 3, 13–17, 28, 35, 102, 105–6, 227, 232 Turing Test 15, 101–7, 229, 232 tutors, remote 160–1 TV, smart 80, 82 Twitter 153–4 ‘ubiquitous computing’ 91–4 unemployment, technological 139–50, 163, 225, 255 universal micropayment system 156 Universal Turing Machine 15–16 Ursache, Marius 193–7, 203–4, 207 vacuum cleaners, robotic 75–7, 234, 236 video games 28–9, 35–7, 151–2, 186–7, 194, 197 Vinge, Vernor 229–30 virtual assistants 107–32, 225–6, 240–1 characteristics 126–8 falling in love with 122–4 political 119–22 proactive 116–18 therapeutic 128–31 voices 124–126, 127–8 Viv Labs 132 Vladeck, David 242–4 ‘vloggers’ 151–2 von Neumann, John 13–14, 17, 100, 229 Voxta (AI assistant) 119–20 waiter drones 141 ‘Walking Cities’ 89–90 Walter, William Grey 74–7 Warwick, Kevin 65–6 Watson (Blue J) 138–9, 162, 189–92 Waze 90–91, 126 weapons 14, 17, 72, 224–5, 234–5, 247, 255–6 ‘wetware’ 208 Wevorce 145 Wiener, Norbert 72–3, 227 Winston, Patrick 49–50 Wofram Alpha tool 108–9 Wozniak, Steve 35, 114 X.ai 116–17 Xbox 360, Kinect device 114 XCoffee 70 XCON (expert system) 31 Xiaoice 129, 130 YouTube 151 Yudkowsky, Eliezer 237–8 Zuckerberg, Mark 7, 107–8, 230–1, 254–5 Acknowledgments WRITING A BOOK is always a bit of a solitary process.

The Singularity Is Near: When Humans Transcend Biology
by Ray Kurzweil
Published 14 Jul 2005

The Turing machine, Alan Turing's theoretical conception of a universal computer in 1950, provides only seven very basic commands, yet can be organized to perform any possible computation.73 The existence of a "universal Turing machine," which can simulate any possible Turing machine that is described on its tape memory, is a further demonstration of the universality and simplicity of information.74 In The Age of Intelligent Machines, I showed how any computer could be constructed from "a suitable number of [a] very simple device," namely, the "nor" gate.75 This is not exactly the same demonstration as a universal Turing machine, but it does demonstrate that any computation can be performed by a cascade of this very simple device (which is simpler than rule 110), given the right software (which would include the connection description of the nor gates).76 Although we need additional concepts to describe an evolutionary process that create intelligent solutions to problems, Wolfram's demonstration of the simplicity an ubiquity of computation is an important contribution in our understanding of the fundamental significance of information in the world.

…

The seven commands of a Turing machine are: (1) Read Tape, (2) Move Tape Left, (3) Move Tape Right, (4) Write 0 on the Tape, (5) Write 1 on the Tape, (6) Jump to Another Command, and (7) Halt. 74. In what is perhaps the most impressive analysis in his book, Wolfram shows how a Turing machine with only two states and five possible colors can be a universal Turing machine. For forty years, we've thought that a universal Turing machine had to be more complex than this. Also impressive is Wolfram's demonstration that rule 110 is capable of universal computation, given the right software. Of course, universal computation by itself cannot perform useful tasks without appropriate software. 75.

The Stack: On Software and Sovereignty
by Benjamin H. Bratton
Published 19 Feb 2016

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 Church-Turing thesis (developed through the 1940s and 1950s) would demonstrate that Turing's “machine” not only could simulate algorithms, but that a universal Turing machine, containing all possible such machines, could, in theory, calculate all logical problems that are in fact computable (a limit that Turing's paper sought to identify). The philosophical implications are thorny and paradoxical. At the same moment that Turing demonstrates the mechanical basis for synthetic logic by machines (suggesting real artificial intelligence), he partially delinks the correlation between philosophical thought and machinic calculation.

…

It builds on distributed server and terminal architectures, extending shared computing resources across a networked organization, and just as the regulation of industrial modernity was given tempo by the longitudinal standardization of railroad and telegraph timetables, the beginning of the Cloud could just as well be dated to the inauguration of the UNIX epoch (January 1, 1970) and the starting point of UNIX Time used to synchronize computers across a network (and which today helps synchronize, for example, Linux, C, Java, and Javascript).7 But the footprint of the Cloud is measured at the scale of continents, not enterprises. Some see it as an uneven computational troposphere, others as a prototype universal Turing machine, arranged not with tape but with uneven networks of fiber optics, data centers, nested databases, terminals, and browsers.8 The Cloud layer is also a geopolitical machine, erasing some geographies and producing others, forming and destabilizing territories in competitive measure. It is at this level of The Stack that the modern coherence of the state, which would produce one sort of public, and the operations of platforms, which would produce another, can come into conflict, overlapping and interlacing one another without universal jurisdiction or resolution, but it is also where they can reinforce each other with more pervasive forms of ambient governance.

…

The experiment draws on a simple and ambitious question: What if everything you ever saw, heard, and felt, every object you ever touched, every location you ever shadowed—every externally trackable experience—could be recorded at some incredible lossless resolution and fidelity, fed into practically infinite storage, and available to recall and replay at any time? Where Turing's artificial intelligence test attempted to detect machine intelligence by testing its reflection in human cognition, projects like Bell's suggest capture of the totality of autobiographical experience by couching it within a personal universal Turing machine and so (as the research was for Microsoft) to prototype the sorts of data management, visualization, semantic sorting, editing, and indexing interfaces necessary for the yottabyte-fluent absolute User to come? Of course, in that future, part of what would be recorded are her sessions during which she plays back past experiences, which would then also be available for review later on, and so on, and so on, a mirror held up to a mirror, reflecting up into the darkness.19 The phenomenology of metadata would be overwhelming.

This Will Make You Smarter: 150 New Scientific Concepts to Improve Your Thinking
by John Brockman
Published 14 Feb 2012

Developing concepts that carve nature at its joints is the first crucial step toward understanding, not only in the Game of Life but in science and in ordinary life as well. At a more advanced level, we discover that the Game of Life is Turing complete. That is, it’s possible to build a pattern that acts like a Universal Turing Machine (a computer that can simulate any other computer). Thus, any computable function could be implemented in the Game of Life—including perhaps a function that describes a universe like the one we inhabit. It’s also possible to build a universal constructor in the Game of Life, a pattern that can build many types of complex objects, including copies of itself.

…

in time vs. outside of time, 221–24 see also mind thought experiments, 28–29 time, 1–2, 128, 138, 163, 169, 234 arrow of, 237 evolution and, 1–2, 223 thinking in vs. outside of, 221–24 time span of discretion, 334–35 Tolstoy, Leo, 34 Tooby, John, 33–36 tools, 333 top-down thinking, 157–59 Topol, Eric, 303–4 Torrey, Fuller, 279 tracery, 247 trade, 100, 258 international, 96 traffic, 125 transparent self-model, 214 Trivers, Robert, 321 Truman Show, The, 143 truth, 43, 44–45, 192, 301 as model, 72–73 and thinking in time vs. outside of time, 221–22, 223 utility vs., 135–36 Turing, Alan, 146–47 Tversky, Amos, 121, 280 Twain, Mark, 111 typewriter keyboards, 285–86 ulcers, 240 umwelt, 143–45 uncertainty, 28, 53–54, 65, 69, 72, 273, 340 and fear of the unknown, 55–57 unpredictableness, 103–4 risk literacy and, 259–61 statistical thinking and, 260 theater and, 262 see also certainty; probability unconscious, 146 rational, 146–49 understanding, 358 unintended effects of actions, 124–26, 372 uniqueness and specialness: Copernican Principle and, 11–12 in dual view of ourselves, 32 of Earth and humans, 3–5 mediocrity principle and, 6–8, 11, 12 Universal Turing Machine, 276 universe, 294, 301 causes and purposes in, 9–10 Copernican Principle and, 11–12 expansion of, 1, 11 life in, 3–5, 13–14, 292 mediocrity principle and, 6–8, 11, 12 truth and, 222 unknown, fear of, 55–57 Uranus, 361 “Use of Knowledge in Society, The” (Hayek), 258 utility, 347 truth vs., 135–36 vaccinations, 268, 279, 394 autism and, 56, 331 vanilla, 142 Veblen, Thorstein, 228 Veeck, Bill, 360 Veeck effect, 360–62 Venter, J.

Human Compatible: Artificial Intelligence and the Problem of Control
by Stuart Russell
Published 7 Oct 2019

In it, he described a simple computing device that could accept as input the description of any other computing device, together with that second device’s input, and, by simulating the operation of the second device on its input, produce the same output that the second device would have produced. We now call this first device a universal Turing machine. To prove its universality, Turing introduced precise definitions for two new kinds of mathematical objects: machines and programs. Together, the machine and program define a sequence of events—specifically, a sequence of state changes in the machine and its memory. In the history of mathematics, new kinds of objects occur quite rarely.

…

See work, elimination of Tegmark, Max, 4, 114, 138 Tellex, Stephanie, 73 Tencent, 250 tensor processing units (TPUs), 35 Terminator (film), 112, 113 Tesauro, Gerry, 55 Thaler, Richard, 244 Theory of the Leisure Class, The (Veblen), 230 Thinking, Fast and Slow (Kahneman), 238 thinking, learning from, 293–95 Thornton, Richard, 133 Times, 7, 8 tool (narrow) artificial intelligence, 46, 47, 136 TPUs (tensor processing units), 35 tragedy of the commons, 31 Transcendence (film), 3–4, 141–42 transitivity of preferences, 23–24 Treatise of Human Nature, A (Hume), 167 tribalism, 150, 159–60 truck drivers, 119 TrueSkill system, 279 Tucker, Albert, 30 Turing, Alan, 32, 33, 37–38, 40–41, 124–25, 134–35, 140–41, 144, 149, 153, 160–61 Turing test, 40–41 tutoring, 100–101 tutoring systems, 70 2001: A Space Odyssey (film), 141 Uber, 57, 182 UBI (universal basic income), 121 uncertainty AI uncertainty as to human preferences, principle of, 53, 175–76 human uncertainty as to own preferences, 235–37 probability theory and, 273–84 United Nations (UN), 250 universal basic income (UBI), 121 Universal Declaration of Human Rights (1948), 107 universality, 32–33 universal Turing machine, 33, 40–41 unpredictability, 29 utilitarian AI, 217–27 Utilitarianism ((Mill), 217–18 utilitarianism/utilitarian AI, 214 challenges to, 221–27 consequentialist AI, 217–19 ideal utilitarianism, 219 interpersonal comparison of utilities, debate over, 222–24 multiple people, maximizing sum of utilities of, 219–26 preference utilitarianism, 220 social aggregation theorem and, 220 Somalia problem and, 226–27 utility comparison across populations of different sizes, debate over, 224–25 utility function, 53–54 utility monster, 223–24 utility theory, 22–26 axiomatic basis for, 23–24 objections to, 24–26 value alignment, 137–38 Vardi, Moshe, 202–3 Veblen, Thorstein, 230 video games, 45 virtual reality authoring, 101 virtue ethics, 217 visual object recognition, 6 von Neumann, John, 23 W3C Credible Web group, 109 WALL-E (film), 255 Watson, 80 wave function, 35–36 “we’re the experts” argument, 152–54 white-collar jobs, 119 Whitehead, Alfred North, 88 whole-brain emulation, 171 Wiener, Norbert, 10, 136–38, 153, 203 Wilczek, Frank, 4 Wiles, Andrew, 185 wireheading, 205–8 work, elimination of, 113–24 caring professions and, 122 compensation effects and, 114–17 historical warnings about, 113–14 income distribution and, 123 occupations at risk with adoption of AI technology, 118–20 reworking education and research institutions to focus on human world, 123–24 striving and enjoying, relation between, 121–22 universal basic income (UBI) proposals and, 121 wage stagnation and productivity increases, since 1973, 117 “work in human–machine teams” argument, 163 World Economic Forum, 250 World Wide Web, 64 Worshipful Company of Scriveners, 109 Zuckerberg, Mark, 157 ABCDEFGHIJKLMNOPQRSTUVWXYZ About the Author Stuart Russell is a professor of Computer Science and holder of the Smith-Zadeh Chair in Engineering at the University of California, Berkeley.

The Grand Design
by Stephen Hawking and Leonard Mlodinow
Published 14 Jun 2010

In the Game of Life world, do composite objects exist that, after merely following the laws of that world for some generations, will spawn others of their kind? Not only were Conway and his students able to demonstrate that this is possible, but they even showed that such an object would be, in a sense, intelligent! What do we mean by that? To be precise, they showed that the huge conglomerations of squares that self-replicate are “universal Turing machines.” For our purposes that means that for any calculation a computer in our physical world can in principle carry out, if the machine were fed the appropriate input—that is, supplied the appropriate Game of Life world environment—then some generations later the machine would be in a state from which an output could be read that would correspond to the result of that computer calculation.

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

A companion demonstration shows that if one uses enough states, then, for any computable function, there exists a Turing machine using just two symbols. And second, one of the most astonishing results in Turing’s 1936 paper is that we do not have to build a different Turing machine for every new function we wish to compute. He showed that there exists a so-called Universal Turing Machine (UTM) that accepts as its input (that is, what’s initially written on its tape) a description of any other specific Turing machine (that description includes the state-transition table and the initial tape of the specific Turing machine) and then the UTM simulates the specific machine. That is, the details of each new function can be completely absorbed by the UTM tape, with the finite state portion of the UTM unchanging.

Power and Progress: Our Thousand-Year Struggle Over Technology and Prosperity
by Daron Acemoglu and Simon Johnson
Published 15 May 2023

He imagined an abstract computer, now called a Turing machine, that can carry out computations according to the inputs specified on a possibly infinite tape—for example, instructions to implement basic mathematical operations. He then defined a function to be computable if such a machine could compute its values. A machine is said to be a universal Turing machine if it can compute any number that can be calculated by any Turing machine. Notably, if the human mind is in essence a very sophisticated computer and the tasks that it performs are within the class of computable functions, then a universal Turing machine could replicate all human capabilities. Before World War II, however, Turing did not venture into the question of whether machines could really think and how far they could go in performing human tasks.

Life at the Speed of Light: From the Double Helix to the Dawn of Digital Life
by J. Craig Venter
Published 16 Oct 2013

A logical recipe to create these complex mechanisms was developed in the next decade. In 1936 Alan Turing, the cryptographer and pioneer of artificial intelligence, described what has come to be known as a Turing machine, which is described by a set of instructions written on a tape. Turing also defined a universal Turing machine, which can carry out any computation for which an instruction set can be written. This is the theoretical foundation of the digital computer. Turing’s ideas were developed further in the 1940s, by the remarkable American mathematician and polymath John von Neumann, who conceived of a self-replicating machine.

Rule of the Robots: How Artificial Intelligence Will Transform Everything
by Martin Ford
Published 13 Sep 2021

Turing, born in London in 1912, did groundbreaking work on the theory of computation and the nature of algorithms, and is generally regarded as the founding father of computer science. Turing’s most important accomplishment came in 1936, just two years after he graduated from the University of Cambridge, when he laid out the mathematical principles for what is today called a “universal Turing machine”—essentially the conceptual blueprint for every real-world computer that has ever been built. Turing clearly understood at the very inception of the computer age that machine intelligence was a logical and perhaps inevitable extension of electronic computation. The phrase “artificial intelligence” was coined by John McCarthy, who was then a young mathematics professor at Dartmouth College.

Diaspora
by Greg Egan
Published 1 Jan 1997

But with the carpets, it's not quite the same as random molecular motion." "Maybe not." Karpal smiled, but said nothing. "What? You've found a pattern? Don't tell me: our set of twenty thousand polysaccharide Wang Tiles just happens to form the Turing Machine for calculating pi." "No. What they form is a universal Turing Machine. They can calculate anything at all-depending on the data they start with. Every daughter fragment is like a program being fed to a chemical computer. Growth executes the program." "Ah." Paolo's curiosity was roused-but he was having some trouble picturing where the hypothetical Turing Machine put its read/write head.

The Future of the Brain: Essays by the World's Leading Neuroscientists
by Gary Marcus and Jeremy Freeman
Published 1 Nov 2014

And unlike worms and flies with their high degree of stereotypy, in which genetically determined neural circuits mediate innate behaviors, mammalian neocortical circuits are shaped by the experiences of their ancestors, in the form of genetic specialization within cortical regions, as well as by personal experiences in the form of synaptic learning, and exploit more general-purpose, flexible population coding principles that are highly sensitive to context. In that sense, the cortical column may be the closest that nature has come to evolving a universal Turing machine, a machine whose settings are adapted by a combination of genomic and learned (synaptic) mechanisms to the particular statistics of its input, be it visual, olfactory, linguistic, or otherwise. Of Men and Mice A deep understanding of the cortex necessitates querying the relevant microvariables, in particular spiking neurons, by recording the occurrences and timing of action potentials.

I, Warbot: The Dawn of Artificially Intelligent Conflict
by Kenneth Payne
Published 16 Jun 2021

Another famous mathematician, Kurt Gödel had already offered a proof of this incompleteness, but now Turing stepped in to offer further support. And, as a by-product of the proof, Turing casually invented the modern computer.12 In his landmark paper, Turing imagined a computer, which he called a ‘logical computing machine’, ever after known as the universal Turing machine. This machine, he claimed, could perform any calculation (hence ‘universal’), by disaggregating them into a series of individual steps. These would be marked on a paper tape and fed through the machine’s reader. The computer was entirely theoretical—there never was an infinitely long, one dimensional ticker tape, as he proposed.

The Myth of Artificial Intelligence: Why Computers Can't Think the Way We Do
by Erik J. Larson
Published 5 Apr 2021

Instead, he switched gears, exploring how, as he put it, to “greatly reduce” the requirement of human intuition when doing calculations. His thesis considered the powers of ingenuity, by creating ever more complicated systems of rules. (Ingenuity, it turned out, could become universal—there are machines that can take as input other machines, and thus run all the machines that can be built. This insight, technically a universal Turing machine and not a simple Turing machine, was to become the digital computer.) But in his formal work on computing, Turing had (perhaps inadvertently) let the cat out of the bag. By allowing for intuition as distinct from and outside of the operations of a purely formal system like a computer, Turing in effect suggested that there may be differences between computer programs that do math and mathematicians.

The Cultural Logic of Computation
by David Golumbia
Published 31 Mar 2009

The rules as stated in the traditional grammar books do not lend themselves to logical analysis, and so it is natural to search for some alternative method of description that will be more compatible with our modern methods of describing communication processes in general. For example, one possible method for describing a grammar is in terms of a program for a universal Turing machine. (Chomsky and Miller 1958, 92–93) Even this brief passage equivocates consistently between whether “a grammar” is something that an automaton should or should not be able to use. In other words, are the logical rules instanced by systems like Peano logic (one of the systems developed in the Frege-Turing-Gödel heritage) the same kinds of rules that structure natural languages?

Fuller Memorandum
by Stross, Charles
Published 14 Jan 2010

They're obviously taking me somewhere indoors-- Indoors? Something tells me that, yes, we are indoors now. Maybe it's the lack of fresh air, or the echoes, or the ground beneath this trolley's wheels. We must be nearly there. I distract myself, trying to recall the transition table for Cantor's 2,5 Universal Turing Machine--the one with the five chess pieces and the board. I was always crap at chess, never really got into it deeply enough at school, but I understand UTMs, and if I can hold enough moves in my head before the gray stuff turns to Swiss cheese I might be able to code something up. Damn it, Bob, you're a magician!

The Sense of Style: The Thinking Person's Guide to Writing in the 21st Century
by Steven Pinker
Published 1 Jan 2014

The new entries in AHD 5 are a showcase for the linguistic exuberance and recent cultural history of the Anglosphere: Abrahamic, air rage, amuse-bouche, backward-compatible, brain freeze, butterfly effect, carbon footprint, camel toe, community policing, crowdsourcing, Disneyfication, dispensationalism, dream catcher, earbud, emo, encephalization, farklempt, fashionista, fast-twitch, Goldilocks zone, grayscale, Grinch, hall of mirrors, hat hair, heterochrony, infographics, interoperable, Islamofascism, jelly sandal, jiggy, judicial activism, ka-ching, kegger, kerfuffle, leet, liminal, lipstick lesbian, manboob, McMansion, metabolic syndrome, nanobot, neuroethics, nonperforming, off the grid, Onesie, overdiagnosis, parkour, patriline, phish, quantum entanglement, queer theory, quilling, race-bait, recursive, rope-a-dope, scattergram, semifreddo, sexting, tag-team, time-suck, tranche, ubuntu, unfunny, universal Turing machine, vacuum energy, velociraptor, vocal percussion, waterboard, webmistress, wetware, Xanax, xenoestrogen, x-ray fish, yadda yadda yadda, yellow dog, yutz, Zelig, zettabyte, zipline If I were allowed to take just one book to the proverbial desert island, it might be a dictionary. who and whom.

Empire of the Sum: The Rise and Reign of the Pocket Calculator
by Keith Houston
Published 22 Aug 2023

At Bletchley Park, a stately home that housed Britain’s government codebreakers, he masterminded the cracking of the German “Enigma” encryption scheme, a feat that may have shortened the Second World War by up to two years.3 Before the war, Turing had published a conceptual blueprint for all programmable electronic computers, later to be dubbed the “universal Turing machine.” After the war, he devised the “imitation game,” or Turing test, that anticipated the arrival of artificial intelligence.4 Finally, Turing is remembered for the manner of his death. He was convicted of gross indecency in 1952 for a relationship with another man and was offered estrogen injections, a form of “chemical castration,” to avoid prison.

The Blockchain Alternative: Rethinking Macroeconomic Policy and Economic Theory
by Kariappa Bheemaiah
Published 26 Feb 2017

It was during the time of developing ENIAC that he met the renowned polymath, John von Neumann, and with his help went on to design a stored-program computer, the EDVAC (Electronic Discrete Variable Automatic Computer), the first binary computer (ENIAC was decimal). See Figure 4-11. Figure 4-11.General design of the Electronic Discrete Variable Automatic Computer. Reference Source: ‘The von Neumann Architecture’, The Computing Universe, 2014 From an abstract architecture perspective, von Neumann’s design is logically equivalent to Turing’s Universal Turing Machine. In fact, von Neumann had read Turing’s theoretical papers prior to designing his machine. Ultimately it was this simple design that was built upon by successive generations of computer scientists and led to the design of computers with multiple processors and the creation of parallel computing.

Jennifer Morgue
by Stross, Charles
Published 12 Jan 2006

Probably he whiffed of Laundry business — and that set off one of the traps, which yanked him in." "How do you get inside a game?" asks Pinky, looking hopeful. "Could you get me into Grand Theft Auto: Castro Club Extreme" Brains glances at him in evident disgust. "You can virtualize any universal Turing machine," he sniffs. "Okay, Bob. What precisely do you need from us in order to get the kid out of there" I point to the laptop: "I need that, running the Dungeon Master client inside the game. Plus a class four summoning grid, and a lot of luck." My guts clench. "Make that a lot more luck than usual."

Ways of Being: Beyond Human Intelligence
by James Bridle
Published 6 Apr 2022

Worse, as more cities are added to the list, the problem gets exponentially harder, because the number of options multiply. This explosive growth in possible solutions is a huge problem for mathematical algorithms, which can get lost in a maze of dead-ends and bad answers. For this reason, the travelling salesman problem is a classic example of a problem that a Universal Turing Machine – the a-machine – cannot reliably solve. It’s computationally undecidable. And what did we say about undecidability? It must be time for the o-machine. Slime moulds figuring out the shortest distances between ‘cities’. In 2018 the same slime mould, Physarum polycephalum, showed that it was able to solve the travelling salesman problem in linear time, meaning that as the problem increased in size, it kept making the most efficient decisions at every juncture.

From Bacteria to Bach and Back: The Evolution of Minds
by Daniel C. Dennett
Published 7 Feb 2017

More importantly, he showed that if their instructions included conditional branching (if-then instructions, such as “if you observe 0, replace it with 1 and move left, and if you observe 1 leave it as is and move right, and change to state n.”), then these machines could pursue indefinitely complex paths determined by the instructions, which gave them a remarkable competence: they could do anything computational. In other words, a programmable digital computer is a Universal Turing Machine, capable of mimicking any special-purpose digital computer by following a set of instructions that implement that special-purpose computer in software.13 (You don’t have to rewire your smartphone to get it to do new tasks; just download an app and turn it into a star finder or translator or hand calculator or spell-checker or.…) A huge Design Space of information-processing was made accessible by Turing, and he foresaw that there was a traversable path from Absolute Ignorance to Artificial Intelligence, a long series of lifting steps in that Design Space.

Superintelligence: Paths, Dangers, Strategies
by Nick Bostrom
Published 3 Jun 2014

E.g., MacKay (2003). 27. Murphy (2012). 28. Pearl (2009). 29. We suppress various technical details here in order not to unduly burden the exposition. We will have occasion to revisit some of these ignored issues in Chapter 12. 30. A program p is a description of string x if p, run on (some particular) universal Turing machine U, outputs x; we write this as U(p) = x. (The string x here represents a possible world.) The Kolmogorov complexity of x is then K(x):=minp {l(p): U(p) = x}, where l(p) is the length of p in bits. The “Solomonoff” probability of x is then defined as where the sum is defined over all (“minimal,” i.e. not necessarily halting) programs p for which U outputs a string starting with x (Hutter 2005). 31.

The Innovators: How a Group of Inventors, Hackers, Geniuses and Geeks Created the Digital Revolution
by Walter Isaacson
Published 6 Oct 2014

In 1939 Zuse began work on a third model, the Z3, that used electromechanical relays both for the arithmetic unit and for the memory and control units. When it was completed in 1941, it became the first fully working all-purpose, programmable digital computer. Even though it did not have a way to directly handle conditional jumps and branching in the programs, it could theoretically perform as a universal Turing machine. Its major difference from later computers was that it used clunky electromagnetic relays rather than electronic components such as vacuum tubes or transistors. Zuse’s friend Schreyer went on to write a doctoral thesis, “The Tube Relay and the Techniques of Its Switching,” that advocated using vacuum tubes for a powerful and fast computer.

The Codebreakers: The Comprehensive History of Secret Communication From Ancient Times to the Internet
by David Kahn
Published 1 Feb 1963

To prove it, he envisioned a mechanism that could move to the left or to the right an infinitely long tape marked into squares, and could read and change or read and leave unchanged the blank or the mark—the 0 or the 1—in each square. He demonstrated that this machine could compute anything that could be calculated. Then he showed that even this machine could not tell whether the unknown problems could be solved. This machine, later called the “universal Turing machine,” has come to be recognized as the idealization of general-purpose computers and Turing, therefore, as the intellectual father of the computer. This genius turned his mind to the problem of solving Enigma messages. He took the Poles’ bombe and advanced it by a quantum leap. He conceived a device that would take a cryptogram’s presumed plaintext—as the Poles had done with AnX, only longer—and run it through all possible rotor combinations until it found one that would yield the known ciphertext from the presumed plaintext.

…

G. di, 404 Turing, A., 975-76 Turning grilles, 308-09 Tut Latin, 822 Two-letter differential, 840-41, 847 Typewriter keyboards, 740-41 TYPEX, 510 Tyro, T, 89 Tyronian notes, 89 U-2 aircraft, 693, 720 U-110, 977 U-158, 504 U-505, 506 U-boats, 273, 466, 504-07 UBCHI, 301, 304 Ugaritic literature, 900 ULTRA, 601 Ultra Secret, The, 979 Unbreakable cipher, 398-400 Unicity distance, 750 Unicity point, 750 United States Air Force Security Service, 680-81 Army, 1, 12, 398, 427, 574-75, 577 Central Bureau, 577, 578 Central Intelligence Agency, 681, 684 colonial cryptology, 174-86 Data Encryption Standard, 979-81, 983 National Defense Research Committee, 558-60 Navy, 5, 12, 252, 386-88, 408, 415-19 passim, 503-04, 680, 969, 971 Philippines, Navy cryptanalytic unit, 10, 25, 47, 563, 564 poor pre-World War II cryptography, 488-89 2nd Signal Service Battalion, 576-77 Signal Companies (Radio Intelligence), 507, 578-79 Signal school, 321, 324, 325 Signal Security Service, 575, 611, 678 solution of American messages, 187, 460, 496-98, 556-57, 671 State Department, 488-501 superiority of current American cryp-tology, 730 takes world lead, 385 see also Army Security Agency; black chambers, American; censorship; Code Compilation Section; Combat Intelligence Unit; Federal Bureau of Investigation; Friedman; FRUPAC; G.2 A.6; Hitt; M-94; M-134; M-138; M-209; National Security Agency; Office of Strategic Services; OP-20-G; Radio Intelligence Division; Rochefort; Safford; SIGABA; Signal Intelligence Service; Signal Security Agency; SIGTOT; Stager; War Department Telegraph Code; word transposition Univacs, 726 Universal Pocket Code, 490 Universal Trade Code, 359, 846 Universal Turing machine, 976 Uruk, 76 Valerianus, P., 903 Valério, L. P. E., 240, 242 Vanek, V., 540 Variant Beaufort, 203, 242 Vassilyev, A. T., 619 Vatican. See papal cryptology Vātsyāyana, 74 Venice, 109-10, 114, 858 Ventris, M. G. F., 922-37 passim Verkuyl, J. A., 691 Vernam, G. S., 394, 403, 612 system, 395-403, 492, 501, 612, 825, 830, 984 Verne, J., 793-94 Vetterlein, Engineer, 555 Viaris, Marquis G.

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

Nonetheless, remarks he made at various times suggested that he intended the word automaton to encompass not just computers but brains, radar systems, the telephone system, homeostatic sys- tems within biology, and anything else that processed information and regulated itself. In at least one instance, moreover, his theory proved to be spectacularly prescien t. In the case of, say, a factory machine tool, von Neumann observed, you have an automaton that can turn out very complex parts but not another machine tool. Likewise, a universal Turing machine can output an arbitrarily complex tape but not another Turing machine. However, in almost any biological organ- ism, you have an automaton that can not only reproduce identical copies of it- self but also (through evolution) give rise to organisms that are more complex than itself. So von Neumann asked, What are the essential features required for an automaton to reproduce itself and to evolve?

How the Mind Works
by Steven Pinker
Published 1 Jan 1997

The computer scientist Joseph Weizenbaum once showed how to build one out of a die, some rocks, and a roll of toilet paper. In fact, one doesn’t even need a huge warehouse of these machines, one to do sums, another to do square roots, a third to print English sentences, and so on. One kind of Turing machine is called a universal Turing machine. It can take in a description of any other Turing machine printed on its tape and thereafter mimic that machine exactly. A single machine can be programmed to do anything that any set of rules can do. Does this mean that the human brain is a Turing machine? Certainly not. There are no Turing machines in use anywhere, let alone in our heads.

Artificial Intelligence: A Modern Approach
by Stuart Russell and Peter Norvig
Published 14 Jul 2019

Whereas the identification-in-the-limit approach concentrates on eventual convergence, the study of Kolmogorov complexity or algorithmic complexity, developed independently by Solomonoff (1964, 2009) and Kolmogorov (1965), attempts to provide a formal definition for the notion of simplicity used in Ockham’s razor. To escape the problem that simplicity depends on the way in which information is represented, it is proposed that simplicity be measured by the length of the shortest program for a universal Turing machine that correctly reproduces the observed data. Although there are many possible universal Turing machines, and hence many possible “shortest” programs, these programs differ in length by at most a constant that is independent of the amount of data. This beautiful insight, which essentially shows that any initial representation bias will eventually be overcome by the data, is marred only by the undecidability of computing the length of the shortest program.

The Art of Computer Programming: Fundamental Algorithms
by Donald E. Knuth
Published 1 Jan 1974

A suitable notation for coroutines in ALGOL-like languages was introduced in Dahl and Nygaard's SIMULA I [CACM 9 A966), 671-678], 230 BASIC CONCEPTS 1-4.5 and several excellent examples of coroutines (including replicated coroutines) appear in the book Structured Programming by O.-J. Dahl, E. W. Dijkstra, and C. A. R. Hoare, Chapter 3. The first interpretive routine may be said to be the "Universal Turing Machine," a Turing machine capable of simulating any other Turing machines. Turing machines are not actual computers; they are theoretical constructions used to prove that certain problems are unsolvable by algorithms. Interpretive routines in the conventional sense were mentioned by John Mauchly in his lectures at the Moore School in 1946.

The Best of Best New SF
by Gardner R. Dozois
Published 1 Jan 2005

But with the carpets, it’s not quite the same as random molecular motion.” “Maybe not.” Karpal smiled, but said nothing. “What? You’ve found a pattern? Don’t tell me: our set of twenty thousand polysaccharide Wang Tiles just happens to form the Turing Machine for calculating pi.” “No. What they form is a universal Turing Machine. They can calculate anything at all – depending on the data they start with. Every daughter fragment is like a program being fed to a chemical computer. Growth executes the program.” “Ah.” Paolo’s curiosity was roused – but he was having some trouble picturing where the hypothetical Turing Machine put its read/write head.

Rationality: From AI to Zombies
by Eliezer Yudkowsky
Published 11 Mar 2015

To talk about the “shortest computer program” that does something, you need to specify a space of computer programs, which requires a language and interpreter. Solomonoff induction uses Turing machines, or rather, bitstrings that specify Turing machines. What if you don’t like Turing machines? Then there’s only a constant complexity penalty to design your own universal Turing machine that interprets whatever code you give it in whatever programming language you like. Different inductive formalisms are penalized by a worst-case constant factor relative to each other, corresponding to the size of a universal interpreter for that formalism. In the better (in my humble opinion) versions of Solomonoff induction, the computer program does not produce a deterministic prediction, but assigns probabilities to strings.