Turing machine

78 results back to index


pages: 210 words: 62,771

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

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

Ada Lovelace, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, Andrew Wiles, British Empire, cellular automata, Claude Shannon: information theory, complexity theory, Conway's Game of Life, discrete time, Douglas Hofstadter, Georg Cantor, Gödel, Escher, Bach, Henri Poincaré, Internet Archive, Jacquard loom, Jacquard loom, John Conway, John von Neumann, Joseph-Marie Jacquard, Norbert Wiener, Paul Erdős, Turing complete, Turing machine, Turing test, Von Neumann architecture

Fortunately, it doesn’t require much more work to obtain some undecidable questions that are much more relevant. Does a Turing Machine Diverge on Its Encoding? Is Undecidable When we run a Turing machine on an input string there are three possible outcomes: it halts in the accept state; it halts in the reject state; or it never halts. Let us look at three questions related to this. Is it possible to construct a Turing machine that receives encodings of Turing machines as input and halts in the accept state only if the encoded Turing machine accepts its encoding? Is it possible to construct a Turing machine that receives encodings of Turing machines as input and halts in the accept state only if the encoded Turing machine rejects its encoding? Is it possible to construct a Turing machine that receives encodings of Turing machines as input and halts in the accept state only if the encoded Turing machine diverges on its its encoding?

However, this gives a contradiction, as we have shown that there is no Turing machine with this property. The conclusion is that there is no Turing machine that receives encodings of Turing machines as input and halts in the accept state only if the encoded Turing machine diverges on its its encoding. This shows that the question Does a Turing machine diverge on its encoding? is undecidable. Again, the negation will also be undecidable, so we know that the question Does a Turing machine halt on its encoding? is undecidable. The Acceptance, Halting, and Blank Tape Problems We now have two undecidable questions: Does a Turing machine accept its encoding? and Does a Turing machine halt on its encoding? We will generalize both questions. The acceptance problem: Given any Turing machine M and any input I, does M accept I?

We can ask the corresponding question. Could MFA be a Turing machine? The answer is, of course, yes. We have shown that there is an algorithm for deciding whether or not finite automata accept their encodings. Consequently, there is a Turing machine that does this. Turing Machines That Do Not Accept Their Encodings We now turn our attention to Turing machines and look at whether or not they accept their encodings. Just as with finite automata, there are Turing machines that accept their encodings and there are Turing machines that don’t. One difference from the previous case is that we know that if a finite automaton does not accept its encoding, then it has rejected its encoding, but with Turing machines there are three possible outcomes. Being told that a Turing machine does not accept its encoding does not imply that the Turing machine has rejected its encoding.


pages: 229 words: 67,599

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

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

Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, Any sufficiently advanced technology is indistinguishable from magic, Claude Shannon: information theory, conceptual framework, Fellow of the Royal Society, finite state, four colour theorem, Georg Cantor, Grace Hopper, Isaac Newton, John von Neumann, knapsack problem, New Journalism, reversible computing, Richard Feynman, Richard Feynman, Schrödinger's Cat, Steve Jobs, Steve Wozniak, thinkpad, Turing machine, Turing test, V2 rocket

At some time after we turn the Turing machine on, it presumably completes its task (whatever that might be), and the finite-state machine enters state 0 (called the halting state) and stops. Figure 9.1.1. A Turing machine. As far as I know, nobody has ever actually constructed a Turing machine. It is a purely theoretical concept. Described in 1936 by the English mathematician Alan Turing (see Shannon’s mini-biography in Chapter 3)— that is, ten years before the first actual electronic computers began to be constructed—Turing’s machines are nevertheless as powerful as any modern machine in what they can compute. Compared to a modern, electronic-speed computer, a Turing machine is really, really slow (think of a race between a snail and a photon), but time is irrelevant. There is an infinity of it yet to come. Given enough time, a Turing machine can compute anything that can be computed.2 A Turing machine’s power to compute comes not from super technology, but from its tape, for two reasons.

I’ll return to the concept of a computable number in the final section of this chapter. 9.2 TWO TURING MACHINES As my first specific example of a Turing machine, consider the following state-transition table for a Turing machine that adds any two non-negative integers m and n that are placed on the tape, leaves their sum on the tape, and then halts. Our convention for representing m and n is to write m + 1 consecutive 1s for m, then a 0, and then n + 1 consecutive 1s for n. All the rest of the tape squares, initially, have the symbol 0. (This representation for m and n is called unary notation.) The reason for using one additional 1 for each value of m and n is to allow either (or both) of m and n to be zero (which is represented by a single 1). This Turing machine is said to compute the function f (m, n) = m + n. Notice that in this machine the read/write head either doesn’t move during a machine cycle or, if it does move, it does so always to the right.

But, before we get to that, a couple of final comments on Turing machines. First, Shannon suggested that a reasonable measure of the “complexity” of a Turing machine is the product of the number of different symbols that can appear on the tape, and the number of states for the finite-state machine portion. That is, symbols and states can be traded-off against each other. In 1956, in fact, Shannon took this trade-off to the limit and proved the remarkable result that if one uses enough symbols, then, given any computable function, there exists a Turing machine with just two states that can evaluate that function. 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.


pages: 245 words: 12,162

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

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

complexity theory, computer age, four colour theorem, index card, John von Neumann, linear programming, NP-complete, p-value, RAND corporation, Richard Feynman, Richard Feynman, traveling salesman, Turing machine

Although extra tapes are convenient, anything we can compute on a multiple-tape machine can also be computed on a machine with a single tape, albeit a bit more slowly. This last point, about simulating a multiple-tape machine with a single tape, is important. We would like to define an algorithm as something that can be carried out on a single-tape Turing machine, but does this capture everything we might want in an algorithm? All we can say is that, so far, Turing machines have been able to handle everything that has been thrown at them. If something is computable on a modern-day computer, then a lightning-fast Turing machine could also carry out the computation. 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.

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. This is something we take for granted, but the creation of programmable machines was an intellectual leap, made by Turing in his original paper. 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.

Formally, P is the class of problems that can be solved in polynomial time on a single-tape Turing machine, that is, if n is the number symbols on the input tape, then the machine is guaranteed to halt after a number of steps that is at most C times nk , for some power k and some constant C . This definition of P is certainly tidy: we could replace the single-tape Turing machine by a multiple-tape machine, or even by a powerful modern digital computer, without altering the class. Indeed, the simulation of a modern computer via a Turing machine will slow down computations, but the slow-down factor is only polynomial in n. So if we have a polynomial-time algorithm on a modern computer, then we also have a polynomial-time algorithm on a single-tape Turing machine. Complexity Belonging to P is the gold standard for decision problems, but Stephen Cook studied a possibly larger class that arises in a natural way.


pages: 463 words: 118,936

Darwin Among the Machines by George Dyson

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

Ada Lovelace, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, anti-communist, British Empire, carbon-based life, cellular automata, Claude Shannon: information theory, combinatorial explosion, computer age, Danny Hillis, fault tolerance, Fellow of the Royal Society, finite state, IFF: identification friend or foe, invention of the telescope, invisible hand, Isaac Newton, Jacquard loom, Jacquard loom, James Watt: steam engine, John Nash: game theory, John von Neumann, Menlo Park, Nash equilibrium, Norbert Wiener, On the Economy of Machinery and Manufactures, packet switching, pattern recognition, phenotype, RAND corporation, Richard Feynman, Richard Feynman, spectrum auction, strong AI, the scientific method, The Wealth of Nations by Adam Smith, Turing machine, Von Neumann architecture

“The restriction is not one which seriously affects computation, since the use of more complicated states of mind can be avoided by writing more symbols on the tape.”5 The Turing machine thus embodies the relationship between a finite, if arbitrarily large, sequence of symbols in space and a finite, if arbitrarily large, sequence of events in time. Turing was careful to remove all traces of intelligence. The machine can do nothing more complicated or knowledgeable at any given moment than make a mark, erase a mark, and move the tape one square to the right or to the left. Each step in the relationship between tape and Turing machine is determined by an instruction table (now called a program) listing all possible internal states, all possible external symbols, and, for every possible combination, what to do (write or erase a symbol, move right or left, change internal state) in the event that combination comes up. The Turing machine follows instructions and never makes mistakes.

The key was added modulo 2 to the plaintext message (counting by two the way we count hours by twelve, so that 0 + 1 = 1 and 1 + 1 = 0), with 1 and 0 represented by the presence or absence of a hole in the tape. Adding the key to the enciphered text a second time would return the original text. Each Fish was a species of Turing machine, and the process by which the Colossi were used to break the various species of Fish was a textbook example of the process by which the function (or partial function) of one Turing machine could be encoded as a subsidiary function of another Turing machine to produce simulated results. The problem, of course, was that the British didn’t know the constantly changing state of the Fish; they had to guess. Colossus was programmed, in Boolean logic mode, by a plugboard and toggle switches at the back of the machine. “The flexible nature of the programming was probably proposed by Newman and perhaps also Turing, both of whom were familiar with Boolean logic, and this flexibility paid off handsomely,” recalled I.

A similar principle of distributed intelligence (enforced by need-to-know security rules) led to successful code breaking at Bletchley Park. The Turing machine, as a universal representation of the relations between patterns in space and sequences in time, has given these intuitive models of intelligence a common language that translates freely between concrete and theoretical domains. Turing’s machine has grown progressively more universal for sixty years. From McCulloch and Pitts’s demonstration of the equivalence between Turing machines and neural nets in 1943 to John von Neumann’s statement that “as far as the machine is concerned, let the whole outside world consist of a long paper tape,”51 the Turing machine has established the measure by which all models of computation have been defined. Only in theories of quantum computation—in which quantum superposition allows multiple states to exist at the same time—have the powers of the discrete-state Turing machine been left behind.


pages: 405 words: 117,219

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

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

3D printing, Ada Lovelace, agricultural Revolution, Airbnb, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, anthropic principle, Asperger Syndrome, autonomous vehicles, barriers to entry, battle of ideas, Berlin Wall, bioinformatics, British Empire, business process, carbon-based life, cellular automata, Claude Shannon: information theory, combinatorial explosion, complexity theory, continuous integration, Conway's Game of Life, cosmological principle, dark matter, dematerialisation, double helix, Douglas Hofstadter, Edward Snowden, epigenetics, Flash crash, Google Glasses, Gödel, Escher, Bach, income inequality, index card, industrial robot, Internet of things, invention of agriculture, invention of the steam engine, invisible hand, Isaac Newton, Jacquard loom, Jacquard loom, Jacques de Vaucanson, James Watt: steam engine, job automation, John von Neumann, Joseph-Marie Jacquard, millennium bug, natural language processing, Norbert Wiener, On the Economy of Machinery and Manufactures, packet switching, pattern recognition, Paul Erdős, post-industrial society, prediction markets, Ray Kurzweil, Rodney Brooks, Second Machine Age, self-driving car, Silicon Valley, speech recognition, stem cell, Stephen Hawking, Steven Pinker, strong AI, technological singularity, The Coming Technological Singularity, the scientific method, theory of mind, Turing complete, Turing machine, Turing test, Tyler Cowen: Great Stagnation, Vernor Vinge, Von Neumann architecture, Watson beat the top human players on Jeopardy!, Y2K

He then took Gödel’s theorem and reformulated it by replacing Gödel’s arithmetic-based notation with simple, hypothetical devices that became known as ‘Turing machines’. A Turing machine is like a tape recorder. The tape can move in both directions, back and forth, and the machine can record symbols on the tape by following simple instructions. There is also a ‘state register’, something we would today call ‘memory’, which keeps track of what the Turing machine has been up to. Remember Gödel’s genius idea of substituting logical operations and expressions with numbers? In turn, Turing substituted logical operations and expressions with Turing machines. A Turing machine took a statement as its input, applied a logical expression (or ‘formula’) that was written as a set of instructions, and produced a binary result: the statement was either true or false. The first thing that Turing showed was that a Turing machine capable of performing a mathematical computation was equivalent to an algorithm (i.e. a series of logical steps that processed a statement and arrived at a conclusion).

Could that be a better computer model for how human consciousness works? To build this computer model in practice Turing suggested that classical, algorithmic machines should be augmented with ‘oracles’: these are machines that can decide what is undecidable by a normal Turing machine, for instance the halting problem. But what would an oracle machine look like? And how would it function? In theory, oracle machines are just like Turing machines, with the additional ability to answer ‘yes’ or ‘no’ whenever the normal Turing machine cannot find the answer. This, effectively, transforms an improvable theorem into an axiom. Nesting Turing machines with oracles produces a hypercomputer. You can go beyond that too: you can start nesting hypercomputers together, all the way to infinity. And that would be a replica of the human mind. The provocative, and very interesting, thing about the concept of oracles is their randomness.

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


pages: 247 words: 43,430

Think Complexity by Allen B. Downey

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

Benoit Mandelbrot, cellular automata, Conway's Game of Life, Craig Reynolds: boids flock, discrete time, en.wikipedia.org, Frank Gehry, Gini coefficient, Guggenheim Bilbao, mandelbrot fractal, Occupy movement, Paul Erdős, sorting algorithm, stochastic process, strong AI, Thomas Kuhn: the structure of scientific revolutions, Turing complete, Turing machine, We are the 99%

For a given program running on a real computer, it is possible (at least in principle) to construct a Turing machine that performs an equivalent computation. The Turing machine is useful because it is possible to characterize the set of functions that can be computed by a Turing machine, which is what Turing did. Functions in this set are called Turing computable. To say that a Turing machine can compute any Turing-computable function is a tautology: it is true by definition. But Turing computability is more interesting than that. It turns out that just about every reasonable model of computation anyone has come up with is Turing complete; that is, it can compute exactly the same set of functions as the Turing machine. Some of these models, like lambda calculus, are very different from a Turing machine, so their equivalence is surprising. This observation led to the Church-Turing thesis, which is essentially a definition of what it means to be computable.

So Wolfram’s claim is that Class 4 behavior is common in the natural world and almost all of the systems that manifest it are computationally equivalent. Example 6-4. The goal of this exercise is to implement a Turing machine. See http://en.wikipedia.org/wiki/Turing_machine. Start with a copy of CA.py named TM.py. Add attributes to represent the location of the head, the action table, and the state register. Override step to implement a Turing machine update. For the action table, use the rules for a three-state busy beaver. Write a class named TMDrawer that generates an image that represents the state of the tape and the position and state of the head. For one example of what that might look like, see http://mathworld.wolfram.com/TuringMachine.html. * * * [6] See http://mathworld.wolfram.com/PrincipleofComputationalEquivalence.html. Falsifiability Wolfram holds that his principle is a stronger claim than the Church-Turing thesis because it is about the natural world rather than abstract models of computation.

Universality To understand universality, we have to understand computability theory, which is about models of computation and what they compute. One of the most general models of computation is the Turing machine, which is an abstract computer proposed by Alan Turing in 1936. A Turing machine is a 1-D CA, infinite in both directions, augmented with a read-write head. At any time, the head is positioned over a single cell. It can read the state of that cell (usually there are only two states), and it can write a new value into the cell. In addition, the machine has a register, which records the state of the machine (one of a finite number of states), and a table of rules. For each machine state and cell state, the table specifies an action. Actions include modifying the cell the head is over, and moving one cell to the left or right. A Turing machine is not a practical design for a computer, but it models common computer architectures.


pages: 372 words: 101,174

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

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

Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, Albert Michelson, anesthesia awareness, anthropic principle, brain emulation, cellular automata, Claude Shannon: information theory, cloud computing, computer age, Dean Kamen, discovery of DNA, double helix, en.wikipedia.org, epigenetics, George Gilder, Google Earth, Isaac Newton, iterative process, Jacquard loom, Jacquard loom, John von Neumann, Law of Accelerating Returns, linear programming, Loebner Prize, mandelbrot fractal, Norbert Wiener, optical character recognition, pattern recognition, Peter Thiel, Ralph Waldo Emerson, random walk, Ray Kurzweil, reversible computing, self-driving car, speech recognition, Steven Pinker, strong AI, the scientific method, theory of mind, Turing complete, Turing machine, Turing test, Wall-E, Watson beat the top human players on Jeopardy!, X Prize

But his central premise—that humans can solve Turing’s and Gödel’s insoluble problems—is unfortunately simply not true. A famous unsolvable problem called the busy beaver problem is stated as follows: Find the maximum number of 1s that a Turing machine with a certain number of states can write on its tape. So to determine the busy beaver of the number n, we build all of the Turing machines that have n states (which will be a finite number if n is finite) and then determine the largest number of 1s that these machines write on their tapes, excluding those Turing machines that get into an infinite loop. This is unsolvable because as we seek to simulate all of these n-state Turing machines, our simulator will get into an infinite loop when it attempts to simulate one of the Turing machines that does get into an infinite loop. However, it turns out that computers have nonetheless been able to determine the busy beaver function for certain ns.

Note that even though the tape is theoretically infinite in length, any actual program that does not get into an infinite loop will use only a finite portion of the tape, so if we limit ourselves to a finite tape, the machine will still solve a useful set of problems. If the Turing machine sounds simple, it is because that was its inventor’s objective. Turing wanted his machine to be as simple as possible (but no simpler, to paraphrase Einstein). Turing and Alonzo Church (1903–1995), his former professor, went on to develop the Church-Turing thesis, which states that if a problem that can be presented to a Turing machine is not solvable by it, it is also not solvable by any machine, following natural law. Even though the Turing machine has only a handful of commands and processes only one bit at a time, it can compute anything that any computer can compute. Another way to say this is that any machine that is “Turing complete” (that is, that has equivalent capabilities to a Turing machine) can compute any algorithm (any procedure that we can define).

In 1936 Alan Turing described his “Turing machine,” which was not an actual machine but another thought experiment. His theoretical computer consists of an infinitely long memory tape with a 1 or a 0 in each square. Input to the machine is presented on this tape, which the machine can read one square at a time. The machine also contains a table of rules—essentially a stored program—that consist of numbered states. Each rule specifies one action if the square currently being read is a 0, and a different action if the current square is a 1. Possible actions include writing a 0 or 1 on the tape, moving the tape one square to the right or left, or halting. Each state will then specify the number of the next state that the machine should be in. The input to the Turing machine is presented on the tape. The program runs, and when the machine halts, it has completed its algorithm, and the output of the process is left on the tape.


pages: 696 words: 143,736

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

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

Ada Lovelace, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, Any sufficiently advanced technology is indistinguishable from magic, Buckminster Fuller, call centre, cellular automata, combinatorial explosion, complexity theory, computer age, computer vision, cosmological constant, cosmological principle, Danny Hillis, double helix, Douglas Hofstadter, first square of the chessboard / second half of the chessboard, fudge factor, George Gilder, Gödel, Escher, Bach, I think there is a world market for maybe five computers, information retrieval, invention of movable type, Isaac Newton, iterative process, Jacquard loom, Jacquard loom, John von Neumann, Lao Tzu, Law of Accelerating Returns, mandelbrot fractal, Marshall McLuhan, Menlo Park, natural language processing, Norbert Wiener, optical character recognition, pattern recognition, phenotype, Ralph Waldo Emerson, Ray Kurzweil, Richard Feynman, Richard Feynman, Schrödinger's Cat, Search for Extraterrestrial Intelligence, self-driving car, Silicon Valley, speech recognition, Steven Pinker, Stewart Brand, stochastic process, technological singularity, Ted Kaczynski, telepresence, the medium is the message, traveling salesman, Turing machine, Turing test, Whole Earth Review, Y2K

Perhaps the most interesting unsolvable problem is called the Busy Beaver, which may be stated as follows: Each Turing machine has a certain number of commands in its program. Given a positive integer n, we construct all of the Turing machines that have n states (i.e., n commands). Next we eliminate those n-state Turing machines that get into an infinite loop (i.e., never halt). Finally, we select the machine (one that halts) that writes the largest number of 1s on its tape. The number of 1s that this Turing machine writes is called busy beaver of n. Tibor Rado, a mathematician and admirer of Turing, showed that there is no algorithm (that is, no Turing machine) that can compute the busy beaver function for all n’s. The crux of the problem is sorting out those n-state Turing machines that get into infinite loops. If we program a Turing machine to generate and simulate every possible n-state Turing machine, this simulator itself goes into an infinite loop when it attempts to simulate one of the n-state Turing machines that gets into an infinite loop.

Because of their hexagonal and pentagonal shape, the molecules were dubbed “buckyballs” in reference to R. Buckminster Fuller’s building designs. Busy beaver One example of a class of noncomputational functions; an unsolvable problem in mathematics. Being a “Turing machine unsolvable problem,” the busy beaver function cannot be computed by a Turing machine. To compute busy beaver of n, one creates all the n-state Turing machines that do not write an infinite number of Is on their tape. The largest number of Is written by the Turing machine in this set that writes the largest number of Is is busy beaver of n. BWA See Biowarfare Agency Byte A contraction for “by eight.” A group of eight bits clustered together to store one unit of information on a computer. A byte may correspond, for example, to a letter of the English alphabet.

He created the first theoretical computer in 1936 (first introduced in Alan M. Turing, “On Computable Numbers with an Application to the Entscheinungs Problem,” Proc. London Math. Soc. 42 [1936]: 230-265) in an eponymous conception called the Turing machine. As with a number of Turing’s breakthroughs, he would have both the first and last word. The Turing machine represented the founding of modern computational theory. It has also persisted as our primary theoretical model of a computer because of its combination of simplicity and power.The Turing machine is one example of the simplicity of the foundations of intelligence. A Turing machine consists of two primary (theoretical) units: a tape drive and a computation unit. The tape drive has a tape of infinite length on which it can write, and (subsequently) read, a series of two symbols: zero and one.


pages: 855 words: 178,507

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

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

Ada Lovelace, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, AltaVista, bank run, bioinformatics, Brownian motion, butterfly effect, citation needed, Claude Shannon: information theory, clockwork universe, computer age, conceptual framework, crowdsourcing, death of newspapers, discovery of DNA, double helix, Douglas Hofstadter, en.wikipedia.org, Eratosthenes, Fellow of the Royal Society, Gödel, Escher, Bach, Henri Poincaré, Honoré de Balzac, index card, informal economy, information retrieval, invention of the printing press, invention of writing, Isaac Newton, Jacquard loom, Jacquard loom, Jaron Lanier, jimmy wales, John von Neumann, Joseph-Marie Jacquard, Louis Daguerre, Marshall McLuhan, Menlo Park, microbiome, Milgram experiment, Network effects, New Journalism, Norbert Wiener, On the Economy of Machinery and Manufactures, PageRank, pattern recognition, phenotype, pre–internet, Ralph Waldo Emerson, RAND corporation, reversible computing, Richard Feynman, Richard Feynman, Simon Singh, Socratic dialogue, Stephen Hawking, Steven Pinker, stochastic process, talking drums, the High Line, The Wisdom of Crowds, transcontinental railway, Turing machine, Turing test, women in the workforce

The device he could not get out of his head was the Turing machine—that impossibly elegant abstraction, marching back and forth along its infinite paper tape, reading and writing symbols. 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.

In 1965 Chaitin was an undergraduate at the City College of New York, writing up a discovery he hoped to submit to a journal; it would be his first publication. He began, “In this paper the Turing machine is regarded as a general purpose computer and some practical questions are asked about programming it.” Chaitin, as a high-school student in the Columbia Science Honors Program, had the opportunity to practice programming in machine language on giant IBM mainframes, using decks of punched cards—one card for each line of a program. He would leave his card deck in the computer center and come back the next day for the program’s output. He could run Turing machines in his head, too: write 0, write 1, write blank, shift tape left, shift tape right.… The universal computer gave him a nice way to distinguish between numbers like Alice and Bob’s A and B. He could write a program to make a Turing machine print out “010101 …” a million times, and he could write down the length of that program—quite short.

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. If the number n can be computed by an algorithm that is relatively short, then n is interesting. If not, it is random. The algorithm PRINT 1 AND THEN PRINT 100 ZEROES generates an interesting number (a googol). Similarly, FIND THE FIRST PRIME NUMBER, ADD THE NEXT PRIME NUMBER, AND REPEAT A MILLION TIMES generates a number that is interesting: the sum of the first million primes. It would take a Turing machine a long time to compute that particular number, but a finite time nonetheless.


pages: 236 words: 50,763

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

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

Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, Andrew Wiles, Claude Shannon: information theory, cloud computing, complexity theory, Erdős number, four colour theorem, Gerolamo Cardano, Isaac Newton, John von Neumann, linear programming, new economy, NP-complete, Occam's razor, P = NP, Paul Erdős, Richard Feynman, Richard Feynman, smart grid, Stephen Hawking, traveling salesman, Turing machine, Turing test, Watson beat the top human players on Jeopardy!, William of Occam

This Church-Turing thesis, developed before the invention of modern computers, has stood the test of time. Everything computable, now or in the future, is indeed computable by a Turing machine. This means we don’t have to worry about the specifics of the Turing machine; other models of computers give us no more computational power. You don’t really need to understand exactly what a Turing machine is to understand computation. Just think of any programming language that has access to an unlimited amount of memory. All programming languages are functionally equivalent, and all can compute exactly what can be computed by the simple Turing machine. Turing back in 1936 showed that a Turing machine cannot in fact compute everything. The most famous example, the halting problem, says that no computer can look at some code of a program and determine whether that code will run forever or eventually halt.

Turing wondered how mathematicians thought, and came up with a formal mathematical model of that thought process, a model we now call the Turing machine, which has become the standard model of computation. Alan Turing was born in London in 1912. In the early 1930s he attended King’s College, Cambridge University, where he excelled in mathematics. During that time he thought of computation in terms of himself as a mathematician. A mathematician has a process in mind, a limited amount of memory, and a large supply of paper and pencils. The mathematician would scribble some notes on a page and either move on to the next page or go back to the previous one where he could modify what he wrote before. Turing used this intuition to create a formal model of computation we now call the Turing machine. Figure 5-1. Turing Machine. Though the machine was a very simple model, Turing stated that everything computable was computable by his machine.

If that civilization has a concept that is the same or similar to one of ours, then that concept should be natural, having been developed through multiple independent sources. Of course, we don’t have a Martian civilization to compare ourselves with, so we have to use our imagination. The Martians would have an Exigius machine of computation that would be different from the Turing machine but have the same computational ability. The Martians would have their own version of the Church-Turing thesis that everything computable is computable by an Exigius machine. So the Turing machine itself is not natural, but computation is. For P versus NP we have some non-Martian evidence. Researchers in Russia and North America with limited communication ended up developing the same P versus NP question and NP-complete problems. They had different motivation, in the East to understand the necessity of perebor and in the West to understand the power of efficient computation.


pages: 362 words: 97,862

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

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

Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, complexity theory, dematerialisation, discovery of DNA, Gödel, Escher, Bach, Henri Poincaré, informal economy, information trail, Isaac Newton, Murray Gell-Mann, Necker cube, Norbert Wiener, Richard Feynman, Richard Feynman, stem cell, trade route, Turing machine

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.) Updike, John, 79 Urbach-Wiethe disease, 227 van der Waals interactions, 26, 39, 43 Vandersypen, L., 263 (fig.)

.), 67 why we see colors, 67, 70–71, 72, 75–77 Color blindness, 68 Communications cell, 86 language, 3, 91–92 one-way versus two-way, 98 See also Information transmission Competition, for access to consciousness, 231–232, 233 (fig.) 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.)

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?


pages: 434 words: 135,226

The Music of the Primes by Marcus Du Sautoy

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

Ada Lovelace, Andrew Wiles, Arthur Eddington, Augustin-Louis Cauchy, computer age, Dava Sobel, Dmitri Mendeleev, Eratosthenes, Erdős number, four colour theorem, Georg Cantor, German hyperinflation, global village, Henri Poincaré, Isaac Newton, Jacquard loom, Jacquard loom, music of the spheres, New Journalism, Paul Erdős, Richard Feynman, Richard Feynman, Search for Extraterrestrial Intelligence, Simon Singh, Solar eclipse in 1919, Stephen Hawking, Turing machine, William of Occam, Wolfskehl Prize, Y2K

Robinson felt sure that there should be a way to exploit the groundwork laid by Turing. She understood that each Turing machine gives rise to a sequence of numbers. For example, one of the Turing machines could be made to produce a list of the square numbers 1, 4, 9, 16, …, whilst another generated the primes. One of the steps in Turing’s solution of Hilbert’s Decision Problem had been to prove that no program existed that could decide whether, given a Turing machine and a number, that number is the output of the machine. Robinson was looking for a connection between equations and Turing machines. Each Turing machine, she believed, would correspond to a particular equation. If there were such a connection, Robinson hoped that asking whether a number was the output of a particular Turing machine would translate into asking whether the equation corresponding to that machine had a solution.

If there existed a program to test equations for solutions, as Hilbert was hoping for when he posed his tenth problem, then the same program could be used, via Robinson’s as yet hypothetical connection between equations and Turing machines, to check which numbers were outputs of Turing machines. But Turing had shown that no such program – one that could decide about the outputs of Turing machines – existed. Therefore there could be no program that could decide whether equations had solutions. The answer to Hilbert’s tenth problem would be ‘no’. Robinson set about understanding why each Turing machine might have its own equation. She wanted an equation whose solutions were connected to the sequence of numbers output by the Turing machine. She was rather amused by the question she had set herself. ‘Usually in mathematics you have an equation and you want to find a solution. Here you were given a solution and you had to find the equation.

He came up with the idea of special machines that could effectively be made to behave like any person or machine that was doing arithmetic computations. They would later be known as Turing machines. Hilbert had been rather vague about what he meant by a machine that could tell whether statements could be proved. Now, thanks to Turing, Hilbert’s question had been put into focus. If one of Turing’s machines could not distinguish the provable from the unprovable, then no other machine could. So were his machines powerful enough to meet the challenge of Hilbert’s Decision Problem? While he was out one day, running along the banks of the River Cam, Turing experienced the second flash of enlightenment that told him why none of these Turing machines could be made to distinguish between statements that had proofs and those that didn’t. As he paused for a breather, lying on his back in a meadow near Granchester, he saw that an idea which had been used successfully to answer a question about irrational numbers might be applicable to this question about the existence of a machine to test for provability.


pages: 611 words: 186,716

The Diamond Age by Neal Stephenson

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

British Empire, clean water, dark matter, defense in depth, edge city, Just-in-time delivery, Mason jar, pattern recognition, sensible shoes, Silicon Valley, Socratic dialogue, South China Sea, the scientific method, Turing machine, wage slave

In other words, once Princess Nell had deciphered the messages, her stall functioned like another Turing machine. It would have been easy enough to conclude that this whole castle was, like the others, a Turing machine. But the Primer had taught Nell to be very careful about making unwarranted assumptions. Just because her stall functioned according to Turing rules did not mean that all of the others did. And even if every stall in this castle was, in fact, a Turing machine, she still could not come to any fixed conclusions. She had seen riders carrying books to and from the castle, which meant that cipherers must be at work elsewhere in this kingdom. She could not verify that all of them were Turing machines. It did not take long for Nell to attain prosperity here. After a few months (which in the Primer were summarized in as many sentences) her employers announced that they were getting more work than they could handle.

She had not yet had the opportunity to study it in detail, but after her experiences in all of King Coyote's other castles, she suspected that it, too, was just another Turing machine. Her study of the Cipherers' Market, and particularly of the rulebooks used by the cipherers to respond to messages, had taught her that for all its complexity, it too was nothing more than another Turing machine. She had come here to the Castle of King Coyote to see whether the King answered his messages according to Turing-like rules. For if he did, then the entire system- the entire kingdom- the entire Land Beyond-was nothing more than a vast Turing machine. And as she had established when she'd been locked up in the dungeon at Castle Turing, communicating with the mysterious Duke by sending messages on a chain, a Turing machine, no matter how complex, was not human. It had no soul. It could not do what a human did.

"What was your purpose in coming here?" "To obtain the twelfth key." "Anything else?" "To learn about Wizard 0.2." "Ah." "To discover whether it was, in fact, a Turing machine." "Well, you have your answer. Wizard 0.2 is most certainly a Turing machine-the most powerful ever built." "And the Land Beyond?" "All grown from seeds. Seeds that I invented." "And it is also a Turing machine, then? All controlled by Wizard 0.2?" "No," said King Coyote. "Managed by Wizard. Controlled by me." "But the messages in the Cipherers' Market control all the events in the Land Beyond, do they not?" "You are most perceptive, Princess Nell." "Those messages came to Wizard-just another Turing machine." "Open the altar," said King Coyote, pointing to a large brass plate with a keyhole in the middle. Princess Nell used her key to open the lock, and King Coyote flipped back the lid of the altar.

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

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

additive manufacturing, AI winter, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, anthropic principle, Any sufficiently advanced technology is indistinguishable from magic, artificial general intelligence, augmented reality, autonomous vehicles, Benoit Mandelbrot, Bill Joy: nanobots, bioinformatics, brain emulation, Brewster Kahle, Brownian motion, business intelligence, c2.com, call centre, carbon-based life, cellular automata, Claude Shannon: information theory, complexity theory, conceptual framework, Conway's Game of Life, cosmological constant, cosmological principle, cuban missile crisis, data acquisition, Dava Sobel, David Brooks, Dean Kamen, disintermediation, double helix, Douglas Hofstadter, en.wikipedia.org, epigenetics, factory automation, friendly AI, George Gilder, Gödel, Escher, Bach, informal economy, information retrieval, invention of the telephone, invention of the telescope, invention of writing, Isaac Newton, iterative process, Jaron Lanier, Jeff Bezos, job automation, job satisfaction, John von Neumann, Kevin Kelly, Law of Accelerating Returns, life extension, linked data, Loebner Prize, Louis Pasteur, mandelbrot fractal, Mikhail Gorbachev, mouse model, Murray Gell-Mann, mutually assured destruction, natural language processing, Network effects, new economy, Norbert Wiener, oil shale / tar sands, optical character recognition, pattern recognition, phenotype, premature optimization, randomized controlled trial, Ray Kurzweil, remote working, reversible computing, Richard Feynman, Richard Feynman, Rodney Brooks, Search for Extraterrestrial Intelligence, semantic web, Silicon Valley, Singularitarianism, speech recognition, statistical model, stem cell, Stephen Hawking, Stewart Brand, strong AI, superintelligent machines, technological singularity, Ted Kaczynski, telepresence, The Coming Technological Singularity, transaction costs, Turing machine, Turing test, Vernor Vinge, Y2K, Yogi Berra

To see machines' ability to use heuristic methods, consider one of the most interesting of the unsolvable problems, the "busy beaver" problem, formulated by Tibor Rado in 1962.31 Each Turing machine has a certain number of states that its internal program can be in, which correspond to the number of steps in its internal program. There are a number of different 4-state Turing machines that are possible, a certain number of 5-state machines, and so on. In the "busy beaver" problem, given a positive integer n, we construct all the Turing machines that have n states. The number of such machines will always be finite. Next we eliminate those n-state machines that get into an infinite loop (that is, never halt). Finally, we select the machine (one that does halt) that writes the largest number of 1s on its tape. The number of 1s that this Turing machine writes is called the busy beaver of n. Rado showed that there is no algorithm—that is, no Turing machine—that can compute this function for all ns.

The complexity of Babbage's invention stemmed only from the details of its design, which indeed proved too difficult for Babbage to implement using the technology available to him. 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 crux of the problem is sorting out those n-state machines that get into infinite loops. If we program a Turing machine to generate and simulate all possible n-state Turing machines, this simulator itself gets into an infinite loop when it attempts to simulate one of the n-state machines that gets into an infinite loop. Despite its status as an unsolvable problem (and one of the most famous), we can determine the busy-beaver function for some ns. (Interestingly, it is also an unsolvable problem to separate those ns for which we can determine the busy beaver of n from those for which we cannot.) For example, the busy beaver of 6 is easily determined to be 35. With seven states, a Turing machine can multiply, so the busy beaver of 7 is much bigger: 22,961. With eight states, a Turing machine can compute exponentials, so the busy beaver of 8 is even bigger: approximately 1043.


pages: 846 words: 232,630

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

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

Albert Einstein, Alfred Russel Wallace, anthropic principle, buy low sell high, cellular automata, combinatorial explosion, complexity theory, computer age, conceptual framework, Conway's Game of Life, Danny Hillis, double helix, Douglas Hofstadter, Drosophila, finite state, Gödel, Escher, Bach, In Cold Blood by Truman Capote, invention of writing, Isaac Newton, Johann Wolfgang von Goethe, John von Neumann, Murray Gell-Mann, New Journalism, non-fiction novel, Peter Singer: altruism, phenotype, price mechanism, prisoner's dilemma, QWERTY keyboard, random walk, Richard Feynman, Richard Feynman, Rodney Brooks, Schrödinger's Cat, Stephen Hawking, Steven Pinker, strong AI, the scientific method, theory of mind, Thomas Malthus, Turing machine, Turing test

It doesn't matter what material you make a computer out of; what matters is the algorithm it runs; and since every algorithm is finitely specifiable, it is possible to devise a uniform language for uniquely describing each algorithm and putting all the specifications in "alphabetical order." Turing devised just such a system, and in it every computer — from your laptop to the grandest parallel supercomputer that will ever be built — has a unique description as what we now call a Turing machine. The Turing machines can each be given a unique identification number — its Library of Babel Number, if you like. Gödel's Theorem can then be reinterpreted to say that each of those Turing machines that happens to be a consistent algorithm for proving truths of arithmetic (and, not surprisingly, these are a Vast but Vanishing subset of all the possible Turing machines) has associated with it a Gödel sentence — a truth of arithmetic it cannot prove. So that is what Gödel, anchored by Turing to the world of computers, tells us: every computer that is a consistent truth-of-arithmetic-prover has an Achilles' heel, a truth it can never prove, even if it runs till doomsday.

They wanted something dead simple, easy to visualize and easy to calculate, so they not only dropped from three dimensions to two; they also "digitized" both space and time — all times and distances, as we saw, are in whole numbers of "instants" and "cells." 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.

Whenever you {236} saw a glider approaching an eater, you would just predict "consumption in four generations" without bothering with the pixel-level calculations. As a second step, you could move to thinking of the gliders as symbols on the "tape" of a gigantic Turing machine, and then, adopting this higher design stance towards the configuration, predict its future as a Turing machine. At this level you would be "hand-simulating" the "machine language" of a computer program that plays chess, still a tedious way of making predictions, but orders of magnitude more efficient than working out the physics. As a third and still more efficient step, you could ignore the details of the chess-playing program itself and just assume that, whatever they are, they are good! That is, you could assume that the chess-playing program running on the Turing machine made of gliders and eaters played not just legal chess but good legal chess — it had been well designed (perhaps it has designed itself, in the manner of Samuel's checkers program) to find the good moves.


pages: 429 words: 114,726

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

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

barriers to entry, business process, Claude Shannon: information theory, computer age, deskilling, Firefox, Frederick Winslow Taylor, future of work, Grace Hopper, informal economy, information retrieval, interchangeable parts, Isaac Newton, Jacquard loom, Jacquard loom, job satisfaction, John von Neumann, knowledge worker, loose coupling, new economy, Norbert Wiener, pattern recognition, performance metric, post-industrial society, Productivity paradox, RAND corporation, Robert Gordon, sorting algorithm, Steve Jobs, Steven Levy, the market place, Thomas Kuhn: the structure of scientific revolutions, Thorstein Veblen, Turing machine, Von Neumann architecture, Y2K

In order to facilitate his exploration, Turing invented a new tool, an imaginary device capable of performing simple mechanical computations. Each Turing Machine, which consisted of only a long paper tape along with a mechanism for reading from and writing to that tape, contained a table of instructions that allowed it to perform a single computation. 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.

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. Independent of the work of theoretical computer scientists, working programmers—and their corporate employers—were discovering to their chagrin that computer software was even more complicated and expensive to develop than computer hardware.

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.


pages: 158 words: 49,168

Infinite Ascent: A Short History of Mathematics by David Berlinski

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

Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, Andrew Wiles, Benoit Mandelbrot, Douglas Hofstadter, Eratosthenes, four colour theorem, Georg Cantor, Gödel, Escher, Bach, Henri Poincaré, Isaac Newton, John von Neumann, Murray Gell-Mann, Stephen Hawking, Turing machine, William of Occam

These, too, are finite and correspond in an unspecified way to various internal configurations of the reading head, so that what the Turing machine does is a function not only of what at any moment it sees, but what at any moment it is. There is not much else. A Turing machine is a deterministic device, and like an ordinary machine, it does what it must do. Turing machines can nonetheless do rather an astonishing variety of intellectual tasks. Addition is an example, as with a few notational elaborations the logician may be observed constructing a calculating device out of thin air. Those elaborations: The machine’s single symbol is 1. Any natural number n the machine represents as a string of n + 1 consecutive 1’s, so that 0 is 1, and 1, 11, and n + m = (n + m) + 1. The following ten lines of code suffice to get this machine to add any two natural numbers. Any two (Figure 10.1). A mathematical function is computable, logicians say, if there is a Turing machine by which it can be computed. In the late 1930s, Alonzo Church and Stephen Kleene demonstrated that the recursive functions, the lambda-computable functions, and the Turing computable functions were one and the same, and so provided a single precise explication of the informal notion of an algorithm.

An effective calculation is any calculation that could be undertaken, Turing argued, by an exceptionally simple imaginary machine, or even a human computer, someone who has, like a clerk in the department of motor vehicles or a college dean, been stripped of all cognitive powers and can as a result execute only a few primitive acts. A Turing machine consists of a tape divided into squares and a reading head. Although finite, the tape may be extended in both directions. The reading head, as its name might suggest, is designed to recognize and manipulate a finite set of symbols—0 and 1, for most purposes. Beginning at an initial square, the reading head is capable of moving to the left or to the right on the tape, one square at a time, and it is capable of writing symbols on the tape or erasing the symbols that it is scanning. At any given moment, the reading head may occupy one of a number of internal states. These, too, are finite and correspond in an unspecified way to various internal configurations of the reading head, so that what the Turing machine does is a function not only of what at any moment it sees, but what at any moment it is.

The definition of the algorithm, as Gödel observed, has one unexpected property: It is completely stable in the sense that it does not depend on any underlying system of formalization. No matter where logicians begin in defining the algorithm, they always end up in the same place. Gödel regarded this circumstance as a miracle. FIG. 10.1 And so it is. In virtue of its elegance and obviousness, the definition of an algorithm in terms of Turing machines has become the standard. The usual operations of arithmetic are all Turing-computable. So, too, most algorithms. So, too, Church argued, any algorithm, the concept of a Turing machine exhausting completely the idea of an effective calculation. This last claim is known as Church’s thesis, and in the seventy years since it was advanced, it has passed progressively from a conjecture, to a persuasive definition, to a law of nature, to an unbudgeable fixture in contemporary thought. The algorithm is the second of two great ideas in Western science; the first is the calculus.


pages: 396 words: 117,149

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

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

3D printing, Albert Einstein, Amazon Mechanical Turk, Arthur Eddington, Benoit Mandelbrot, bioinformatics, Black Swan, Brownian motion, cellular automata, Claude Shannon: information theory, combinatorial explosion, computer vision, constrained optimization, correlation does not imply causation, crowdsourcing, Danny Hillis, data is the new oil, double helix, Douglas Hofstadter, Erik Brynjolfsson, experimental subject, Filter Bubble, future of work, global village, Google Glasses, Gödel, Escher, Bach, information retrieval, job automation, John Snow's cholera map, John von Neumann, Joseph Schumpeter, Kevin Kelly, lone genius, mandelbrot fractal, Mark Zuckerberg, Moneyball by Michael Lewis explains big data, Narrative Science, Nate Silver, natural language processing, Netflix Prize, Network effects, NP-complete, P = NP, PageRank, pattern recognition, phenotype, planetary scale, pre–internet, random walk, Ray Kurzweil, recommendation engine, Richard Feynman, Richard Feynman, Second Machine Age, self-driving car, Silicon Valley, speech recognition, statistical model, Stephen Hawking, Steven Levy, Steven Pinker, superintelligent machines, the scientific method, The Signal and the Noise by Nate Silver, theory of mind, transaction costs, Turing machine, Turing test, Vernor Vinge, Watson beat the top human players on Jeopardy!, white flight

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. Just as there are many models of computation equivalent to a Turing machine, there are probably many different equivalent formulations of a universal learner. The point, however, is to find the first such formulation, just as Turing found the first formulation of the general-purpose computer.

., 91, 94–95 decision tree induction, 85–89 further reading, 300–302 hill climbing and, 135 Hume and, 58–59 induction and, 80–83 intelligence and, 52, 89 inverse deduction and, 52, 82–85, 91 Master Algorithm and, 240–241, 242–243 nature and, 141 “no free lunch” theorem, 62–65 overfitting, 70–75 probability and, 173 problem of induction, 59–62 sets of rules, 68–70 Taleb, Nassim, 38, 158 Tamagotchi, 285 Technology machine learning as, 236–237 sex and evolution of, 136–137 trends in, 21–22 Terrorists, data mining to catch, 232–233 Test set accuracy, 75–76, 78–79 Tetris, 32–33 Text classification, support vector machines and, 195–196 Thalamus, 27 Theory, defined, 46 Theory of cognition, 226 Theory of everything, Master Algorithm and, 46–48 Theory of intelligence, 35 Theory of problem solving, 225 Thinking, Fast and Slow (Kahneman), 141 Thorndike, Edward, 218 Through the Looking Glass (Carroll), 135 Tic-tac-toe, algorithm for, 3–4 Time, as principal component of memory, 217 Time complexity, 5 The Tipping Point (Gladwell), 105–106 Tolstoy, Leo, 66 Training set accuracy, 75–76, 79 Transistors, 1–2 Treaty banning robot warfare, 281 Truth, Bayesians and, 167 Turing, Alan, 34, 35, 286 Turing Award, 75, 156 Turing machine, 34, 250 Turing point, Singularity and, 286, 288 Turing test, 133–134 “Turning the Bayesian crank,” 149 UCI repository of data sets, 76 Uncertainty, 52, 90, 143–175 Unconstrained optimization, 193–194. See also Gradient descent Underwood, Ben, 26, 299 Unemployment, machine learning and, 278–279 Unified inference algorithm, 256 United Nations, 281 US Patent and Trademark Office, 133 Universal learning algorithm. See Master Algorithm Universal Turing machine, 34 Uplift modeling, 309 Valiant, Leslie, 75 Value of states, 219–221 Vapnik, Vladimir, 190, 192, 193, 195 Variance, 78–79 Variational inference, 164, 170 Venter, Craig, 289 Vinge, Vernor, 286 Virtual machines, 236 Visual cortex, 26 Viterbi algorithm, 165, 305 Voronoi diagrams, 181, 183 Wake-sleep algorithm, 103–104 Walmart, 11, 69–70 War, cyber-, 19–21, 279–282, 299, 310 War of the Worlds (radio program), 156 Watkins, Chris, 221, 223 Watson, James, 122, 236 Watson, Thomas J., Sr., 219 Watson (computer), 37, 42–43, 219, 237, 238 Wave equation, 30 Web 2.0, 21 Web advertising, 10–11, 160, 305 Weighted k-nearest-neighbor algorithm, 183–185, 190 Weights attribute, 189 backpropagation and, 111 Master Algorithm and, 242 meta-learning and, 237–238 perceptron’s, 97–99 relational learning and, 229 of support vectors, 192–193 Welles, Orson, 156 Werbos, Paul, 113 Wigner, Eugene, 29 Will, George F., 276 Williams, Ronald, 112 Wilson, E.

Besides, knowledge is not just a long list of facts. Knowledge is general, and has structure. “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? If they were coded up by a human programmer, no learning is involved. Nevertheless, there’s a sense in which the microprocessor is a good analog for the Master Algorithm.

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

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

Ada Lovelace, air freight, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, anti-communist, Apple II, battle of ideas, Berlin Wall, Bill Duvall, Bill Gates: Altair 8800, Byte Shop, Claude Shannon: information theory, computer age, conceptual framework, cuban missile crisis, double helix, Douglas Engelbart, Dynabook, experimental subject, fault tolerance, Frederick Winslow Taylor, friendly fire, From Mathematics to the Technologies of Life and Death, Haight Ashbury, Howard Rheingold, information retrieval, invisible hand, Isaac Newton, James Watt: steam engine, Jeff Rulifson, John von Neumann, Menlo Park, New Journalism, Norbert Wiener, packet switching, pink-collar, popular electronics, RAND corporation, RFC: Request For Comment, Silicon Valley, Steve Crocker, Steve Jobs, Steve Wozniak, Steven Levy, Stewart Brand, Ted Nelson, Turing machine, Turing test, Vannevar Bush, Von Neumann architecture, Wiener process

Their own paper, published in 1943 as "A Logical Calculus of the Ideas Immanent in Nervous Activity," was essentially a demonstration that their idealized neural networks were functionally equivalent to Turing machines. That is, any problem that a Turing machine could solve, an appropriately designed network could also solve. And conversely, anything that was beyond a Turing machine's power-such as the decidability problem-was likewise beyond a network's power. As the science historian William Aspray has written, "With the Turing machines providing an abstract characterization of thinking in the machine world and McCulloch and Pitts's neuron nets providing one in the biological world, the equivalence result suggested a unified theory of thought that broke down barriers between the physical and biological worlds."14 Or, as McCulloch himself would put it in his 1965 autobiography Embodiments of Mind, he and Pitts had proved the equivalence of all general Turing machines, whether "man-made or begotten."

And to enable transformations between sentence structures-the sort of thing we do all the time when we go from, say, active voice Oohn kissed Mary) to passive (Mary was kissed by John) or to a question (Whom did John kiss?)- you need a grammar from the most powerful class of all, the one that is mathe- matically equivalent to a Turing machine. To put it another way, the very fact that we human beings use language in the way we do is proof that, in some sense, our brains have the computational power of a Turing machine. Or to express it still another way, the pinnacle of all possi- ble mathematical machines-the Turing machine-is also the baseline, the mini- mum needed for human cognition. Anybody who seriously wants to understand the workings of the mind had better start from there, because nothing less will do. Today, of course, Chomsky's proof that computational machines form a hier- archy is considered a major refinement of Turing's original insight, and one of the foundation stones of modern computer science.

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? To give his readers a feel for the issues involved, von Neumann started out with a thought experiment.


pages: 351 words: 107,966

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

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

Beeching cuts, British Empire, computer age, Desert Island Discs, Etonian, Turing machine

Certainly, while at Bletchley, Turing certainly was not greatly interested in social interaction. Yet he was a more radical, open, honest soul than the accounts suggest. Turing became a Fellow of King’s College before, in the late 1930s, heading for the United States, to Princeton. Building bridges between the two disciplines of mathematics and applied physics, he threw himself into the construction of a ‘Turing machine’, a machine that could carry out logical binary calculations. Having seen a tide-predicting machine some years back in Liverpool, it occurred to him that the principle of this device could be applied to his own machine, greatly speeding its function. By 1938, when it was increasingly clear that war was coming to the whole of Europe, Turing returned to England, and to King’s, with his electric multiplier machine mounted on a bread-board.

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.

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. Thus, reasoned Turing, Enigma could also be thwarted mechanically.


pages: 337 words: 93,245

Diaspora by Greg Egan

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

conceptual framework, cosmic abundance, cosmic microwave background, Fermat's Last Theorem, gravity well, Jacquard loom, Jacquard loom, stem cell, telepresence, telepresence robot, Turing machine

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. "Are you telling me only one tile changes between any two rows, where thèmachine' leaves its mark on thèdata tape' ... . The mosaics he'd seen were a riot of complexity, with no two rows remotely the same. Karpal said, "No, no. Wang's original example worked exactly like a standard Turing Machine, to simplify the argument ... but the carpets are more like an arbitrary number of different computers with overlapping data, all working in parallel.

He said, "Hao Wang proved a powerful theorem, twenty-three hundred years ago. Think of a row of Wang Tiles as being like the data tape of a Turing Machine." Paolo had the library grant him knowledge of the term; it was the original conceptual form of a generalized computing device, an imaginary machine which moved hack and forth along a limitless one-dimensional data tape, reading and writing symbols according to a given set of rules. "With the right set of tiles, to force the right pattern, the next row of the tiling will look like the data tape after the Turing Machine has performed one step of its computation. And the row after that will be the data tape after two steps, and so on. For any given Turing Machine, there's a set of Wang Tiles that can imitate it." Paolo nodded amiably. He hadn't heard of this particular quaint result, but it was hardly surprising.


pages: 238 words: 46

When Things Start to Think by Neil A. Gershenfeld

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

3D printing, Ada Lovelace, Bretton Woods, cellular automata, Claude Shannon: information theory, Dynabook, Hedy Lamarr / George Antheil, I think there is a world market for maybe five computers, invention of movable type, Iridium satellite, Isaac Newton, Jacquard loom, Jacquard loom, John von Neumann, means of production, new economy, Nick Leeson, packet switching, RFID, speech recognition, Stephen Hawking, Steve Jobs, telemarketer, the medium is the message, Turing machine, Turing test, Vannevar Bush

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. With this result he could then prove or disprove the Entscheidungsproblem for his one machine and have it apply to all of the rest. He did this by showing that it was impossible for a program to exist that could determine whether another program would eventually halt or keep running forever. Although a Turing machine was a theoretical construction, in the period after World War II a number of laboratories turned to successfully making electronic computers to replace the human "computers" who followed written instructions to carry out calculations.

Like the checkers on a checkerboard, tokens that each represent a collection of molecules get moved among sites based on how the neighboring sites are occupied. This idea has come to be known as Cellular Automata (CAs). From the 1970s onward, the group of Ed Fredkin, Tomaso Toffoli, and Norm Margolus at MIT started to make special-purpose computers designed for CAs. Because these machines entirely dispense with approximations of continuous functions, they can be much simpler and faster. And because a Turing machine can be described this way, a CA can do anything that can be done with a conventional computer. A cellular automata model of the universe is no less fundamental than one based on calculus. It's a much more natural description if a computer instead of a pencil is used to work with the model. BIT BELIEFS + 133 And the discretization solves another problem: a continuous quantity can represent an infinite amount of information.

Much to our pleasant surprise, we discovered that we could design simple continuous systems that exactly matched the response of the familiar digital ones for digital signals, but if they started in the wrong state they could use their analog freedom to synchronize onto the digital signal. Instead of splitting the job into an analog detector and then a digital search program as is done now, a physical analog part can do everything. The digital world has gone on refining Turing's machine, when even Turing understood its limits. One more area that he made a seminal contribution to was explaining how biology can form patterns by using chemical reactions. This useful behavior is easy to find in nature but hard to model on a digital computer. Now that we're approaching the end of the era of rapid increases in the performance of digital computers, like Turing we have no choice but to pay more attention to information processing in the analog world.


pages: 222 words: 74,587

Paper Machines: About Cards & Catalogs, 1548-1929 by Markus Krajewski, Peter Krapp

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

business process, double entry bookkeeping, Frederick Winslow Taylor, Gödel, Escher, Bach, index card, Index librorum prohibitorum, information retrieval, invention of movable type, invention of the printing press, Jacques de Vaucanson, Johann Wolfgang von Goethe, Joseph-Marie Jacquard, knowledge worker, means of production, new economy, paper trading, Turing machine

Historians lament this, since the usually complex sources of historiography allow for many competing or complementary takes on the genealogy of a concept. For an exemplary treatment of computing myths, see Levy 1998. 15. This comparison is not to claim that the index catalog is already a Turing machine. Comparisons, transfers, and analogies are not that simple. If the elements of a universal discrete machine are present, they still lack the computational logic of an operating system, the development of which constitutes Turing’s foundational achievement. What is described here is merely the fact that the card catalog is literally a paper machine, similar to a nontrivial Turing machine only in having similar components—no more, no less. 16. See for instance note 15 regarding the limits of the Turing machine analogy, note 1 of chapter 2 for the book flood metaphor, and notes 62 of chapter 2 and 42 of chapter 4 for the business card and bank note comparisons, respectively.

This epistemological payoff is contained in the description—in short, the necessary catachresis of historiography activates insights that are called forth by the various connotations of the metaphors chosen. 8 Chapter 1 Thus, readers ought not be too surprised by references that may appear peculiar at first. They will find correspondences between index cards and bank notes, house numbers and book shelving, card catalogs and Turing machines, masses of books and their description as waves of a flood. These images are called upon consciously, at times by way of historical quotations. Even if it is clear that a card catalog does not perfectly resemble the digital calculator or computer, I maintain that the card catalog is one precursor of computing.14 On the software side, the components of the catalog and its function correspond to the theoretical concept of a universal discrete machine as developed by Turing in 1936, with a writing/reading head (or scriptor), an infinite paper band partitioned into discrete steps (or slips), and an unambiguous set of instructions for reading and writing data.15 Moreover, on the hardware side there is a line of industrial development from library technology directly to the producers of early computing installations, pointing to the technology transfer from the catalog card to the punch card and on to modern storage media.

In addition, I owe Marguerite Avery, Wolfram Burckhardt, Anne Mark, Jasmin Meerhoff, W. Boyd Rayward, and Oliver Simons for their assistance and cooperation; last but not least, and particularly for the time in between the two books, thanks to Frau V. Weimar, May 2010 Markus Krajewski Notes Chapter 1 1. From the catalog copy in figure 1.1. 2. Turing 1987, pp. 20, 91 and also in this connection, Dotzler 1996, esp. p. 7. For the structural analogy between card catalog and Turing machine, see above all note 15 in this chapter. 3. “For the duration of a state,” as Müller 1995, p. 45 put it. 4. See Kittler 1986, pp. 244f., and Kittler 1993, pp. 170ff. 5. Translator’s note: The author uses the German word verzetteln in a double sense: putting notes and quotes down on paper slips, and sorting individual notes in an index; but also disseminating, releasing them. See Grimm and Grimm 1956, cols. 2565ff.


pages: 253 words: 80,074

The Man Who Invented the Computer by Jane Smiley

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

1919 Motor Transport Corps convoy, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, anti-communist, Arthur Eddington, British Empire, c2.com, computer age, Fellow of the Royal Society, Henri Poincaré, IBM and the Holocaust, Isaac Newton, John von Neumann, Karl Jansky, Norbert Wiener, RAND corporation, Turing machine, V2 rocket, Vannevar Bush, Von Neumann architecture

In addition to this, while the machine could operate eternally, there was no way for the machine to check itself, and so there was no way to know whether every answer was “true” or not. The lambda calculus “represented an elegant and powerful symbolism for mathematical processes of abstraction and variation,” but the Turing machine was a thought experiment that posited a mechanical operation, to be done by either a mechanism or by a human mind. Andrew Hodges, Turing’s biographer, points out that Turing’s idea “was not only a matter of abstract mathematics, not only a play of symbols, for it involved thinking about what people did in the physical world … His machines—soon to be called Turing Machines—offered a bridge, a connection between abstract symbols and the physical world. Indeed, his imagery was, for Cambridge, almost shockingly industrial.” In May 1936, Alan Turing submitted his paper, entitled “On Computable Numbers, with an Application to the Entscheidungsproblem,” to the Proceedings of the London Mathematical Society and then applied unsuccessfully for a Procter Fellowship at Princeton.

In spring 1945, right around the time that the order was going out for the ten Colossus machines to be destroyed, Womersley went to the United States and was shown ENIAC (before, in fact, it was unveiled to the general public). When Womersley got back to the UK, he was eager to build a UK version. Since, unlike Mauchly and Eckert, he happened to be quite familiar with “On Computable Numbers” and had even toyed with designing a mechanical version of a Turing machine before the war (his partner, like Mauchly and Eckert’s original partner, was in the horse-racing pari-mutuel totalizer business), he offered Turing £800 per year—£200 more than he had received at Bletchley Park—to come to the NPL. Turing began work on October 1, 1945, and he was ready with plenty of ideas. Many of his new colleagues at the NPL had also been recruited from the war effort, though from the Admiralty Computing Service, not from Bletchley Park.

Turing thought that if the hardware was fast enough and the program detailed and complex enough, roomfuls of processor units could be avoided. However, such a machine would have had difficulties of its own, according to John Gustafson, who maintains, It is clear that what he had in mind building was something very like the theoretical model in his Computability paper, the model we now call a Turing machine. It worked on one bit at a time, but used a huge amount of memory to do anything of consequence. Since he had proved that anything that was computable could be theoretically computed on such a simple device, why not build one? The CPU would only have required a handful of vacuum tubes. But such a machine is horrendously difficult to program, and even at electronic speeds, it would have been painfully slow for many simple things like floating-point arithmetic.2 One of Turing’s difficulties (or Womersley’s, as his director) was that he didn’t mind talking to the press (either the general press or journals of particular groups, such as the Institution of Radio Engineers), but when he did talk, he raised hopes that did not seem realistically capable of fulfillment, and he was often met with skepticism.


pages: 903 words: 235,753

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

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

1960s counterculture, 3D printing, 4chan, Ada Lovelace, additive manufacturing, airport security, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, algorithmic trading, Amazon Mechanical Turk, Amazon Web Services, augmented reality, autonomous vehicles, Berlin Wall, bioinformatics, bitcoin, blockchain, Buckminster Fuller, Burning Man, call centre, carbon footprint, carbon-based life, Cass Sunstein, Celebration, Florida, charter city, clean water, cloud computing, connected car, corporate governance, crowdsourcing, cryptocurrency, dark matter, David Graeber, deglobalization, dematerialisation, disintermediation, distributed generation, don't be evil, Douglas Engelbart, Edward Snowden, Elon Musk, en.wikipedia.org, Eratosthenes, ethereum blockchain, facts on the ground, Flash crash, Frank Gehry, Frederick Winslow Taylor, future of work, Georg Cantor, gig economy, global supply chain, Google Earth, Google Glasses, Guggenheim Bilbao, High speed trading, Hyperloop, illegal immigration, industrial robot, information retrieval, intermodal, Internet of things, invisible hand, Jacob Appelbaum, Jaron Lanier, Jony Ive, Julian Assange, Khan Academy, linked data, Mark Zuckerberg, market fundamentalism, Marshall McLuhan, Masdar, McMansion, means of production, megacity, megastructure, Menlo Park, Minecraft, Monroe Doctrine, Network effects, new economy, offshore financial centre, oil shale / tar sands, packet switching, PageRank, pattern recognition, peak oil, performance metric, personalized medicine, Peter Thiel, phenotype, place-making, planetary scale, RAND corporation, recommendation engine, reserve currency, RFID, Sand Hill Road, self-driving car, semantic web, sharing economy, Silicon Valley, Silicon Valley ideology, Slavoj Žižek, smart cities, smart grid, smart meter, social graph, software studies, South China Sea, sovereign wealth fund, special economic zone, spectrum auction, Startup school, statistical arbitrage, Steve Jobs, Steven Levy, Stewart Brand, Stuxnet, Superbowl ad, supply-chain management, supply-chain management software, TaskRabbit, the built environment, The Chicago School, the scientific method, Torches of Freedom, transaction costs, Turing complete, Turing machine, Turing test, universal basic income, urban planning, Vernor Vinge, Washington Consensus, web application, WikiLeaks, working poor, Y Combinator

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.

There is no planetary-scale computation, now a vast network of many billions of little Turing machines, that does not intake and absorb the Earth's chemistry in order to function. The Stack is a hungry machine, and while its curated population of algorithms may be all but massless, their processing of Earthly material is a physical event, and therefore the range of possible translations between information and mechanical appetites has another limit that is not mathematical but defined by the real finitude of substances that can force communication between both sides of this encounter.20 Furthermore, like any megamachine the Earth layer is as socially constrained as it is technologically configured, and so there are political economies of Turing machines that are only accessible through misaligned and uneven hierarchies of geography, energy, and programmability.21 This is made clear by unpacking and sifting through the hardware on which The Stack depends.

In trying to place the image, I also think about how just up the 101 freeway from where Deleuze was sitting, silicon was being repurposed as the physical medium of synthetic computational intelligence, in the areas near Palo Alto in a “valley” already having been named in honor of this element. For me these are conjoined, and not just by their geographic proximity: Deleuze on the beach contemplating (we might assume) what he called “the plane of immanence,” the field from which all potential forms emerge, and Intel's initial approximations of microprocessor technology for universal computation, putting a mini-Turing machine on a silicon wafer.5 In different ways and for different ends, both grapple with matter as vibrant, contingent, and mutable, as reproduced in the careful calculation of sets of differences drawn from particular virtual possibilities. At the end of the day, Deleuze's philosophy is more about chemistry than computation, continuities more than discrete digitalizations, but his philosophical imagery of worlds appearing from the multiplication of imminent processes and generic diagrams, on oscillations of the physical and the virtual, is not unfamiliar to the projects of information realism.


pages: 528 words: 146,459

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

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

Ada Lovelace, air freight, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Apple's 1984 Super Bowl advert, barriers to entry, Bill Gates: Altair 8800, borderless world, Buckminster Fuller, Build a better mousetrap, Byte Shop, card file, cashless society, cloud computing, combinatorial explosion, computer age, deskilling, don't be evil, Douglas Engelbart, Dynabook, fault tolerance, Fellow of the Royal Society, financial independence, Frederick Winslow Taylor, game design, garden city movement, Grace Hopper, informal economy, interchangeable parts, invention of the wheel, Jacquard loom, Jacquard loom, Jeff Bezos, jimmy wales, John von Neumann, linked data, Mark Zuckerberg, Marshall McLuhan, Menlo Park, natural language processing, Network effects, New Journalism, Norbert Wiener, Occupy movement, optical character recognition, packet switching, PageRank, pattern recognition, pirate software, popular electronics, prediction markets, pre–internet, QWERTY keyboard, RAND corporation, Robert X Cringely, Silicon Valley, Silicon Valley startup, Steve Jobs, Steven Levy, Stewart Brand, Ted Nelson, the market place, Turing machine, Vannevar Bush, Von Neumann architecture, Whole Earth Catalog, William Shockley: the traitorous eight, women in the workforce, young professional

Whereas Church relied on conventional mathematics to make his arguments, Turing used a conceptual computer, later known as the Turing Machine. The Turing Machine was a thought experiment rather than a realistic computer: the “machine” consisted of a scanning head that could read and write symbols on a tape of potentially infinite length, controlled by an “instruction table” (which we would now call a program). It was computing reduced to its simplest form. Turing also showed that his machine was “universal” in the sense that it could compute any function that it was possible to compute. Generally people described a computer as “general purpose” if it could solve a broad range of mathematical problems. Turing made a much stronger claim: that a universal computer could tackle problems not just in mathematics but in any tractable area of human knowledge. In short, the Turing Machine embodied all the logical capabilities of a modern computer.

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

., 108–109 GUI (graphical user interface), 253, 257–261, 264–267, 273, 297 Handwriting recognition technology, 297, 298 Harvard Business Review, 134 Harvard Mark I, 54–59, 73, 80, 83, 91 (photo), 104 Harvard Mark II, 83–84 Harvard University, 83–84, 104 Hewlett, William, 239, 249 Hewlett-Packard (HP), 219, 239, 249 High-speed broadband, 274 Hilbert, David, 59 Hitachi, 251 Hobbyists, 230, 231, 232–238, 239–241, 242 Hock, Dee, 158–161 Hoerni, Jean, 221 Hoff, Ted, 231–232 Hollerith, Herman, 13–18, 27, 33–36 Hollerith Electric Tabulating System, 15–18, 27, 33–34, 38 Home computing, 211–212 Homebrew Computer Club, 237, 240 Home-built computers, 219 Honeywell competitive strategies of, 132 computer recession and, 133 FACT programming language, 175 IBM-compatible computers, 128–129, 131 mainframe computers, 98, 116, 117, 124 minicomputers, 219 Hopper, Grace Murray, 59, 110, 171, 173, 174–175, 192 (photo) Human computers, 3–6, 50–51, 52–54, 65, 67–68, 71 Human Factors Research Center, 199, 258–259, 282 Human knowledge, 275–278 Human-computer interaction, 207–210, 243, 258–259 Human-factors design, 208 Hypertext, 200, 234–235, 279, 286–287 IBM 1401 mainframe computer, 95 (photo), 117, 120–123, 126, 128–129 accounting machines, 38, 121, 125, 130 Airline Control Program operating system, 160 airline reservation systems, 154–157 antitrust suit against, 187 Automatic Computing Plant, 57 BASE II computer system, 160 Bitnet, 292 business computers, 123–124, 130–133, 138–139 business practices, 21, 30, 39–40, 97 Commercial Translator, 175 compatible product lines and, 125 computer development and, 80 computer industry and, 21, 98, 117, 133 computer industry rank, 219 computer industry standardization, 135 core memory technology, 115, 150, 151 data processing computers, 112–116, 133–134 Defense Calculator (model 701), 107, 113, 114, 115 as defense contractor, 107, 151, 152 Eckert and Mauchly’s attempts to sell EMCC to, 108 electromechanical manufacturing and, 138 electronic technology, 103–107 Endicott Laboratory, 57 ENIAC and, 71–81, 92 (photo), 93, 99, 145 FORTRAN developed by, 171–175, 185, 191, 205–206, 214, 215 Harvard Mark I and, 54–59, 73, 80, 83, 91 (photo), 104 Hollerith and, 14 IBM PC as industry standard, 197 (photo), 245–249 as leader in computer technology, 106 Magnetic Drum Calculator (model 650), 106, 112, 115, 120–121 mainframe computers, 126, 130–131 MS-DOS development agreement and, 256 naming of company, 36 New Product Line, 126–128, 129 OS/2 operating system, 265 PC Jr. computer, 263 personal computers, 197 (photo), 229, 245–249 PL/1 programming language, 183 Program Development Laboratories, 180–182 public image of, 119–120 punched-card systems of, 21, 38–39, 53, 90 (photo) rent-and-refill nature of business, 36, 37–38 sales strategies of, 21, 36–37, 39–40, 138, 246 sales training, 39–40 scanning technology, 164 Selective Sequence Electronic Calculator, 104, 105–106 survival of Great Depression by, 36, 37 systems integration and, 138–139 System/360 computers, 96 (photo), 124–132, 138, 209, 210 Systems Network Architecture, 285 Tape Processing Machine (model 702), 106–107, 112–115 technical innovation, 21, 31, 36, 38–39 T-H-I-N-K motto, 33, 37, 106 time-sharing computers, 209–210 total-system design approach, 120–123 TopView operating system, 265 TSS/360 operating system, 212–213 unbundling, 187–188 war-related computing projects of, 74, 79 IBM-compatible personal computers developed by competitors, 128–129, 131, 138 market dominance of, 255, 261, 263 software development for, 254, 256–257, 264–267 IBM Selective Sequence Electronic Calculator (SSEC), 104–106, 117 Icons, desktop, 258, 260 iOS platform, 297 iPad tablets, 298 iPhone, 298 iPod devices, 298 iTunes stores, 298 Illustrated London News, 12, 88 (photo) Informatics, 177, 188 Information processing calculating engines for, 6–8 clearing houses for, 8–11 human computers for, 3–6 mechanical systems for, 13–19 telegraphy and, 11–13 Information Processing Techniques Office (IPTO), 208, 258–259, 280–283 Information storage, office, 21, 27 Information technology, 19, 25 Initial Orders program, 169 Institute for Advanced Study (IAS), Princeton, 73, 80, 93 (photo), 107, 147, 191 Instruction tables (Turing Machine), 60 Insurance industry, 4, 18, 101, 102, 109, 175, 187 Integrated circuits, 130, 131, 194 (photo), 215–219, 221, 222–225 Intel 8088 chip, 246, 247, 248 Fairchild origins of, 221, 222 integrated circuit technology and, 216 microprocessors and, 195 (fig.), 231–232, 251, 265 Interactive computing, 207–210, 243, 258–259 interface message processor (IMP), 282 International Business Machines.


pages: 370 words: 94,968

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

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

4chan, Ada Lovelace, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Bertrand Russell: In Praise of Idleness, carbon footprint, cellular automata, Claude Shannon: information theory, cognitive dissonance, complexity theory, crowdsourcing, Donald Trump, Douglas Hofstadter, George Akerlof, Gödel, Escher, Bach, high net worth, Isaac Newton, Jacques de Vaucanson, Jaron Lanier, job automation, l'esprit de l'escalier, Loebner Prize, Menlo Park, Ray Kurzweil, RFID, Richard Feynman, Richard Feynman, Ronald Reagan, Skype, statistical model, Stephen Hawking, Steve Jobs, Steven Pinker, theory of mind, Turing machine, Turing test, Von Neumann architecture, Watson beat the top human players on Jeopardy!

To Ackley’s point, most work on computation has not traditionally been on dynamic systems, or interactive ones, or ones integrating data from the real world in real time. Indeed, theoretical models of the computer—the Turing machine, the von Neumann architecture—seem like reproductions of an idealized version of conscious, deliberate reasoning. As Ackley puts it, “The von Neumann machine is an image of one’s conscious mind where you tend to think: you’re doing long division, and you run this algorithm step-by-step. And that’s not how brains operate. And only in various circumstances is that how minds operate.” I spoke next with University of Massachusetts theoretical computer scientist Hava Siegelmann, who agreed. “Turing was very [mathematically] smart, and he suggested the Turing machine as a way to describe a mathematician.16 It’s [modeling] the way a person solves a problem, not the way he recognizes his mother.”

The very fact that we, as a rule, must deliberately “get exercise” bodes poorly: I imagine the middle-class city dweller paying money for a parking space or transit pass in lieu of walking a mile or two to the office, who then pays more money for a gym membership (and drives or buses there). I grew up three miles from the Atlantic Ocean; during the summer, tanning salons a block and a half from the beach would still be doing a brisk business. To see ourselves as distinct and apart from our fellow creatures is to see ourselves as distinct and apart from our bodies. The results of adopting this philosophy have been rather demonstrably weird. Turing Machines and the Corporeal IOU Wanting to get a handle on how these questions of soul and body intersect computer science, I called up the University of New Mexico’s and the Santa Fe Institute’s Dave Ackley, a professor in the field of artificial life. “To me,” he says, “and this is one of the rants that I’ve been on, that ever since von Neumann and Turing and the ENIAC guys15 built machines, the model that they’ve used is the model of the conscious mind—one thing at a time, nothing changing except by conscious thought—no interrupts, no communication from the outside world.

This fits in nicely with our sense of an inner homunculus pulling the levers and operating our body from a control room behind our eyeballs. It fits in nicely with Aristotle’s notion that thinking is the most human thing we can do. And so we compensate accordingly. I almost wonder if micromanagement comes from the same over-biasing of deliberate conscious awareness that led, both to and out of, the Turing machine model of computation underlying all of our computers today. Aware of everything, acting logically, from the top down, step-by-step. But bodies and brains are, of course, not like that at all. Micromanagement and out-of-control executive compensation are odd in a way that dovetails precisely with what’s odd about our rationalist, disembodied, brain-in-a-vat ideas about ourselves. When I fight off a disease bent on my cellular destruction, when I marvelously distribute energy and collect waste with astonishing alacrity even in my most seemingly fatigued moments, when I slip on ice and gyrate crazily but do not fall, when I unconsciously counter-steer my way into a sharp bicycle turn, taking advantage of physics I do not understand using a technique I am not even aware of using, when I somehow catch the dropped oranges before I know I’ve dropped them, when my wounds heal in my ignorance, I realize how much bigger I am than I think I am.


pages: 239 words: 56,531

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

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

Albert Einstein, Andrew Keen, Apple II, Berlin Wall, British Empire, Brownian motion, Buckminster Fuller, Burning Man, butterfly effect, computer age, crowdsourcing, cuban missile crisis, Dissolution of the Soviet Union, don't be evil, Douglas Engelbart, Dynabook, East Village, Edward Lorenz: Chaos theory, Fall of the Berlin Wall, Francis Fukuyama: the end of history, Frank Gehry, Grace Hopper, gravity well, Guggenheim Bilbao, Honoré de Balzac, Howard Rheingold, invention of movable type, Isaac Newton, Jacquard loom, Jacquard loom, Jane Jacobs, Jeff Bezos, John von Neumann, Mark Zuckerberg, Marshall McLuhan, Mercator projection, Mother of all demos, mutually assured destruction, Network effects, new economy, Norbert Wiener, PageRank, pattern recognition, planetary scale, Plutocrats, plutocrats, Post-materialism, post-materialism, Potemkin village, RFID, Richard Feynman, Richard Feynman, Richard Stallman, Robert X Cringely, Schrödinger's Cat, Search for Extraterrestrial Intelligence, SETI@home, Silicon Valley, Skype, social software, spaced repetition, Steve Ballmer, Steve Jobs, Steve Wozniak, Ted Nelson, the built environment, The Death and Life of Great American Cities, the medium is the message, Thomas L Friedman, Turing machine, Turing test, urban planning, urban renewal, Vannevar Bush, walkable city, Watson beat the top human players on Jeopardy!, William Shockley: the traitorous eight

Written just before the war, Turing’s master’s thesis, “On Computable Numbers,” was his greatest contribution to computer science. 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.


pages: 626 words: 181,434

I Am a Strange Loop by Douglas R. Hofstadter

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

Albert Einstein, Andrew Wiles, Benoit Mandelbrot, Brownian motion, double helix, Douglas Hofstadter, Georg Cantor, Gödel, Escher, Bach, Isaac Newton, James Watt: steam engine, John Conway, John von Neumann, mandelbrot fractal, pattern recognition, Paul Erdős, place-making, probability theory / Blaise Pascal / Pierre de Fermat, publish or perish, random walk, Ronald Reagan, self-driving car, Silicon Valley, telepresence, Turing machine

For instance, consider the case of John Searle, a philosopher who has spent much of his career heaping scorn on artificial-intelligence research and computational models of thinking, taking special delight in mocking Turing machines. A momentary digression… Turing machines are extremely simple idealized computers whose memory consists of an infinitely long (i.e., arbitrarily extensible) “tape” of so-called “cells”, each of which is just a square that either is blank or has a dot inside it. A Turing machine comes with a movable “head”, which looks at any one square at a time, and can “read” the cell (i.e., tell if it has a dot or not) and “write” on it (i.e., put a dot there, or erase a dot). Lastly, a Turing machine has, stored in its “head”, a fixed list of instructions telling the head under which conditions to move left one cell or right one cell, or to make a new dot or to erase an old dot. Though the basic operations of all Turing machines are supremely trivial, any computation of any sort can be carried out by an appropriate Turing machine (numbers being represented by adjacent dot-filled cells, so that “•••” flanked by blanks would represent the integer 3).

Though the basic operations of all Turing machines are supremely trivial, any computation of any sort can be carried out by an appropriate Turing machine (numbers being represented by adjacent dot-filled cells, so that “•••” flanked by blanks would represent the integer 3). Back now to philosopher John Searle. He has gotten a lot of mileage out of the fact that a Turing machine is an abstract machine, and therefore could, in principle, be built out of any materials whatsoever. In a ploy that, in my opinion, should fool only third-graders but that unfortunately takes in great multitudes of his professional colleagues, he pokes merciless fun at the idea that thinking could ever be implemented in a system made of such far-fetched physical substrates as toilet paper and pebbles (the tape would be an infinite roll of toilet paper, and a pebble on a square of paper would act as the dot in a cell), or Tinkertoys, or a vast assemblage of beer cans and ping-pong balls bashing together.

Page 26 abstractions are central…in the study of the brain… See [Treisman], [Minsky 1986], [Schank], [Hofstadter and FARG], [Kanerva], [Fauconnier], [Dawkins], [Blackmore], and [Wheelis] for spellings-out of these abstract ideas. Page 27 Just as the notion of “gene” as an invisible entity that enabled… See [ Judson]. Page 27 and just as the notion of “atoms” as the building blocks… See [Pais 1986], [Pais 1991], [Hoffmann], and [Pullman]. Page 28 Turing machines are…idealized computers… See [Hennie] and [Boolos and Jeffrey]. Page 29 In his vivid writings, Searle gives… See Chapter 22 of [Hofstadter and Dennett]. Page 29 one particular can that would “pop up”… In his smugly dismissive review [Searle] of [Hofstadter and Dennett], Searle states: “So let us imagine our thirst-simulating program running on a computer made entirely of old beer cans, millions (or billions) of old beer cans that are rigged up to levers and powered by windmills.


pages: 144 words: 43,356

Surviving AI: The Promise and Peril of Artificial Intelligence by Calum Chace

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

3D printing, Ada Lovelace, AI winter, Airbnb, artificial general intelligence, augmented reality, barriers to entry, bitcoin, blockchain, brain emulation, Buckminster Fuller, cloud computing, computer age, computer vision, correlation does not imply causation, credit crunch, cryptocurrency, cuban missile crisis, dematerialisation, discovery of the americas, disintermediation, don't be evil, Elon Musk, en.wikipedia.org, epigenetics, Erik Brynjolfsson, everywhere but in the productivity statistics, Flash crash, friendly AI, Google Glasses, industrial robot, Internet of things, invention of agriculture, job automation, John Maynard Keynes: Economic Possibilities for our Grandchildren, John Maynard Keynes: technological unemployment, John von Neumann, Kevin Kelly, life extension, low skilled workers, Mahatma Gandhi, means of production, mutually assured destruction, Nicholas Carr, pattern recognition, Peter Thiel, Ray Kurzweil, Rodney Brooks, Second Machine Age, self-driving car, Silicon Valley, Silicon Valley ideology, Skype, South Sea Bubble, speech recognition, Stanislav Petrov, Stephen Hawking, Steve Jobs, strong AI, technological singularity, theory of mind, Turing machine, Turing test, universal basic income, Vernor Vinge, wage slave, Wall-E

His work is estimated to have shortened the war by two years, but incredibly, his reward was to be prosecuted for homosexuality and obliged to accept injections of synthetic oestrogen which rendered him impotent. He died two years later and it took 57 years before a British government apologised for this barbaric behaviour. Before the war, in 1936, Turing had already devised a theoretical device called a Turing machine. It consists of an infinitely long tape divided into squares, each bearing a single symbol. Operating according to the directions of an instruction table, a reader moves the tape back and forth, reading one square – and one symbol – at a time. Together with his PhD tutor Alonzo Church he formulated the Church-Turing thesis, which says that a Turing machine can simulate the logic of any computer algorithm. (That word “algorithm” crops up a lot in computer science. It simply means a set of rules, or instructions, for a computer to follow. An algorithm is not a programme which tells a computer how to handle a particular situation such as opening a spreadsheet, or calculating the sum of a column of figures.

The algorithm builds an internal model and uses it to make predictions, which it tests against additional data and then refines the model.) Turing is also famous for inventing a test for artificial consciousness called the Turing Test, in which a machine proves that it is conscious by rendering a panel of human judges unable to determine that it is not (which is essentially the test that we humans apply to each other). The birth of computing The first design for a Turing machine was made by Charles Babbage, a Victorian academic and inventor, long before Turing’s birth. Babbage never finished the construction of his devices, although working machines have recently been built based on his designs. His Difference Engine (designed in 1822) would carry out basic mathematical functions, and the Analytical Engine (design never completed) would carry out general purpose computation.

The Art of Computer Programming: Fundamental Algorithms by Donald E. Knuth

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

discrete time, distributed generation, fear of failure, Fermat's Last Theorem, Isaac Newton, Jacquard loom, Jacquard loom, John von Neumann, linear programming, linked data, Menlo Park, probability theory / Blaise Pascal / Pierre de Fermat, Richard Feynman, sorting algorithm, stochastic process, Turing machine

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 most notable early interpreters, chiefly intended to provide a convenient means of doing floating point arithmetic, were certain routines for the Whirlwind I (by C.

At the time this chapter was first written, several interesting results of this kind had been obtained (notably by J. Hartmanis and R. E. Stearns) but only for special classes of Turing machines having multiple tapes and read/write heads. The Turing machine model is comparatively unrealistic, so these results tended to have little to do with practical problems. We must admit that, as the number n of nodes created by a linking automa- automaton approaches infinity, we don't know how to build such a device physically, since we want the machine operations to take the same amount of time regardless of the size of n; if linking is represented by using addresses as in a computer memory, it is necessary to put a bound on the number of nodes, since the link fields have a fixed size. A multitape Turing machine is therefore a more realistic model when n approaches infinity. Yet it seems reasonable to believe that a linking automaton as described above leads to a more appropriate theory of the complexity of algorithms than Turing machines do, even when asymptotic formulas for large n are considered, because the theory is more likely to be relevant for practical values of n.

Yet it seems reasonable to believe that a linking automaton as described above leads to a more appropriate theory of the complexity of algorithms than Turing machines do, even when asymptotic formulas for large n are considered, because the theory is more likely to be relevant for practical values of n. Furthermore when n gets bigger than 1030 or so, not even a one-tape Turing machine is realistic: It could never be built. Relevance is more important than realism. Many years have passed since the author wrote most of the comments above, and everybody can be glad that substantial progress has indeed been made on the theory of linking automata (now called pointer machines). But of course much still remains to be done. 2.6 HISTORY AND BIBLIOGRAPHY 465 General rules for programming have been discovered. Most of them have been used in the Kansas City freight yards for a long time. — DERRICK LEHMER A949) You will, I am sure, agree with me ... that if page 534 finds us only in the second chapter, the length of the first one must have been really intolerable. — SHERLOCK HOLMES, in The Valley of Fear A888) ANSWERS TO EXERCISES / am not bound to please thee with my answers.


pages: 574 words: 164,509

Superintelligence: Paths, Dangers, Strategies by Nick Bostrom

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

agricultural Revolution, AI winter, Albert Einstein, algorithmic trading, anthropic principle, anti-communist, artificial general intelligence, autonomous vehicles, barriers to entry, bioinformatics, brain emulation, cloud computing, combinatorial explosion, computer vision, cosmological constant, dark matter, DARPA: Urban Challenge, data acquisition, delayed gratification, demographic transition, Douglas Hofstadter, Drosophila, Elon Musk, en.wikipedia.org, epigenetics, fear of failure, Flash crash, Flynn Effect, friendly AI, Gödel, Escher, Bach, income inequality, industrial robot, informal economy, information retrieval, interchangeable parts, iterative process, job automation, John von Neumann, knowledge worker, Menlo Park, meta analysis, meta-analysis, mutually assured destruction, Nash equilibrium, Netflix Prize, new economy, Norbert Wiener, NP-complete, nuclear winter, optical character recognition, pattern recognition, performance metric, phenotype, prediction markets, price stability, principal–agent problem, race to the bottom, random walk, Ray Kurzweil, recommendation engine, reversible computing, social graph, speech recognition, Stanislav Petrov, statistical model, stem cell, Stephen Hawking, strong AI, superintelligent machines, supervolcano, technological singularity, technoutopianism, The Coming Technological Singularity, The Nature of the Firm, Thomas Kuhn: the structure of scientific revolutions, transaction costs, Turing machine, Vernor Vinge, Watson beat the top human players on Jeopardy!, World Values Survey

By the Church–Turing thesis, all computable functions are computable by a Turing machine. Since any of the three forms of superintelligence could simulate a Turing machine (if given access to unlimited memory and allowed to operate indefinitely), they are by this formal criterion computationally equivalent. Indeed, an average human being (provided with unlimited scrap paper and unlimited time) could also implement a Turing machine, and thus is also equivalent by the same criterion. What matters for our purposes, however, is what these different systems can achieve in practice, with finite memory and in reasonable time. And the efficiency variations are so great that one can readily make some distinctions. For example, a typical individual with an IQ of 85 could be taught to implement a Turing machine. (Conceivably, it might even be possible to train some particularly gifted and docile chimpanzee to do this.)

Nets lacking hidden layers had previously been shown to have severely limited functionality (Minsky and Papert 1969). 26. 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.


pages: 481 words: 125,946

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

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

3D printing, agricultural Revolution, AI winter, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, algorithmic trading, artificial general intelligence, augmented reality, autonomous vehicles, bitcoin, blockchain, clean water, cognitive dissonance, Colonization of Mars, complexity theory, computer age, computer vision, constrained optimization, corporate personhood, cosmological principle, cryptocurrency, cuban missile crisis, Danny Hillis, dark matter, discrete time, Elon Musk, Emanuel Derman, endowment effect, epigenetics, Ernest Rutherford, experimental economics, Flash crash, friendly AI, Google Glasses, hive mind, income inequality, information trail, Internet of things, invention of writing, iterative process, Jaron Lanier, job automation, John von Neumann, Kevin Kelly, knowledge worker, loose coupling, microbiome, Moneyball by Michael Lewis explains big data, natural language processing, Network effects, Norbert Wiener, pattern recognition, Peter Singer: altruism, phenotype, planetary scale, Ray Kurzweil, recommendation engine, Republic of Letters, RFID, Richard Thaler, Rory Sutherland, Search for Extraterrestrial Intelligence, self-driving car, sharing economy, Silicon Valley, Skype, smart contracts, speech recognition, statistical model, stem cell, Stephen Hawking, Steve Jobs, Steven Pinker, Stewart Brand, strong AI, Stuxnet, superintelligent machines, supervolcano, the scientific method, The Wisdom of Crowds, theory of mind, Thorstein Veblen, too big to fail, Turing machine, Turing test, Von Neumann architecture, Watson beat the top human players on Jeopardy!, Y2K

Nowadays we have some novel performing entities, such as Apple Siri, Microsoft Cortana, Google Now, and Amazon Echo. These exciting modern services often camp it up with “female” vocal chat. They talk like Turing women—or, rather, they emit lines of dialog somewhat like voice-over actresses. However, they also offer swift access to vast fields of combinatorial Big Data that no human brain could ever contain, or will ever contain. These services are not stand-alone Turing Machines. They’re amorphous global networks, combing through clouds of Big Data, algorithmically cataloging responses from human users, providing real-time user response with wireless broadband, while wearing the pseudohuman mask of a fake individual so as to meet some basic interface-design needs. That’s what they are. Every aspect of the tired “artificial intelligence” metaphor actively gets in the way of our grasping how, why, where, and for whom that is done.

In fact, natural cognition is likely much more complex and detailed than our current incarnations of artificial intelligence or cognitive computing. For example, how sophisticated do we have to imagine natural cognition, when quantum coherence at room temperature can help birds in our garden sense the magnetic field? How complex do we have to imagine embodied cognition in octopi, when it’s possible to build Turing Machines made exclusively of artificial muscles? How should we answer these questions, when we’re still far from recording in full detail what’s going on in our brains? My guess is that in 200 years our current thinking machines will look as primitive as the original Mechanical Turk. However sophisticated they may become, our machines are still primitive compared to the resolution and efficiency of natural cognition.

MACHINES THAT THINK? NUTS! STUART A. KAUFFMAN Pioneer of biocomplexity research; affiliate, Institute for Systems Biology, Seattle; author, Reinventing the Sacred: A New View of Science, Reason, and Religion The advent of quantum biology, light-harvesting molecules, bird navigation, perhaps smell, suggests that sticking to classical physics in biology may turn out to be simply stubborn. Now Turing Machines are discrete state (0,1), discrete time (T, T+1) subsets of classical physics. We all know they, like Shannon information, are merely syntactic. Wonderful mathematical results such as Gregory Chaitin’s omega—the probability that a program will halt, which is totally non-computable and nonalgorithmic—tell us that the human mind, as Roger Penrose also argued, cannot be merely algorithmic. Mathematics is creative.


pages: 285 words: 78,180

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

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

Albert Einstein, Alfred Russel Wallace, Barry Marshall: ulcers, bioinformatics, borderless world, Brownian motion, clean water, discovery of DNA, double helix, epigenetics, experimental subject, Isaac Newton, Islamic Golden Age, John von Neumann, Louis Pasteur, Mars Rover, Mikhail Gorbachev, phenotype, Richard Feynman, Richard Feynman, stem cell, the scientific method, Thomas Kuhn: the structure of scientific revolutions, Turing machine

In 1929 the young Irish crystallographer John Desmond Bernal (1901–1971) imagined the possibility of machines with a lifelike ability to reproduce themselves, in a “post-biological future” he described in The World, the Flesh & the Devil: “To make life itself will be only a preliminary stage. The mere making of life would only be important if we intended to allow it to evolve of itself anew.” 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. Just as Turing had envisaged a universal machine, so von Neumann envisaged a universal constructor.

Watson and Crick described the elegantly functional molecular structure of the double helix, and how DNA is reproduced so its instructions can be passed down the generations. This is nature’s self-reproducing automaton. The onset of efforts to create another kind of self-reproducing automaton, along with the beginnings of artificial-life research, date back to around this period, when the first modern computers came into use. The discovery of the coded nature of life’s genetic information system led naturally to parallels with Turing machines. Turing himself, in his key 1950 paper on artificial intelligence, discussed how survival of the fittest was “a slow method” that could possibly be given a boost, not least because an experimenter was not restricted to random mutations.26 Many began to believe that artificial life would emerge from complex logical interactions within a computer. Various streams of thought combined at this point: the theories of von Neumann, with his work on early computers and his self-reproducing automaton; of Turing, who posed basic questions about machine intelligence27; and of the American mathematician Norbert Weiner, who applied ideas from information theory and self-regulating processes to living things in the field of cybernetics,28 described in his book Cybernetics, published in 1948.


pages: 661 words: 187,613

The Language Instinct: How the Mind Creates Language by Steven Pinker

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

Albert Einstein, cloud computing, David Attenborough, double helix, Drosophila, elephant in my pajamas, finite state, illegal immigration, Loebner Prize, Maui Hawaii, meta analysis, meta-analysis, natural language processing, out of africa, P = NP, phenotype, rolodex, Ronald Reagan, Saturday Night Live, speech recognition, Steven Pinker, theory of mind, transatlantic slave trade, Turing machine, Turing test, Yogi Berra

It took Alan Turing, the brilliant British mathematician and philosopher, to make the idea of a mental representation scientifically respectable. Turing described a hypothetical machine that could be said to engage in reasoning. In fact this simple device, named a Turing machine in his honor, is powerful enough to solve any problem that any computer, past, present, or future, can solve. And it clearly uses an internal symbolic representation—a kind of mentalese—without requiring a little man or any occult processes. By looking at how a Turing machine works, we can get a grasp of what it would mean for a human mind to think in mentalese as opposed to English. In essence, to reason is to deduce new pieces of knowledge from old ones. A simple example is the old chestnut from introductory logic: if you know that Socrates is a man and that all men are mortal, you can figure out that Socrates is mortal.

A grammar composed of a set of phrase structure rules, which build a deep-structure tree, and one or more transformational rules, which move the phrases in the deep structure to yield a surface-structure tree. transitive. See intransitive. Turing machine. A design for a simple computer consisting of a potentially infinite strip of paper, and a processor that can move along the paper and print or erase symbols on it in a sequence that depends on which symbol the processor is currently reading and which of several states it is in. Though too clumsy for practical use, a Turing machine is thought to be capable of computing anything that any digital computer, past, present, or future, can compute. Universal Grammar. The basic design underlying the grammars of all human languages; also refers to the circuitry in children’s brains that allows them to learn the grammar of their parents’ language.

The neuron at the receiving end adds up any signals coming in from excitatory synapses, subtracts any signals coming in from inhibitory synapses, and if the sum exceeds a threshold, the receiving neuron becomes active itself. A network of these toy neurons, if large enough, can serve as a computer, calculating the answer to any problem that can be specified precisely, just like the page-crawling Turing machine in Chapter 3 that could deduce that Socrates is mortal. That is because toy neurons can be wired together in a few simple ways that turn them into “logic gates,” devices that can compute the logical relations “and,” “or,” and “not” that underlie deduction. The meaning of the logical relation “and” is that the statement “A and B” is true if A is true and if B is true. An AND gate that computes that relation would be one that turns itself on if all of its inputs are on.


pages: 523 words: 143,139

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

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

4chan, Ada Lovelace, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, algorithmic trading, anthropic principle, asset allocation, autonomous vehicles, Berlin Wall, Bill Duvall, bitcoin, Community Supported Agriculture, complexity theory, constrained optimization, cosmological principle, cryptocurrency, Danny Hillis, delayed gratification, dematerialisation, diversification, double helix, Elon Musk, fault tolerance, Fellow of the Royal Society, Firefox, first-price auction, Flash crash, Frederick Winslow Taylor, George Akerlof, global supply chain, Google Chrome, Henri Poincaré, information retrieval, Internet Archive, Jeff Bezos, John Nash: game theory, John von Neumann, knapsack problem, Lao Tzu, linear programming, martingale, Nash equilibrium, natural language processing, NP-complete, P = NP, packet switching, prediction markets, race to the bottom, RAND corporation, RFC: Request For Comment, Robert X Cringely, sealed-bid auction, second-price auction, self-driving car, Silicon Valley, Skype, sorting algorithm, spectrum auction, Steve Jobs, stochastic process, Thomas Malthus, traveling salesman, Turing machine, urban planning, Vickrey auction, Walter Mischel, Y Combinator

See, for example, Russell and Wefald, Do the Right Thing, and Horvitz and Zilberstein, “Computational Tradeoffs Under Bounded Resources.” Tom and his colleagues have used this approach to develop models of human cognition; see Griffiths, Lieder, and Goodman, “Rational Use of Cognitive Resources.” analogy to a human mathematician: In section 9 of Turing, “On Computable Numbers,” Turing justifies the choices made in defining what we now call a Turing machine by comparing them to operations that a person might carry out: a two-dimensional piece of paper becomes a one-dimensional tape, the person’s state of mind becomes the state of the machine, and symbols are written and read as the person or machine moves around on the paper. Computation is what a computer does, and at the time the only “computers” were people. we are irrational and error-prone: For example, see Gilovich, How We Know What Isn’t So; Ariely and Jones, Predictably Irrational; and Marcus, Kluge. 1.

man vs. nature: Appropriately, schoolchildren in the twenty-first century increasingly learn about “person vs. nature,” “person vs. self,” “person vs. person,” and “person vs. society.” “a clever man would put the poison into his own goblet”: The Princess Bride, screenplay by William Goldman; 20th Century Fox, 1987. “anticipating the anticipations of others”: Attributed to Keynes in Gregory Bergman, Isms, Adams Media, 2006. it was the halting problem that inspired Turing: Alan Turing considers the halting problem and proposes the Turing machine in “On Computable Numbers, with an Application to the Entscheidungsproblem” and “On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction.” “poker players call it ‘leveling’”: Dan Smith, personal interview, September 11, 2014. “You don’t have deuce–seven”: This took place at the “Full Tilt Poker Durrrr Million Dollar Challenge,” held at Les Ambassadeurs Club in London, November 17–19, 2009, and was televised on Sky Sports.

See also Transmission Control Protocol (TCP) teaching to the test technical investors telegraph telephone temperature temporal locality Tenenbaum, Josh tennis tournaments Texas Hold ’Em text messages “TeX Tuneup of 2012, The” (Knuth) Thanksgiving commerce theft, irrational responses and Things a Computer Scientist Rarely Talks About (Knuth) 37% rule Thoreau, Henry David thrashing threading Three Princes of Serendip, The Threshold Rule throughput Tibshirani, Robert Tikhonov, Andrey time interval of timeboxing time costs time management time-space tradeoffs Tolins, Jackson Tomlinson, Ray town size distributions Toxoplasma gondii traffic tragedy of the commons training scars transit systems Transmission Control Protocol (TCP) ACKs and backchannels and flow control and price of anarchy and traveling salesman problem Treat, Tyler “Treatise on the Probability of the Causes of Events” (Laplace) Tree, Jean Fox Trick, Michael triple handshake triple-or-nothing game trip planning. See also traveling salesman problem Turing, Alan Turing machine turn-taking Tuskegee Syphilis Study Tversky, Amos Twain, Mark twin primes Twitter two-factor models two-machine scheduling UC Berkeley Ulam, Stanislaw “Stan” Ullman, Ellen uncertainty Unilever “Unreasonable Effectiveness of Data, The” (Norvig) “up or out” system Upper Confidence Bound urban planners US Armed Forces US Census US House of Representatives US Public Health Service U-turns vacation email and itinerary of policy on vaccination Vail, Alfred valet stand veil of ignorance verification, gap between search and Vickrey, William Vickrey auction Vita Coco voicemail voice transmission, Internet Voltaire Von Neumann, John Wagenmakers, E.


pages: 294 words: 81,292

Our Final Invention: Artificial Intelligence and the End of the Human Era by James Barrat

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

3D printing, AI winter, Amazon Web Services, artificial general intelligence, Automated Insights, Bernie Madoff, Bill Joy: nanobots, brain emulation, cellular automata, cloud computing, cognitive bias, computer vision, cuban missile crisis, Daniel Kahneman / Amos Tversky, Danny Hillis, data acquisition, don't be evil, Extropian, finite state, Flash crash, friendly AI, friendly fire, Google Glasses, Google X / Alphabet X, Isaac Newton, Jaron Lanier, John von Neumann, Kevin Kelly, Law of Accelerating Returns, life extension, Loebner Prize, lone genius, mutually assured destruction, natural language processing, Nicholas Carr, optical character recognition, PageRank, pattern recognition, Peter Thiel, prisoner's dilemma, Ray Kurzweil, Rodney Brooks, Search for Extraterrestrial Intelligence, self-driving car, semantic web, Silicon Valley, Singularitarianism, Skype, smart grid, speech recognition, statistical model, stealth mode startup, stem cell, Stephen Hawking, Steve Jobs, Steve Wozniak, strong AI, Stuxnet, superintelligent machines, technological singularity, The Coming Technological Singularity, traveling salesman, Turing machine, Turing test, Vernor Vinge, Watson beat the top human players on Jeopardy!, zero day

Fortunately Bletchley Park had a secret weapon of its own—Alan Turing. Before the war, Turing had studied mathematics and encryption at Cambridge and Princeton. He had imagined an “automatic machine,” now known as a Turing machine. The automatic machine laid out the basic principles of computation itself. The Church-Turing hypothesis, which combined Turing’s work with that of his Princeton professor, mathematician Alonso Church, really puts the starch in the pants of the study of artificial intelligence. It proposes that anything that can be computed by an algorithm, or program, can be computed by a Turing machine. Therefore, if brain processes can be expressed as a series of instructions—an algorithm—then a computer can process information the same way. In other words, unless there’s something mystical or magical about human thinking, intelligence can be achieved by a computer.

Searle, John self-awareness Self-Aware Systems self-improvement self-preservation September 11 attacks serial processing SETI (Search for Extraterrestrial Intelligence) Shostak, Seth Silicon Valley Singularitarians Singularity definitions of Kurzweil and technological Singularity Is Near, The (Kurzweil) Singularity Summit Singularity University Sir Groovy Siri 60 Minutes Skilling, Jeffrey Smart Action smart phones see also iPhone software complexity of malware see also programming solar energy space exploration “Speculations Concerning the First Ultraintelligent Machine” (Good) speech recognition SRI International stealth companies Sterrit, Roy Stibel, Jeff Stuxnet subprime mortgage crisis Symantec SyNAPSE Technological Risk (Lewis) technology journalism Terminator movies terrorism 9/11 attacks Thiel, Peter Thinking Machines, Inc. Three Mile Island tightly coupled systems Thrun, Sebastian transhumans transistors Traveller Trillion Credit Squadron Turing, Alan Turing machine Turing test Tversky, Amos two-minute problem 2001: A Space Odyssey Ulam, Stanislaw utility function Vassar, Michael Vicarious Systems Vinge, Vernor violence Virginia Tech Massacre Virtually You (Aboujaoude) voice recognition von Neumann, John Voss, Peter Wallach, Wendall Wall Street Warwick, Kevin Washington Post Watson weapons, see military Whitby, Blay “Why the Future Doesn’t Need Us” (Joy) Wired for Thought (Stibel) Wissner-Gross, Alexander D.


pages: 893 words: 199,542

Structure and interpretation of computer programs by Harold Abelson, Gerald Jay Sussman, Julie Sussman

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

Andrew Wiles, conceptual framework, Douglas Hofstadter, Eratosthenes, Fermat's Last Theorem, Gödel, Escher, Bach, industrial robot, information retrieval, iterative process, loose coupling, probability theory / Blaise Pascal / Pierre de Fermat, Richard Stallman, Turing machine

This was first demonstrated in a clear way by Alan M. Turing (1912-1954), whose 1936 paper laid the foundations for theoretical computer science. In the paper, Turing presented a simple computational model – now known as a Turing machine – and argued that any “effective process” can be formulated as a program for such a machine. (This argument is known as the Church-Turing thesis.) Turing then implemented a universal machine, i.e., a Turing machine that behaves as an evaluator for Turing-machine programs. He used this framework to demonstrate that there are well-posed problems that cannot be computed by Turing machines (see exercise 4.15), and so by implication cannot be formulated as “effective processes.” Turing went on to make fundamental contributions to practical computer science as well. For example, he invented the idea of structuring programs using general-purpose subroutines.

Solver tower of types tracing instruction execution register assignment transform-painter transparency, referential transpose a matrix tree B-tree binary, see also binary tree combination viewed as counting leaves of enumerating leaves of fringe of Huffman lazy mapping over red-black represented as pairs reversing at all levels tree accumulation tree->list... tree-map tree-recursive process order of growth trigonometric relations true true true? truncation error truth maintenance try-again Turing machine Turing, Alan M., [2] Turner, David, [2], [3] type field type tag, [2] two-level type(s) cross-type operations dispatching on hierarchy in symbolic algebra hierarchy of lowering, [2] multiple subtype and supertype raising, [2] subtype supertype tower of type-inferencing mechanism type-tag using Scheme data types typed pointer typing input expressions unbound variable unev register unification discovery of algorithm implementation pattern matching vs., [2] unify-match union-set binary-tree representation ordered-list representation unordered-list representation unique (query language) unique-pairs unit square univariate polynomial universal machine explicit-control evaluator as general-purpose computer as University of California at Berkeley University of Edinburgh University of Marseille UNIX, [2] unknown-expression-type unknown-procedure-type unordered-list representation of sets unspecified values define display if without alternative newline set!


pages: 1,387 words: 202,295

Structure and Interpretation of Computer Programs, Second Edition by Harold Abelson, Gerald Jay Sussman, Julie Sussman

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

Andrew Wiles, conceptual framework, Douglas Hofstadter, Eratosthenes, Gödel, Escher, Bach, industrial robot, information retrieval, iterative process, loose coupling, probability theory / Blaise Pascal / Pierre de Fermat, Richard Stallman, Turing machine, wikimedia commons

This was first demonstrated in a clear way by Alan M. Turing (1912-1954), whose 1936 paper laid the foundations for theoretical computer science. In the paper, Turing presented a simple computational model—now known as a Turing machine—and argued that any “effective process” can be formulated as a program for such a machine. (This argument is known as the Church-Turing thesis.) Turing then implemented a universal machine, i.e., a Turing machine that behaves as an evaluator for Turing-machine programs. He used this framework to demonstrate that there are well-posed problems that cannot be computed by Turing machines (see Exercise 4.15), and so by implication cannot be formulated as “effective processes.” Turing went on to make fundamental contributions to practical computer science as well. For example, he invented the idea of structuring programs using general-purpose subroutines.

Knuth, Fundamental Algorithms (Volume 1 of The Art of Computer Programming) Jump to: A B C D E F G H I K L M N O P Q R S T U V W Z Index Entry Section A abstract models: 2.1.3 abstract syntax: 4.1.1 abstraction barriers: Chapter 2 abstraction barriers: 2.1.2 accumulator: 2.2.3 accumulator: 3.1.1 acquired: 3.4.2 action: 5.1.1 additive: 2.4.3 additively: Chapter 2 additively: 2.4 address: 5.3.1 address arithmetic: 5.3.1 agenda: 3.3.4 algebraic specification: 2.1.3 aliasing: 3.1.3 and-gate: 3.3.4 applicative-order: 4.2.1 applicative-order evaluation: 1.1.5 arbiter: 3.4.2 arguments: 1.1.1 assembler: 5.2.1 assertions: 4.4.1 assignment operator: 3.1 atomically: 3.4.2 automatic storage allocation: 5.3 average damping: 1.3.3 B B-trees: 2.3.3 backbone: 3.3.3 backquote: 5.5.2 backtracks: 4.3.1 balanced: 2.2.2 barrier synchronization: 3.4.2 base address: 5.3.1 Bertrand’s hypothesis: 3.5.2 bignum: 5.3.1 bindings: 3.2 binds: 1.1.8 binomial coefficients: 1.2.2 block structure: 1.1.8 bound variable: 1.1.8 box-and-pointer notation: 2.2 breakpoint: 5.2.4 broken heart: 5.3.2 bugs: Chapter 1 C cache-coherence: 3.4.1 call-by-name: 3.5.1 call-by-name: 4.2.2 call-by-name thunks: 3.5.1 call-by-need: 3.5.1 call-by-need: 4.2.2 call-by-need thunks: 3.5.1 capturing: 1.1.8 Carmichael numbers: 1.2.6 case analysis: 1.1.6 cell: 3.4.2 chronological backtracking: 4.3.1 Church numerals: 2.1.3 Church-Turing thesis: 4.1.5 clauses: 1.1.6 closed world assumption: 4.4.3 closure: Chapter 2 closure property: 2.2 code generator: 5.5.1 coerce: 2.5.2 coercion: 2.5.2 combinations: 1.1.1 comments: 2.2.3 compacting: 5.3.2 compilation: 5.5 compile-time environment: 5.5.6 composition: 1.3.4 compound data: Chapter 2 compound data object: Chapter 2 compound procedure: 1.1.4 computability: 4.1.5 computational process: Chapter 1 concurrently: 3.4 congruent modulo: 1.2.6 connectors: 3.3.5 consequent expression: 1.1.6 constraint networks: 3.3.5 constructors: 2.1 continuation procedures: 4.3.3 continued fraction: 1.3.3 control structure: 4.4.3 controller: 5.1 conventional interfaces: Chapter 2 conventional interfaces: 2.2.3 current time: 3.3.4 D data: Chapter 1 data: 2.1.3 data abstraction: Chapter 2 data abstraction: 2.1 data paths: 5.1 data-directed: 2.4 data-directed programming: Chapter 2 data-directed programming: 2.4.3 deadlock: 3.4.2 deadlock-recovery: 3.4.2 debug: Chapter 1 deep binding: 4.1.3 deferred operations: 1.2.1 delayed argument: 3.5.4 delayed evaluation: Chapter 3 delayed evaluation: 3.5 delayed object: 3.5.1 dense: 2.5.3 dependency-directed backtracking: 4.3.1 depth-first search: 4.3.1 deque: 3.3.2 derived expressions: 4.1.2 digital signals: 3.3.4 dispatching on type: 2.4.3 displacement number: 5.5.6 dotted-tail notation: 2.2.1 driver loop: 4.1.4 E empty list: 2.2.1 encapsulated: 3.1.1 enclosing environment: 3.2 entry points: 5.1.1 enumerator: 2.2.3 environment: 1.1.2 environment model: Chapter 3 environments: 3.2 Euclid’s Algorithm: 1.2.5 Euclidean ring: 2.5.3 evaluating: 1.1.1 evaluator: Chapter 4 event-driven simulation: 3.3.4 evlis tail recursion: 5.4.1 execution procedure: 4.1.7 explicit-control evaluator: 5.4 expression: 1.1.1 F failure continuation: 4.3.3 FIFO: 3.3.2 filter: 1.3.1 filter: 2.2.3 first-class: 1.3.4 fixed point: 1.3.3 fixed-length: 2.3.4 forcing: 4.2.2 forwarding address: 5.3.2 frame: 4.4.2 frame coordinate map: 2.2.4 frame number: 5.5.6 framed-stack: 5.4.1 frames: 3.2 free: 1.1.8 free list: 5.3.1 front: 3.3.2 full-adder: 3.3.4 function boxes: 3.3.4 functional programming: 3.1.3 functional programming languages: 3.5.5 G garbage: 5.3.2 garbage collection: 5.3 garbage collection: 5.3.2 garbage collector: 3.3.1 garbage-collected: 4.2.2 generic operations: Chapter 2 generic procedures: 2.3.4 generic procedures: 2.4 glitches: Chapter 1 global: 1.2 global: 3.2 global environment: 1.1.2 golden ratio: 1.2.2 grammar: 4.3.2 H half-adder: 3.3.4 half-interval method: 1.3.3 Halting Theorem: 4.1.5 headed list: 3.3.3 hiding principle: 3.1.1 hierarchical: 2.2 hierarchy of types: 2.5.2 higher-order procedures: 1.3 Horner’s rule: 2.2.3 I imperative programming: 3.1.3 indeterminates: 2.5.3 index: 5.3.1 indexing: 4.4.2 instantiated with: 4.4.1 instruction counting: 5.2.4 instruction execution procedure: 5.2.1 instruction sequence: 5.5.1 instruction tracing: 5.2.4 instructions: Chapter 5 instructions: 5.1.1 integerizing factor: 2.5.3 integers: 1.1 integrator: 3.5.3 interning: 5.3.1 interpreter: Chapter 1 interpreter: Chapter 4 invariant quantity: 1.2.4 inverter: 3.3.4 iterative improvement: 1.3.4 iterative process: 1.2.1 K k-term: 1.3.3 key: 2.3.3 L labels: 5.1.1 lazy evaluation: 4.2.1 lexical address: 5.5.6 lexical addressing: 4.1.3 lexical scoping: 1.1.8 linear iterative process: 1.2.1 linear recursive process: 1.2.1 linkage descriptor: 5.5.1 list: 2.2.1 list: 2.2.1 list: 2.2.1 list structure: 2.2.1 list-structured: 2.1.1 list-structured memory: 5.3 local evolution: 1.2 local state variables: 3.1 location: 5.3.1 logic-programming: Chapter 4 logical and: 3.3.4 logical deductions: 4.4.1 logical or: 3.3.4 M machine language: 5.5 macro: 4.1.2 map: 2.2.3 mark-sweep: 5.3.2 memoization: 1.2.2 Memoization: 3.3.3 memoize: 4.2.2 merge: 3.5.5 message passing: 2.1.3 message passing: 2.4.3 message-passing: 3.1.1 metacircular: 4.1 Metalinguistic abstraction: Chapter 4 Miller-Rabin test: 1.2.6 modular: Chapter 3 modulo: 1.2.6 modulo: 1.2.6 modus ponens: 4.4.3 moments in time: 3.4 Monte Carlo integration: 3.1.2 Monte Carlo simulation: 3.1.2 mutable data objects: 3.3 mutators: 3.3 mutex: 3.4.2 mutual exclusion: 3.4.2 N n-fold smoothed function: 1.3.4 native language: 5.5 needed: 5.5.1 networks: Chapter 4 Newton’s method: 1.3.4 nil: 2.2.1 non-computable: 4.1.5 non-strict: 4.2.1 nondeterministic: 3.4.1 nondeterministic choice point: 4.3.1 nondeterministic computing: Chapter 4 nondeterministic computing: 4.3 normal-order: 4.2.1 normal-order evaluation: 1.1.5 normal-order evaluation: Chapter 4 O obarray: 5.3.1 object program: 5.5 objects: Chapter 3 open-code: 5.5.5 operands: 1.1.1 operator: 1.1.1 operator: 4.1.6 or-gate: 3.3.4 order of growth: 1.2.3 ordinary: 2.5.1 output prompt: 4.1.4 P package: 2.4.3 painter: 2.2.4 pair: 2.1.1 pair: 2.1.1 parse: 4.3.2 Pascal’s triangle: 1.2.2 pattern: 4.4.1 pattern matcher: 4.4.2 pattern matching: 4.4.2 pattern variable: 4.4.1 pipelining: 3.4 pointer: 2.2 poly: 2.5.3 power series: 3.5.2 predicate: 1.1.6 predicate: 1.1.6 prefix: 2.3.4 prefix code: 2.3.4 prefix notation: 1.1.1 pretty-printing: 1.1.1 primitive constraints: 3.3.5 probabilistic algorithms: 1.2.6 procedural abstraction: 1.1.8 procedural epistemology: Preface 1e procedure: 1.2.1 procedure definitions: 1.1.4 procedures: Chapter 1 process: 1.2.1 program: Chapter 1 programming languages: Chapter 1 prompt: 4.1.4 pseudo-random: 3.1.2 pseudodivision: 2.5.3 pseudoremainder: 2.5.3 Q quasiquote: 5.5.2 queries: 4.4 query language: 4.4 queue: 3.3.2 quote: 2.3.1 R Ramanujan numbers: 3.5.3 rational functions: 2.5.3 RC circuit: 3.5.3 read-eval-print loop: 1.1.1 reader macro characters: 4.4.4.7 real numbers: 1.1 rear: 3.3.2 recursion equations: Chapter 1 Recursion theory: 4.1.5 recursive: 1.1.3 recursive: 1.1.8 recursive process: 1.2.1 red-black trees: 2.3.3 referentially transparent: 3.1.3 register machine: Chapter 5 register table: 5.2.1 registers: Chapter 5 released: 3.4.2 remainder of: 1.2.6 resolution principle: 4.4 ripple-carry adder: 3.3.4 robust: 2.2.4 RSA algorithm: 1.2.6 rules: 4.4 rules: 4.4.1 S satisfy: 4.4.1 scope: 1.1.8 selectors: 2.1 semaphore: 3.4.2 separator code: 2.3.4 sequence: 2.2.1 sequence accelerator: 3.5.3 sequences: 1.3.1 serializer: 3.4.2 serializers: 3.4.2 series RLC circuit: 3.5.4 shadow: 3.2 shared: 3.3.1 side-effect bugs: 3.1.3 sieve of Eratosthenes: 3.5.2 smoothing: 1.3.4 source language: 5.5 source program: 5.5 sparse: 2.5.3 special forms: 1.1.3 stack: 1.2.1 stack: 5.1.4 state variables: 1.2.1 state variables: 3.1 statements: 5.5.1 stop-and-copy: 5.3.2 stratified design: 2.2.4 stream processing: 1.1.5 streams: Chapter 3 streams: 3.5 streams: 3.5 strict: 4.2.1 subroutine: 5.1.3 substitution: 1.1.5 substitution model: 1.1.5 subtype: 2.5.2 success continuation: 4.3.3 summation of a series: 1.3.1 summer: 3.5.3 supertype: 2.5.2 symbolic expressions: Chapter 2 syntactic sugar: 1.1.3 syntax: 4.1 systematically search: 4.3.1 systems: Chapter 4 T tableau: 3.5.3 tabulation: 1.2.2 tabulation: 3.3.3 tagged architectures: 5.3.1 tail-recursive: 1.2.1 tail-recursive: 5.4.2 target: 5.5.1 thrashing: UTF thunk: 4.2.2 thunks: 4.2.2 time: 3.4 time segments: 3.3.4 tower: 2.5.2 tree accumulation: 1.1.3 tree recursion: 1.2.2 trees: 2.2.2 truth maintenance: 4.3.1 Turing machine: 4.1.5 type field: 5.3.1 type tag: 2.4.2 type tags: 2.4 type-inferencing: 3.5.4 typed pointers: 5.3.1 U unbound: 3.2 unification: 4.4 unification: 4.4.2 unification: 4.4.2 unification algorithm: 4.4 univariate polynomials: 2.5.3 universal machine: 4.1.5 upward-compatible extension: 4.2.2 V value: 1.1.2 value of a variable: 3.2 values: 2.3.1 variable: 1.1.2 variable-length: 2.3.4 vector: 5.3.1 W width: 2.1.4 wires: 3.3.4 wishful thinking: 2.1.1 Z zero crossings: 3.5.3 Jump to: A B C D E F G H I K L M N O P Q R S T U V W Z Next: Colophon, Prev: Figures, Up: Top [Contents] Prev: Term Index, Up: Top [Contents] Colophon On the cover page is Agostino Ramelli’s bookwheel mechanism from 1588.


pages: 250 words: 73,574

Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers by John MacCormick, Chris Bishop

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

Ada Lovelace, AltaVista, Claude Shannon: information theory, fault tolerance, information retrieval, Menlo Park, PageRank, pattern recognition, Richard Feynman, Richard Feynman, Silicon Valley, Simon Singh, sorting algorithm, speech recognition, Stephen Hawking, Steve Jobs, Steve Wozniak, traveling salesman, Turing machine, Turing test, Vannevar Bush

But to assist his argument, Turing describes a particular type of machine (for Turing, a “machine” is what we would call a “computer” today) that can also do calculations. Part of the paper is devoted to demonstrating that certain calculations cannot be performed by these machines—this is the proof of undecidability, which we have discussed in detail already. But another part of the same paper makes a detailed and compelling argument that Turing's “machine” (read: computer) can perform any calculation done by a “computer” (read: human). You may be beginning to appreciate why it is difficult to overstate the seminal nature of Turing's “On computable numbers.” paper. It not only defines and solves some of the most fundamental problems in computer science, but also strikes out into the heart of a philosophical minefield, making a persuasive case that human thought processes could be emulated by computers (which, remember, had not been invented yet!).

See database, table; virtual table tag Tale of Two Cities, A target value Taylor, A. J. P. TCP telegraph telephone. See phone terminate theology Thompson, Thomas M. threshold; soft title: of this book; of a web page to-do list to-do list trick Tom Sawyer training. See also learning training data transaction: abort; atomic; in a database; on the internet; rollback travel agent Traveling Salesman Problem trick, definition of TroubleMaker.exe Turing, Alan Turing machine Turing test TV Twain, Mark twenty questions, game of twenty-questions trick two-dimensional parity. See parity two-phase commit U.S. Civil War Ullman, Jeffrey D. uncomputable. See also undecidable undecidable. See also uncomputable undefined unicycle universe unlabeled Vazirani, Umesh verification Verisign video video game virtual table virtual table trick Waters, Alice web.


pages: 230

Purely Functional Data Structures by Chris Okasaki

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

reversible computing, Turing machine, type inference

It has since been used in many situations, including real-time queues [HM81], realtime deques [Hoo82, GT86, Sar86, CG93], catenable deques [BT95], and the order maintenance problem [DS87]. Deques Hood [Hoo82] first modified the real-time queues of [HM81] to obtain real-time deques based on global rebuilding. Several other researchers later duplicated this work [GT86, Sar86, CG93]. These implementations are all similar to techniques used to simulate multihead Turing machines [Sto70, FMR72, LS81]. Hoogerwoord [Hoo92] proposed amortized deques based on batched rebuilding, but, as always with batched rebuilding, his implementation is not efficient when used persistently. The real-time deques in Figure 8.4 first appeared in [Oka95c]. Coroutines and Lazy Evaluation Streams (and other lazy data structures) have frequently been used to implement a form of coroutining between the producer of a stream and the consumer of a stream.

Information Processing Letters, 14(5):205-206, July 1982. (p. 55) T. W. Butler. Computer response time and user performance. In Conference on Human Factors in Computing Systems, pages 5862, December 1983. (p. 83) Richard S. Bird and Philip Wadler. Introduction to Functional Programming. Prentice Hall International, 1988. (p. 29) Tyng-Ruey Chuang and Benjamin Goldberg. Real-time deques, multihead Turing machines, and purely functional programming. In Conference on Functional Programming Languages and Computer Architecture, pages 289-298, June 1993. (pp. 109,113) Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to algorithms. MIT Press, 1990. (p. 27) Richard H. Connelly and F. Lockwood Morris. A generalization of the trie data structure. Mathematical Structures in Computer Science, 5(3):381-418, September 1995.


pages: 239 words: 64,812

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

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

Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Apple II, barriers to entry, Berlin Wall, British Empire, business process, conceptual framework, create, read, update, delete, crowdsourcing, East Village, European colonialism, finite state, Firefox, Flash crash, glass ceiling, Grace Hopper, haute couture, iterative process, Jaron Lanier, John von Neumann, land reform, London Whale, Paul Graham, pink-collar, revision control, Silicon Valley, Silicon Valley ideology, Skype, Steve Jobs, Steve Wozniak, theory of mind, Therac-25, Turing machine, wikimedia commons, women in the workforce

As later grammarians put it, we are lakṣaṇaikacakṣuṣka, solely guided by rules. Correctness is guaranteed by the correct application of rules.13 The systematic, deterministic workings of these rules may remind you of the orderly on-and-off workings of logic gates. The Ashtadhyayi is, of course, an algorithm, a machine that consumes phonemes and morphemes and produces words and sentences. Panini’s machine—which is sometimes compared to the Turing machine—is also the first known instance of the application of algorithmic thinking to a domain outside of logic and mathematics. The influence of the Ashtadhyayi was and remains immense. In the Sanskrit ecumene, later grammarians suggested some additions and modifications, and other grammars were written before and after Panini’s intervention, but all have been overshadowed by this one “tersest and yet most complete grammar of any language.”14 The West discovered the Ashtadhyayi during the great flowering of Orientalist research and translation in the eighteenth and nineteenth centuries.

Ada, the Enchantress of Numbers: Poetical Science. Sausalito: Critical Connection, 2010. Kindle Edition. Torvalds, Linus. “Re: Stable Linux 2.6.25.10.” Gmane.org, July 15, 2008. http://article.gmane.org/gmane.linux.kernel/706950. Turing, Alan. “On Computable Numbers, with an Application to the Entscheidungs-problem (1936).” In The Annotated Turing: A Guided Tour through Alan Turing’s Historic Paper on Computability and the Turing Machine, by Charles Petzold. Indianapolis: Wiley, 2008. Urban, Hugh B. The Economics of Ecstasy: Tantra, Secrecy, and Power in Colonial Bengal. New York: Oxford University Press, 2001. ______. The Power of Tantra: Religion, Sexuality and the Politics of South Asian Studies. London: IB Tauris, 2009. Kindle edition. Varma, Roli. “Computing Self-Efficacy among Women in India.” Journal of Women and Minorities in Science and Engineering 16, no. 3 (2010): 257–74. ______.

Wireless by Stross, Charles

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

anthropic principle, back-to-the-land, Benoit Mandelbrot, Buckminster Fuller, Cepheid variable, cognitive dissonance, colonial exploitation, cosmic microwave background, epigenetics, finite state, Georg Cantor, gravity well, hive mind, jitney, Khyber Pass, Magellanic Cloud, mandelbrot fractal, peak oil, phenotype, Pluto: dwarf planet, security theater, sensible shoes, Turing machine

” “What’s thinking got to do with—” I stop. It’s useless pretending. “Fuck. 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?” “Back channels,” Cantor says cryptically. “Alan, be a good lad and try to jam the door for a minute, will you?

“You’re a theoretical research cell, aren’t you?” “We prefer to call ourselves a think tank.” Cantor nods gravely. “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. Which makes you too bright for your own good. Listen to me: just try to convince yourself that we’re playing chess, and Matron will let you out of here.”


pages: 1,280 words: 384,105

The Mammoth Book of the Best of Best New SF by Gardner Dozois

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

back-to-the-land, Buckminster Fuller, Burning Man, call centre, Columbine, congestion charging, dark matter, Doomsday Book, double helix, Extropian, gravity well, Mason jar, offshore financial centre, out of africa, pattern recognition, phenotype, Silicon Valley, slashdot, Stephen Hawking, telepresence, Turing machine, Turing test, Winter of Discontent, Y2K

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. “Are you telling me only one tile changes between any two rows, where the ‘machine’ leaves its mark on the ‘data tape’ . . . ?” The mosaics he’d seen were a riot of complexity, with no two rows remotely the same. Karpal said, “No, no. Wang’s original example worked exactly like a standard Turing Machine, to simplify the argument . . . but the carpets are more like an arbitrary number of different computers with overlapping data, all working in parallel.

He said, “Hao Wang proved a powerful theorem, twenty-three hundred years ago. Think of a row of Wang Tiles as being like the data tape of a Turing Machine.” Paolo had the library grant him knowledge of the term; it was the original conceptual form of a generalized computing device, an imaginary machine which moved back and forth along a limitless one-dimensional data tape, reading and writing symbols according to a given set of rules. “With the right set of tiles, to force the right pattern, the next row of the tiling will look like the data tape after the Turing Machine has performed one step of its computation. And the row after that will be the data tape after two steps, and so on. For any given Turing Machine, there’s a set of Wang Tiles which can imitate it.” Paolo nodded amiably. He hadn’t heard of this particular quaint result, but it was hardly surprising.


pages: 561 words: 167,631

2312 by Kim Stanley Robinson

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

agricultural Revolution, double helix, full employment, hive mind, if you see hoof prints, think horses—not zebras, Kuiper Belt, late capitalism, mutually assured destruction, offshore financial centre, pattern recognition, phenotype, post scarcity, precariat, retrograde motion, stem cell, strong AI, the built environment, the High Line, Turing machine, Turing test, Winter of Discontent

Titan, by far the largest Saturnian moon, is bigger than Mercury or Pluto. More about Titan later. Extracts (9) One question for computability: is the problem capable of producing a result If a finite number of steps will produce an answer, it is a problem that can be solved by a Turing machine Is the universe itself the equivalent of a Turing machine? This is not yet clear Turing machines can’t always tell when the result has been obtained. No oracle machine is capable of solving its own halting problem A Turing jump operator assigns to each problem X a successively harder problem, X prime. Setting a Turing machine the problem of making its own Turing jump creates a recursive effect called the Ouroboros All problems solvable by quantum computers are also solvable by classical computers. Making use of quantum mechanical phenomena only increases speed of operation two popular physical mechanisms, dots and liquids.


pages: 353 words: 101,130

Schild's Ladder by Greg Egan

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

framing effect, gravity well, invisible hand, Turing machine

That's very nearly what Sophus is claiming lies behind the border: an enormous quantum computer that could perform any operation that falls under the general description of quantum physics--and in fact is in a superposition of states in which it's doing all of them." Mariama's eyes widened, but then she protested, "Sophus never puts it like that." "No, of course not," Yann agreed. "He's much too careful to use overheated language like that. 'The universe is a Deutsch-Bennett-Turing machine's is not a statement that goes down well with most physicists, since it has no empirically falsifiable content." He smiled mischievously. "It does remind me of something, though. If you ever want a good laugh, you should try some of the pre-Qusp anti-AI propaganda. I once read a glorious tract which asserted that as soon as there was intelligence without bodies, its 'unstoppable lust for processing power' would drive it to convert the whole Earth, and then the whole universe, into a perfectly efficient Planck-scale computer.

A quantum computer can simulate any quantum process; that's old news. It doesn't mean that there is a quantum computer underlying anything." "No," Tchicaya agreed. "But qubit network theory doesn't claim that. It just says that when you get to a low enough level, you have nothing left to lose by treating the system as if it were software. It's like all the proofs in applied algorithmic theory that are based on imagining Turing machines. No one complains that the real universe is conspicuously devoid of paper tape." "Old habits die hard," she confessed. "I'm still in mourning for the Sarumpaet rules, and they were disproved before I was born. They're what I was brought up on, they're what I've thought of all my life as the template for a physical theory. It's not easy adapting, even to Sophus's model." "Yeah. I really am grateful to you for trying this," Tchicaya said.


pages: 232

A Discipline of Programming by E. Dijkstra

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

finite state, Turing machine, Y Combinator

This shows quite clearly why I regard general recursion as an order of magnitude more complicated than just repetition, and it therefore hurts me to see the semantics of the repetitive construct "while B do S" defined as that of the call "whiledo(B, S)" of the recursive procedure (described in ALGOL 60 syntax): procedure whiledo (condition, statement); begin if condition then begin statement; whiledo (condition, statement) end end Although correct, it hurts me, for I don't like to crack an egg with a sledgehammer, no matter how effective the sledgehammer is for doing so. For the generation of theoretical computing scientists that became involved in the subject during the sixties, the above recursive definition is often not only "the natural one", but even "the true one". In view of the fact that we cannot even define what a Turing machine is supposed to do without appeal- ing to the notion of repetition, some redressing of the balance seemed indi- ca ted. For the absence of a bibliography I offer neither explanation nor apology. Acknowledgements. The following people have had a direct influence on this book, either by their willingness to discuss its intended contents or by com- menting on (parts of) the finished manuscript: C.

In other words, we accept an HSLM that is only able to simulate properly a subset of the computations that are guaranteed to terminate prop- erly when executed by the UM. Note 4. The notion of the liberal pre-condition is introduced here in recognition of the fact that the HSLM is so bounded. This is in sharp contrast to the very similar notion of "partial correctness", which has been introduced in connection with unbounded machines (such as Turing machines) because of the undecidability of the Halting Problem. (End of note 4.) One may raise the question -but I shall not answer it- of what the UM will do when started at an initial state for which we don't know whether it satisfies wp(S, T) or not. I take the position (from a philosophical point of view probably very shaky) that as long as we have not proved that the initial state satisfies wp(S, T), the UM may do as it likes, in the sense that we have no right to complain.


pages: 336 words: 93,672

The Future of the Brain: Essays by the World's Leading Neuroscientists by Gary Marcus, Jeremy Freeman

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

23andMe, Albert Einstein, bioinformatics, bitcoin, brain emulation, cloud computing, complexity theory, computer age, computer vision, conceptual framework, correlation does not imply causation, crowdsourcing, dark matter, data acquisition, Drosophila, epigenetics, Google Glasses, iterative process, linked data, mouse model, optical character recognition, pattern recognition, personalized medicine, phenotype, race to the bottom, Richard Feynman, Richard Feynman, Ronald Reagan, semantic web, speech recognition, stem cell, Steven Pinker, supply-chain management, Turing machine, web application

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. Active neurons rapidly assemble and disassemble into far-flung coalitions that can be tracked from the sensory periphery to motor structures.

See also Human Brain Project (HBP); SyNAPSE project (IBM); whole-brain simulation simulome, 183 Skinner’s behaviorism, 206 Sligte, Ilja, 166 Smith, Stephen, 14 Society for Neuroscience, 258 Solstad, Trygve, 75 songbirds: FOXP2 gene, 155–56 Spaun (Semantic Pointer Architecture Unified Network): architecture of model, 130f; behavior and brain model, 126–27, 129, 131–32; flexible coordination, 132–33; neural firing patterns, 129; neurons, 127; reverse engineering, 133–34; serial working memory task in, 128f, 131 speech, 140; computational neuroanatomy of, 146; FOXP2 gene mutation, 151–52, 155; information, 145; perception, 144–46; production, 146, 187, 190 spinal cord injury, 229 Sporns, Olaf, 11, 65, 90–99 standard operating procedures (SOP), 33 star-nosed mole, 187 Stensola, Hanne, 72 Stensola, Tor, 72 stimulation: electrical, 11, 79, 195, 225–26 stroke, 229, 243 style computing, 213 subjective feelings, 269 Südhof, Thomas, 207 supercomputer: human brain as, 94 supervised learning, 206 SyNAPSE project (IBM): brain simulation, 125–26 synaptic connections: brain, 50 synaptic plasticity, 119, 221, 241 synaptic proteins: in situ immune microscopy of, 60–61 synchronization: neuronal interactions, 93 syntactic theory: language computations, 143–44; minimalism, 144 syntax, 140, 141, 147–48 Talairach, Jean, 5 Talairach Atlas, 10 Tank David, 19 Taube, Jeff, 75 Technical University of Munich, 121 technological innovation, 79 Thunder, 104 Tonegawa, Susumu, 259 top-down modeling, 85f, 112, 162, 171f, 267 touch receptors, 67 Tournoux, P., 5 transcranial magnetic stimulation (TMS), 228 transcriptome, 48 transducer, 246, 250 transistor, 82, 84, 85f, 86–88, 135, 177, 181, 183, 210, 221, 245, 250 traumatic brain injury, 194, 266 trilevel hypothesis: brain, 84–85 Tsuchiya, Nao, 168, 169 tuberculosis, 171 tuberous sclerosis, 241 tumors, 266 Turing machine, 26 23andMe, 198 Twitter, 103 two-photon imaging: mouse cortex, 107 two-photon microscopy, 32 two-photon tomography, 34 ulcerative colitis, 234 ultrasonic frequencies, 246 ultrasonic waves, 249 ultrasound, 250 Universidad Politécnica de Madrid, 116 University College London, 122, 177 University of California–San Diego, 177 University of Edinburgh, 115 University of Oslo, 115, 116 US BRAIN Initiative, 113, 124 US Human Connectome Project, 113 Vallortigara, Giorgio, 207 Vandenbroucke, Annelinde, 166 Van Essen, David, 12 variable binding: brain, 213–14; language, 212 Venter, Craig, 256 Vesalius, Andreas, 3, 4f vestibular system, 22 virtual brains: building, 97–99 virtual reality: whole brain neuroimaging and, 17–24 vision: restoration, 227, 230 Vision (Marr), 181 visual processing: stimuli, 163 visual responses: brute-force data collection, 105 visual-spatial extinction, 163–64 visual system: primates, 104–5 visual thalamus, 264 Vogt, Karl, 91 Vogt, Marthe, 4 von Economo, Constantin, 4 von Neumann, John, 208, 212–13 V2 neurons: hypothesis, 105–6 Waddington, Conrad, 189 Watson, James, 7, 46 Waxholm Space, 115 Werbos, Paul, 41 White, John, 12 whole-brain neuroimaging, 20–21, 17–24 whole-brain neuroscience: behavior as brain output, 121–22; building the brain, 118–19; ethics, 123; global collaboration, 123–24; global effort to understand brain, 124; modeling brain disorders and diseases, 122; unifying brain models, 120–21; validity of model, 119–20 whole-brain simulation: creating to understand, 111–13; neuroinformatics for computing, 113–15; next generation brain atlases, 115–17; ongoing debate, 267–68; predictive neuroscience, 117–18.


pages: 387 words: 111,096

Enigma by Robert Harris

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

Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, British Empire, Columbine, index card, invention of the printing press, sensible shoes, Turing machine

But the fourth—the fourth—will be solved purely electronically, using a relay rack and valves, linked to the bombe by this fat cable form, that looks like a -' Kramer cupped his hands into a circle '—well, that looks like a cobra, I guess. Using valves in sequence—that's a revolution. Never been done before. Your people say it should make the calculations a hundred times, maybe a thousand times, as fast.' Jericho said, almost to himself: 'A Turing machine.' 'A what?' 'An electronic computer.' 'Well, whatever you want to call it. It works in theory, that's the good news. And from what they're saying, this may be just the start. It seems they're planning some kind of super-bombe, all electronic, called Colossus.' Jericho had a sudden vision of Alan Turing, one winter afternoon, sitting cross-legged in his Cambridge study while the lamps came on outside, describing his dream of a universal calculating machine.

For the twentieth time his hand went to the bulge of cryptograms in his inside pocket. Two Englands, he thought. One England—this one—familiar, safe, obvious. But now another, secret England, secluded in the grounds of stately houses -Beaumanor, Gayhurst, Woburn, Adstock, Bletchley—an England of aerial farms and direction finders, clattering bombes and, soon, the glowing green and orange valves of Turing machines ('it should make the calculations a hundred times, maybe a thousand times as fast'}. A new age beginning to be born in the parklands of the old. What was it that Hardy had written in his Apology? 'Real mathematics has no effect on war. No one has yet discovered any warlike purpose to be served by the theory of numbers.' The old boy couldn't guess the half of it. The bell tinkled again and Hester emerged from the post office holding a newspaper over her head like an umbrella.


pages: 416 words: 106,582

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

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

23andMe, Albert Einstein, Alfred Russel Wallace, banking crisis, Barry Marshall: ulcers, Benoit Mandelbrot, Berlin Wall, biofilm, Black Swan, butterfly effect, Cass Sunstein, cloud computing, congestion charging, correlation does not imply causation, Daniel Kahneman / Amos Tversky, dark matter, data acquisition, David Brooks, delayed gratification, Emanuel Derman, epigenetics, Exxon Valdez, Flash crash, Flynn Effect, hive mind, impulse control, information retrieval, Isaac Newton, Jaron Lanier, John von Neumann, Kevin Kelly, mandelbrot fractal, market design, Mars Rover, Marshall McLuhan, microbiome, Murray Gell-Mann, Nicholas Carr, open economy, place-making, placebo effect, pre–internet, QWERTY keyboard, random walk, randomized controlled trial, rent control, Richard Feynman, Richard Feynman, Richard Feynman: Challenger O-ring, Richard Thaler, Schrödinger's Cat, security theater, Silicon Valley, stem cell, Steve Jobs, Steven Pinker, Stewart Brand, the scientific method, Thorstein Veblen, Turing complete, Turing machine, Walter Mischel, Whole Earth Catalog

As you begin to form these and other concepts, the chaos on the screen gradually becomes more comprehensible. 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. Nonetheless, the structures that evolve into a Game of Life are different from those we find in the real world: Game of Life structures tend to be fragile, in the sense that changing a single cell will often cause them to dissolve.

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


pages: 518 words: 107,836

How Not to Network a Nation: The Uneasy History of the Soviet Internet (Information Policy) by Benjamin Peters

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

Albert Einstein, Andrei Shleifer, Benoit Mandelbrot, bitcoin, Brownian motion, Claude Shannon: information theory, cloud computing, cognitive dissonance, computer age, conceptual framework, crony capitalism, crowdsourcing, cuban missile crisis, Daniel Kahneman / Amos Tversky, David Graeber, Dissolution of the Soviet Union, double helix, Drosophila, Francis Fukuyama: the end of history, From Mathematics to the Technologies of Life and Death, hive mind, index card, informal economy, invisible hand, Jacquard loom, Jacquard loom, John von Neumann, Kevin Kelly, knowledge economy, knowledge worker, linear programming, mandelbrot fractal, Marshall McLuhan, means of production, Menlo Park, Mikhail Gorbachev, mutually assured destruction, Network effects, Norbert Wiener, packet switching, pattern recognition, Paul Erdős, Peter Thiel, RAND corporation, rent-seeking, road to serfdom, Ronald Coase, scientific mainstream, Steve Jobs, Stewart Brand, stochastic process, technoutopianism, The Structural Transformation of the Public Sphere, transaction costs, Turing machine

Researchers and historians of science remember his 1943 paper, coauthored with the enigmatic polymath Walter Pitts, “A Logical Calculus of the Ideas Immanent in Nervous Activity,” which proposed models for neural networks in the brain that later became influential in the theory of automata, computation, and cybernetics. Their argument holds that the mind is, given certain reductions, equivalent to a Turing machine. In other words, with sufficient abstraction, it is possible to imagine the neural network in a mind as a logical circuit that is capable of carrying out any computable problem. In McCulloch’s words, he sought “a theory in terms so general that the creations of God and men almost exemplify it.”10 That “almost” packs much into its experimental epistemology. Although the conclusion that the mind functions as a computer has since been disputed and dismissed by several generations of neuroscience and cognitive science, the basic neurophysiological insights that McCulloch brought to cybernetics animated the midcentury cybernetic scene.

The Soviet translation and adoption of cybernetics share with the other case studies glossed here an underlying fascination with the relationship of the mind to the machine, especially as seen in the biology and neurology of the British and Chilean cyberneticists. The mind-machine analog is a politically charged two-way street. Not only does cybernetics prompt us to think about how a logic machine (computer circuits or any other Turing machine) may function like a mind (a neural network), but it also raises McCulloch’s potent possibility that subsequent neuroscience has soundly rejected: the mind (neural network) might function like a logic machine (computer circuits). This reverse comparison (that a mind is like a machine) proves particularly enduring in later discussions of the design and development of national networks. The designers of major early cold war national networks in the Soviet Union, the United States, and Chile sought, implicitly or explicitly, to model their own self-governing national networks after cybernetic neural networks.


pages: 137 words: 36,231

Information: A Very Short Introduction by Luciano Floridi

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

agricultural Revolution, Albert Einstein, bioinformatics, carbon footprint, Claude Shannon: information theory, conceptual framework, double helix, Douglas Engelbart, George Akerlof, Gordon Gekko, industrial robot, Internet of things, invention of writing, John Nash: game theory, John von Neumann, moral hazard, Nash equilibrium, Norbert Wiener, phenotype, prisoner's dilemma, RAND corporation, RFID, Turing machine

These perform calculations through the interaction of continuously varying physical phenomena, such as the shadow cast by the gnomon on the dial of a sundial, the approximately regular flow of sand in an hourglass or of water in a water clock, and the mathematically constant swing of a pendulum. Clearly, it is not the use of a specific substance or reliance on a specific physical phenomenon that makes an information system analogue, but the fact that its operations are directly determined by the measurement of continuous, physical transformations of whatever solid, liquid, or gaseous matter is employed. There are analogue computers that use continuously varying voltages and a Turing machine (the logically idealized model of our personal computers) is a digital computer but may not be electrical. Given their physical nature, analogue computers operate in real time (i.e. time corresponding to time in the real world) and therefore can be used to monitor and control events as they happen, in a 1:1 relation between the time of the event and the time of computation (think of the hourglass).

The Art of Computer Programming by Donald Ervin Knuth

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

Brownian motion, complexity theory, correlation coefficient, Eratosthenes, Georg Cantor, information retrieval, Isaac Newton, iterative process, John von Neumann, Louis Pasteur, mandelbrot fractal, Menlo Park, NP-complete, P = NP, Paul Erdős, probability theory / Blaise Pascal / Pierre de Fermat, RAND corporation, random walk, sorting algorithm, Turing machine, Y2K

If it takes T(n) steps to multiply n-bit numbers, we can accomplish m-bit times n-bit multiplication by breaking the n-bit number into \n/m~\ m-bit groups, using \n/rri\T(m) + O(n + m) operations. The results cited in the text therefore give an estimated running time of O(n log m log log m) on Turing machines, or O(n log m) on machines with random access to words of bounded size, or O(n) on pointer machines. 15. The best upper bound known is O(n(lognJ log log n), due to M. J. Fischer and L. J. Stockmeyer [J. Comp. and Syst. Sci. 9 A974), 317-331]; their construction works on multitape Turing machines, and is O(n log n) on pointer machines. The best lower bound known is of order nlogn/loglogn, due to M. S. Paterson, M. J. Fischer, and A. R. Meyer [SIAM/AMS Proceedings 7 A974), 97-111]; this applies to multitape Turing machines but not to pointer machines. 16. Let 2fc be the smallest power of 2 that exceeds 2K. Set at 4— u~t ^2ut and bt «— u/2*-"*) /2, where ut = 0 for t > K.

A generalized spectral test, based on discrete Fourier transforms, can be used to test how well a sequence measures up to Definition Ql [see A. Compagner, Physical Rev. E52 A995), 5634-5645]. Still another interesting approach to a definition of randomness has been taken by Per Martin-L6f [Information and Control 9 A966), 602-619]. Given a finite 6-ary sequence Xi, ..., Xn, let l(Xi,... ,Xn) be the length of the shortest Turing machine program that generates this sequence. (Alternatively, we could use other classes of effective algorithms, such as those discussed in Section 1.1.) Then l(Xi,... ,Xn) is a measure of the "patternlessness" of 170 RANDOM NUMBERS 3.5 the sequence, and we may equate this idea with randomness. The sequences of length N that maximize l(Xi,... ,Xn) may be called random. (From the standpoint of practical random number generation by computer, this is, of course, the worst definition of "randomness" that can be imagined!)

The running time will satisfy T(n) = O(nT(logn)); hence T(n)<Cn(Clgn)(Clglgn)(Clglglgn)..., E2) where the product continues until reaching a factor with lg... lgn < 1. Schonhage and Strassen showed how to improve this theoretical upper bound to O(n log n log log n) in their paper, by using integer numbers u to carry out fast Fourier transforms on integers, modulo numbers of the form 2e + 1. This upper bound applies to Turing machines, namely to computers with bounded memory and a finite number of arbitrarily long tapes. If we allow ourselves a more powerful computer, with random access to any number of words of bounded size, Schonhage has pointed out that the upper bound drops to O(nlogn). For we can choose k = I and m = 6k, and we have time to build a complete multiplication table of all possible products xy for 0 < x,y < 2^mj/12\ (The number of such products is 2fc or 2fc+1, and we can compute each table entry by addition from one of its predecessors in O(k) steps, hence O(k2k) = 0{n) steps will suffice for the calculation.)


pages: 523 words: 148,929

Physics of the Future: How Science Will Shape Human Destiny and Our Daily Lives by the Year 2100 by Michio Kaku

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

agricultural Revolution, AI winter, Albert Einstein, augmented reality, Bill Joy: nanobots, bioinformatics, blue-collar work, British Empire, Brownian motion, cloud computing, Colonization of Mars, DARPA: Urban Challenge, delayed gratification, double helix, Douglas Hofstadter, en.wikipedia.org, friendly AI, Gödel, Escher, Bach, hydrogen economy, I think there is a world market for maybe five computers, industrial robot, invention of movable type, invention of the telescope, Isaac Newton, John von Neumann, life extension, Louis Pasteur, Mahatma Gandhi, Mars Rover, megacity, Murray Gell-Mann, new economy, oil shale / tar sands, optical character recognition, pattern recognition, planetary scale, postindustrial economy, Ray Kurzweil, refrigerator car, Richard Feynman, Richard Feynman, Rodney Brooks, Ronald Reagan, Search for Extraterrestrial Intelligence, Silicon Valley, Simon Singh, speech recognition, stem cell, Stephen Hawking, Steve Jobs, telepresence, The Wealth of Nations by Adam Smith, Thomas L Friedman, Thomas Malthus, trade route, Turing machine, uranium enrichment, Vernor Vinge, Wall-E, Walter Mischel, Whole Earth Review, X Prize

Your computer is just as dumb today as it was yesterday.) So there are at least two approaches to modeling the brain. The first, the traditional top-down approach, is to treat robots like digital computers, and program all the rules of intelligence from the very beginning. A digital computer, in turn, can be broken down into something called a Turing machine, a hypothetical device introduced by the great British mathematician Alan Turing. A Turing machine consists of three basic components: an input, a central processor that digests this data, and an output. All digital computers are based on this simple model. The goal of this approach is to have a CD-ROM that has all the rules of intelligence codified on it. By inserting this disk, the computer suddenly springs to life and becomes intelligent.


pages: 423 words: 21,637

On Lisp: Advanced Techniques for Common Lisp by Paul Graham

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

Paul Graham, sorting algorithm, Turing machine

Extensibility, bottom-up programming, interactive development, source code transformation, embedded languages--this is where Lisp shows to advantage. In principle, of course, any Turing-equivalent programming language can do the same things as any other. But that kind of power is not what programming languages are about. In principle, anything you can do with a programming language you can do with a Turing machine; in practice, programming a Turing machine is not worth the trouble. So when I say that this book is about how to do things that are impossible in other languages, I don't mean "impossible" in the mathematical sense, but in the sense that matters for programming languages. That is, if you had to write some of the programs in this book in C, you might as well do it by writing a Lisp compiler in C first. Embedding Prolog in C, for example--can you imagine the amount of work that would take?


pages: 303 words: 67,891

Advances in Artificial General Intelligence: Concepts, Architectures and Algorithms: Proceedings of the Agi Workshop 2006 by Ben Goertzel, Pei Wang

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

AI winter, artificial general intelligence, bioinformatics, brain emulation, combinatorial explosion, complexity theory, computer vision, conceptual framework, correlation coefficient, epigenetics, friendly AI, information retrieval, Isaac Newton, John Conway, Loebner Prize, Menlo Park, natural language processing, Occam's razor, p-value, pattern recognition, performance metric, Ray Kurzweil, Rodney Brooks, semantic web, statistical model, strong AI, theory of mind, traveling salesman, Turing machine, Turing test, Von Neumann architecture, Y2K

We come to the game with numerous modules useful for 3 Roughly speaking, the standard proof that a particular problem class C is hard is given by showing that you can map another hard problem class H into it. Since there is (believed to be) insufficient underlying structure to solve H rapidly, this then exhibits a subclass of C that is not (believed to be) rapidly solvable. In the case of Sokoban, the proof proceeds by constructing, for any given Turing machine with given finite tape length, a particular Sokoban instance that is solvable if and only if the Turing machine halts in an accepting state. This leaves (at least) two outs for solving problems in C rapidly. First, since the mapping is into, with range only a small subset of instances of C, almost all instances of C may be rapidly solvable. For example, in the case of Sokoban, it intuitively seems that random instances can only be hard if they have a high enough density of barrels and goals, because otherwise solving the different goals decouples.


pages: 489 words: 148,885

Accelerando by Stross, Charles

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

call centre, carbon-based life, cellular automata, cognitive dissonance, Conway's Game of Life, dark matter, dumpster diving, Extropian, finite state, Flynn Effect, glass ceiling, gravity well, John von Neumann, knapsack problem, Kuiper Belt, Magellanic Cloud, mandelbrot fractal, market bubble, means of production, packet switching, performance metric, phenotype, planetary scale, Pluto: dwarf planet, reversible computing, Richard Stallman, SETI@home, Silicon Valley, Singularitarianism, slashdot, South China Sea, stem cell, technological singularity, telepresence, The Chicago School, theory of mind, Turing complete, Turing machine, Turing test, upwardly mobile, Vernor Vinge, Von Neumann architecture, web of trust, Y2K

Aineko glances at Amber, sees her thunderous expression, and hastily changes the subject: "The solution was intuitively obvious, just not to humans. You're so verbal." Lifting a hind paw, she scratches behind her left ear for a moment then pauses, foot waving absentmindedly. "Besides, the CETI team was searching under the street lights while I was sniffing around in the grass. They kept trying to find primes; when that didn't work, they started trying to breed a Turing machine that would run it without immediately halting." Aineko lowers her paw daintily. "None of them tried treating it as a map of a connectionist system based on the only terrestrial components anyone had ever beamed out into deep space. Except me. But then, your mother had a hand in my wetware, too." "Treating it as a map –" Amber stops. "You were meant to penetrate Dad's corporate network?" "That's right," says the cat.

For example, a collapse of the false vacuum," Manfred insists, slightly uncoordinated and slurring his vowels under the influence of the first glass of fruit punch he's experienced in nigh-on twenty real-time years. His body is young and still relatively featureless, hair still growing out, and he's abandoned his old no-implants fetish at last to adopt an array of interfaces that let him internalize all the exocortex processes that he formerly ran on an array of dumb Turing machines outside his body. He's standing on his own sense of style and is the only person in the room who isn't wearing some variation of dinner jacket or classical evening dress. "Entangled exchange via routers is all very well, but it won't let us escape the universe itself – any phase change will catch up eventually, the network must have an end. And then where will we be, Sameena?" "I'm not disputing that."


pages: 479 words: 144,453

Homo Deus: A Brief History of Tomorrow by Yuval Noah Harari

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

23andMe, agricultural Revolution, algorithmic trading, Anne Wojcicki, anti-communist, Anton Chekhov, autonomous vehicles, Berlin Wall, call centre, Chris Urmson, cognitive dissonance, Columbian Exchange, computer age, Deng Xiaoping, don't be evil, European colonialism, experimental subject, falling living standards, Flash crash, Frank Levy and Richard Murnane: The New Division of Labor, glass ceiling, global village, invention of writing, invisible hand, Isaac Newton, job automation, Kevin Kelly, means of production, Mikhail Gorbachev, Minecraft, Moneyball by Michael Lewis explains big data, mutually assured destruction, new economy, pattern recognition, Peter Thiel, placebo effect, Ray Kurzweil, self-driving car, Silicon Valley, Silicon Valley ideology, stem cell, Steven Pinker, telemarketer, too big to fail, trade route, Turing machine, Turing test, ultimatum game, Watson beat the top human players on Jeopardy!

The most interesting emerging religion is Dataism, which venerates neither gods nor man – it worships data. 11 The Data Religion Dataism says that the universe consists of data flows, and the value of any phenomenon or entity is determined by its contribution to data processing.1 This may strike you as some eccentric fringe notion, but in fact it has already conquered most of the scientific establishment. Dataism was born from the explosive confluence of two scientific tidal waves. In the 150 years since Charles Darwin published On the Origin of Species, the life sciences have come to see organisms as biochemical algorithms. Simultaneously, in the eight decades since Alan Turing formulated the idea of a Turing Machine, computer scientists have learned to engineer increasingly sophisticated electronic algorithms. Dataism puts the two together, pointing out that exactly the same mathematical laws apply to both biochemical and electronic algorithms. Dataism thereby collapses the barrier between animals and machines, and expects electronic algorithms to eventually decipher and outperform biochemical algorithms.

(game show) 315–16, 315 Jesus Christ 91, 155, 183, 187, 271, 274, 297 Jews/Judaism: ancient/biblical 60, 90–1, 94, 172–3, 174, 181, 193, 194–5, 268, 390; animal welfare and 94; expulsions from early modern Europe 197, 198; Great Jewish Revolt (AD 70) 194; homosexuality and 225–6; Second World War and 164–5, 165, 182 Jolie, Angelina 332–3, 335, 347 Jones, Lieutenant Henry 254 Journal of Personality and Social Psychology 354–5 Joyce, James: Ulysses 240 JSTOR digital library 383 Jung, Carl 223–4 Kahneman, Daniel 294, 295–6, 338–9 Kasparov, Garry 320–1, 320 Khmer Rouge 264 Khrushchev, Nikita 263, 273–4 Kurzweil, Ray 24, 25, 27; The Singularity is Near 381 Kyoto protocol, 1997 215–16 Lake Fayum engineering project, Egypt 161–2, 175, 178 Larson, Professor Steve 324–5 Law of the Jungle 14–21 lawns 58–64, 62, 63 lawyers, replacement by artificial intelligence of 314 Lea, Tom: That 2,000 Yard Stare (1944) 244, 245, 246 Lenin Academy for Agricultural Sciences 371–2 Lenin, Vladimir 181, 207, 251, 271, 272, 273, 375 Levy, Professor Frank 322 liberal humanism/liberalism 98, 181, 247; contemporary alternatives to 267–77; free will and 281–90, 304; humanism and see humanism; humanist wars of religion, 1914– 1991 and 261–7; individualism, belief in 290–304, 305; meaning of life and 304, 305; schism within humanism and 246–57; science undermines foundations of 281–306; technological challenge to 305–6, 307–50; value of experience and 257–9, 260, 387–8; victory of 265–7 life expectancy 5, 25–7, 32–4, 50 ‘logic bombs’ (malicious software codes) 17 Louis XIV, King 4, 64, 227 lucid dreaming 361–2 Luther, Martin 185–7, 275, 276 Luther King, Martin 263–4, 275 Lysenko, Trofim 371–2 MAD (mutual assured destruction) 265 malaria 12, 19, 315 malnutrition 3, 5, 6, 10, 27, 55 Mao Zedong 27, 165, 167, 251, 259, 263, 375 Maris, Bill 24 marriage: artificial intelligence and 337–8, 343; gay 275, 276; humanism and 223–5, 275, 276, 291, 303–4, 338, 364; life expectancy and 26 Marx, Karl/Marxism 56–7, 60, 183, 207, 247–8, 271–4; Communist Manifesto 217; Das Kapital 57, 274 Mattersight Corporation 317–18 Mazzini, Giuseppe 249–50 meaning of life 184, 222, 223, 299–306, 338, 386 Memphis, Egypt 158–9 Mendes, Aristides de Sousa 164–5, 164 Merkel, Angela 248–9 Mesopotamia 93 Mexico 8–9, 11, 263 Michelangelo 27, 253; David 260 Microsoft 15, 157, 330–1; Band 330–1; Cortana 342–3 Mill, John Stuart 35 ‘mind-reading’ helmet 44–5 Mindojo 314 MIT 322, 383 modern covenant 199–219, 220 Modi, Narendra 206, 207 money: credit and 201–5; Dataism and 352, 365, 379; intersubjective nature of 144, 145, 171, 177; invention of 157, 158, 352, 379; investment in growth 209–11 mother–infant bond 88–90 Mubarak, Hosni 137 Muhammad 188, 226, 270, 391 Murnane, Professor Richard 322 Museum of Islamic Art, Qatar 64 Muslims: Charlie Hebdo attack and 226; Crusades and 146, 147, 148, 149; economic growth, belief in 206; evaluating success of 174; evolution and 103; expulsions of from early modern Europe 197, 198; free will and 285; lawns and 64; LGBT community and 225 see also Islam Mussolini, Benito 302 Myanmar 144, 206 Nagel, Thomas 357 nanotechnology 23, 25, 51, 98, 212, 269, 344, 353 National Health Service, UK 334–5 National Salvation Front, Romania 136 NATO 264–5 Naveh, Danny 76, 96 Nayaka people 75–6, 96 Nazism 98, 164–5, 181, 182, 247, 255–7, 262–3, 375, 376, 396 Ne Win, General 144 Neanderthals 49, 156, 261, 273, 356, 378 Nebuchadnezzar, King of Babylonia 172–3, 310 Nelson, Shawn 255 New York Times 309, 332–4, 347, 370 New Zealand: Animal Welfare Amendment Act, 2015 122 Newton, Isaac 27, 97–8, 143, 197 Nietzsche, Friedrich 234, 254, 268 non-organic beings 43, 45 Norenzayan, Ara 354–5 Novartis 330 nuclear weapons 15, 16, 17, 17, 131, 149, 163, 216, 265, 372 Nyerere, Julius 166 Oakland Athletics 321 Obama, President Barack 313, 375 obesity 5–6, 18, 54 OncoFinder 323 Ottoman Empire 197, 207 ‘Our Boys Didn’t Die in Vain’ syndrome 300–3, 301 Page, Larry 28 paradox of knowledge 55–8 Paris Agreement, 2015 216 Pathway Pharmaceuticals 323 Petsuchos 161–2 Pfungst, Oskar 129 pharmacists 317 pigs, domesticated 79–83, 82, 87–8, 90, 98, 99, 100, 101, 231 Pinker, Steven 305 Pius IX, Pope 270–1 Pixie Scientific 330 plague/infectious disease 1–2, 6–14 politics: automation of 338–41; biochemical pursuit of happiness and 41; liberalism and 226–7, 229, 232, 232, 234, 247–50, 247n, 252; life expectancy and 26–7, 29; revolution and 132–7; speed of change in 58 pollution 20, 176, 213–14, 215–16, 341–2 poverty 3–6, 19, 33, 55, 205–6, 250, 251, 262, 349 Presley, Elvis 159–60, 159 Problem of Other Minds 119–20, 126–7 Protestant Reformation 185–7, 198, 242–4, 242, 243 psychology: evolutionary 82–3; focus of research 353–6, 360–2; Freudian 117; humanism and 223–4, 251–2; positive 360–2 Putin, Vladimir 26, 375 pygmy chimpanzees (bonobos) 138–9 Quantified Self movement 331 quantum physics 103, 170, 182, 234 Qur’an 170, 174, 269, 270 rats, laboratory 38, 39, 101, 122–4, 123, 127–8, 286–7 Redelmeier, Donald 296 relativity, theory of 102, 103, 170 religion: animals and 75–8, 90–8, 173; animist 75–8, 91, 92, 96–7, 173; challenge to liberalism 268; Dataism 367–97 see also Dataism; defining 180–7; ethical judgments 195–7; evolution and see evolution; formula for knowledge 235–7; God, death of 67, 234, 261, 268; humanist ethic and 234–5; monotheist 101–2, 173; science, relationship with 187–95, 197–8; scriptures, belief in 172–4; spirituality and 184–7; theist religions 90–6, 98, 274 revolutions 57, 60, 132–7, 155, 263–4, 308, 310–11 Ritalin 39, 364 robo-rat 286–7 Roman Empire 98, 191, 192, 194, 240, 373 Romanian Revolution, 1989 133–7, 138 Romeo and Juliet (Shakespeare) 365–6 Rousseau, Jean-Jacques 223, 282, 305 Russian Revolution, 1917 132–3, 136 Rwanda 15 Saarinen, Sharon 53 Saladin 146, 147, 148, 150–1 Santino (chimpanzee) 125–7 Saraswati, Dayananda 270, 271, 273 Scientific Revolution 96–9, 197–8, 212, 236–7, 379 Scotland 4, 303–4, 303 Second World War, 1939–45 21, 34, 55, 115, 164, 253, 262–3, 292 self: animal self-consciousness 124–7; Dataism and 386–7, 392–3; evolutionary theory and 103–4; experiencing and narrating self 294–305, 337, 338–9, 343; free will and 222–3, 230, 247, 281–90, 304, 305, 306, 338; life sciences undermine liberal idea of 281–306, 328–9; monotheism and 173, 174; single authentic self, humanist idea of 226–7, 235–6, 251, 281–306, 328–41, 363–6, 390–1; socialism and self-reflection 251–2; soul and 285; techno-humanism and 363–6; technological challenge to liberal idea of 327–46, 363–6; transcranial stimulator and 289 Seligman, Martin 360 Senusret III 161, 162 September 11 attacks, New York, 2011 18, 374 Shavan, Shlomi 331 Shedet, Egypt 161–2 Silico Medicine 323 Silicon Valley 15, 24, 25, 268, 274, 351, 381 Sima Qian 173, 174 Singapore 32, 207 smallpox 8–9, 10, 11 Snayers, Pieter: Battle of White Mountain 242–4, 243, 246 Sobek 161–2, 163, 171, 178–9 socialist humanism/socialism 247–8, 250–2, 256, 259–60, 261–2, 263, 264, 265, 266–7, 271–4, 325, 351, 376 soul 29, 92, 101–6, 115–16, 128, 130, 132, 138, 146, 147, 148, 150, 160, 184–5, 186, 189, 195, 229, 272, 282, 283, 285, 291, 324, 325, 381 South Korea 33, 151, 264, 266, 294, 349 Soviet Union: communism and 206, 208, 370, 371–2; data processing and 370, 370, 371–2; disappearance/collapse of 132–3, 135, 136, 145, 145, 266; economy and 206, 208, 370, 370, 371–2; Second World War and 263 Spanish Flu 9–10, 11 Sperry, Professor Roger Wolcott 292 St Augustine 275, 276 Stalin, Joseph 26–7, 256, 391 stock exchange 105–10, 203, 210, 294, 313, 369–70, 371 Stone Age 33–4, 60, 74, 80, 131, 155, 156, 157, 163, 176, 261 subjective experience 34, 80, 82–3, 105–17, 143–4, 155, 179, 229, 237, 312, 388, 393 Sudan 270, 271, 273 suicide rates 2, 15, 33 Sumerians 156–8, 159, 162–3, 323 Survivor (TV reality show) 240 Swartz, Aaron 382–3; Guerilla Open Access Manifesto 383 Sylvester I, Pope 190–1 Syria 3, 19, 149, 171, 220, 275, 313 Taiping Rebellion, 1850–64 271 Talwar, Professor Sanjiv 286–7 techno-humanism: definition of 352–3; focus of psychological research and 353–9; human will and 363–6; upgrading of mind 359–66 technology: Dataism and see Dataism; inequality and future 346–50; liberal idea of individual challenged by 327–46; renders humans economically and militarily useless 307–27; techno-humanism and see techno-humanism Tekmira 203 terrorism 14, 18–19, 226, 288, 290, 311 Tesla 114, 322 Thatcher, Margaret 57, 372 Thiel, Peter 24–5 Third Man, The (movie) 253–4 Thirty Years War, 1618–48 242–3 Three Gorges Dam, 163, 188, 196 Thucydides 173, 174 Toyota 230, 294, 323 transcranial stimulators 44–5, 287–90, 362–3, 364 Tree of Knowledge, biblical 76–7, 77, 97, 98 tuberculosis 9, 19, 23, 24 Turing, Alan 120, 367 Turing Machine 367 Turing Test 120 23andMe 336 Twitter 47, 137, 313, 387 US Army 287–90, 362–3, 364 Uganda 192–3, 195 United States: Dataism and 374; energy usage and happiness levels in 34; evolution, suspicion of within 102; Kyoto protocol, 1997 and 215–16; liberalism, view of within 247n; nuclear weapons and 163; pursuit of happiness and 31; value of life in compared to Afghan life 100; Vietnam War and 264, 265; well-being levels 34 Universal Declaration of Human Rights 21, 24, 31 Urban II, Pope 227–8 Uruk 156–7 Valla, Lorenzo 192 Valle Giulia, Battle of, 1968 263 vampire bats 204–5 Vedas 170, 181, 270 Vietnam War, 1954–75 57, 244, 264, 265 virtual-reality worlds 326–7 VITAL 322–3 Voyager golden record 258–9 Waal, Frans de 140–1 Walter, Jean-Jacques: Gustav Adolph of Sweden at the Battle of Breitenfeld (1631) 242, 243, 244–5 war 1–3, 14–19; humanism and narratives of 241–6, 242, 245, 253–6 Warsaw Pact 264–5 Watson (artificial intelligence system) 315–17, 315, 330 Watson, John 88–9, 90 Waze 341–2 web of meaning 143–9 WEIRD (Western, educated, industrialised, rich and democratic) countries, psychology research focus on 354–5, 359, 360 West Africa: Ebola and 11, 13, 203 ‘What Is It Like to Be a Bat?’


pages: 259 words: 67,456

The Mythical Man-Month by Brooks, Jr. Frederick P.

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

finite state, HyperCard, Menlo Park, sorting algorithm, speech recognition, Steve Jobs, Tacoma Narrows Bridge, Turing machine

., "System quality through structured programming," AFIPS Proc FJCC, 41-1 (1972), pp. 339-343. Dahl, O. J., E. W. Dijkstra, and C. A. R. Hoare, Structured Programming. London and New York: Academic Press, 1972. This volume contains the fullest treatment. See also Dijkstra's germinal letter, "GOTO statement considered harm-ful," CACM, II, 3 (March, 1968), pp. 147-148. Bohm, C., and A. Jacopini, "Flow diagrams, Turing machines, and languages with only two formation rules," CACM, 9, 5 (May, 1966), pp. 366-371. Codd, E. F., E. S. Lowry, E. McDonough, and C. A. Scalzi, "Multiprogramming STRETCH: Feasibility considerations," CACM, 2,11 (Nov., 1959), pp. 13-17. Strachey, C., "Time sharing in large fast computers," Proc. Int. Con/, on Info. Processing, UNESCO (June, 1959), pp. 336-341. See also Codd's remarks on p. 341, where he reported progress on work like that proposed in Strachey's paper.


pages: 218 words: 63,471

How We Got Here: A Slightly Irreverent History of Technology and Markets by Andy Kessler

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

Albert Einstein, Andy Kessler, automated trading system, bank run, Big bang: deregulation of the City of London, Bretton Woods, British Empire, buttonwood tree, Claude Shannon: information theory, Corn Laws, Edward Lloyd's coffeehouse, fiat currency, floating exchange rates, Fractional reserve banking, full employment, Grace Hopper, invention of the steam engine, invention of the telephone, invisible hand, Isaac Newton, Jacquard loom, Jacquard loom, James Hargreaves, James Watt: steam engine, John von Neumann, joint-stock company, joint-stock limited liability company, Joseph-Marie Jacquard, Maui Hawaii, Menlo Park, Metcalfe's law, packet switching, price mechanism, probability theory / Blaise Pascal / Pierre de Fermat, profit motive, railway mania, RAND corporation, Silicon Valley, Small Order Execution System, South Sea Bubble, spice trade, spinning jenny, Steve Jobs, supply-chain management, supply-chain management software, trade route, transatlantic slave trade, transatlantic slave trade, tulip mania, Turing machine, Turing test, William Shockley: the traitorous eight

The Robinson used relays and other electronics and required two sets of paper tapes to read 2000 characters a second. Progress was slow as the tape kept ripping. Two London-based post office engineers, Tommy Flowers and Alan Coombes, improved on the Robinson, more than doubling the speed, by using 2400 vacuum tubes and a number of servomotors, instead of relays and fragile paper tape. But it was still a Turing machine. Its name was Colossus, a mighty name, and it was moved to 114 HOW WE GOT HERE Bletchley Park and started operating in December 1943. It had both logic and memory and since it could change its program based on which code needed to be deciphered, it was a true Turing programmable computer. The Allies relied on the Colossus to help determine Nazi troop concentrations and the best D-Day landing points. *** But in 1945, after VE and VJ days and the end of the war, we all know what happened next.

Raw Data Is an Oxymoron by Lisa Gitelman

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

collateralized debt obligation, computer age, continuous integration, crowdsourcing, Drosophila, Edmond Halley, Filter Bubble, Firefox, Google Earth, Howard Rheingold, index card, informal economy, Isaac Newton, Johann Wolfgang von Goethe, knowledge worker, Louis Daguerre, Menlo Park, optical character recognition, RFID, Richard Thaler, Silicon Valley, social graph, software studies, statistical model, Stephen Hawking, Steven Pinker, text mining, time value of money, trade route, Turing machine, urban renewal, Vannevar Bush

For the fundamentally unproductive maintenance of the difference between man and machine from a systems theoretical perspective, see Peter Fuchs, “Kommunikation mit Computern? Zur Korrektur einer Fragestellung,” Sociologia Internationalis 29 (1991): 1–30, esp. 8f. 38. For the only ontological assumption of systems theory, see the first sentence of the first chapter of the outline of a general theory, Luhmann, Soziale Systeme, 30. 39. Ibid., 240, my emphasis of the term, which (not coincidentally?) refers to the Turing machine. 40. Luhmann, Die Gesellschaft der Gesellschaft, 82. 41. See first the foundational chapter in Luhmann, Soziale Systeme, 191ff. In addition, on the question of the extent to which communication applies to computers, see Peter Fuchs, “Kommunikation mit Computern? Zur Korrektur einer Fragestellung,” Sociologia Internationalis 29 (1991): 1–30. 42. Luhmann, Die Gesellschaft der Gesellschaft, 82f. 43.


pages: 292 words: 88,319

The Infinite Book: A Short Guide to the Boundless, Timeless and Endless by John D. Barrow

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

Albert Einstein, Andrew Wiles, anthropic principle, Arthur Eddington, cosmological principle, dark matter, Edmond Halley, Fellow of the Royal Society, Georg Cantor, Henri Poincaré, Isaac Newton, mutually assured destruction, Olbers’ paradox, prisoner's dilemma, Ray Kurzweil, short selling, Stephen Hawking, Turing machine

So ½ S = ¼ + + + + ... = S – ½ since the right-hand size is just the series without its first term, which is ½. Hence, ½ S = ½ and S = 1. 5. H. Weyl, Philosophy of Mathematics and Natural Science, Princeton University Press, 1949, p. 42. Weyl’s mention of decision procedures and machines is interesting. Mathematics had just emerged from a pre-war period which saw the advent in print of Alan Turing’s ‘Turing machine’, the archetypal universal computer that is indistinguishable from a human calculator (the original meaning of the word ‘computer’) and the question, answered in the negative by Turing, of whether a finite computing machine would be able to decide the truth or falsity of all statements of mathematics in a finite time. Turing showed that there exist uncomputable problems for which the machine would never halt if set to work on deciding them.


pages: 335 words: 107,779

Some Remarks by Neal Stephenson

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

airport security, augmented reality, barriers to entry, British Empire, cable laying ship, call centre, cellular automata, edge city, Eratosthenes, Fellow of the Royal Society, Hacker Ethic, impulse control, Iridium satellite, Isaac Newton, Jaron Lanier, John von Neumann, Just-in-time delivery, Kevin Kelly, music of the spheres, Norbert Wiener, offshore financial centre, oil shock, packet switching, pirate software, Richard Feynman, Richard Feynman, Saturday Night Live, shareholder value, Silicon Valley, Skype, slashdot, social web, Socratic dialogue, South China Sea, special economic zone, Stephen Hawking, the scientific method, trade route, Turing machine, uranium enrichment, Vernor Vinge, X Prize

The debate on free will vs. determinism is no more settled today than it was at the time of the Leibniz-Clarke Correspondence, and so in that sense (at least) Monadology is still interesting as a gambit, which different observers might see as heroic, ingenious, or desperate, to cut that Gordian knot by making free minds or souls into the fundamental components of the universe. 2. Leibniz’s interpreters made use of the vocabulary at their disposal to translate his terminology into words such as “mind,” “soul,” “cognition,” “endeavour,” etc. This, however, was before the era of information theory, Turing machines, and digital computers, which have supplied us with a new set of concepts, a lexicon, and a rigorous science pertaining to things that, like monads, perform a sort of cogitation but are neither divine nor human. A translator of Leibniz’s work, beginning in a.d. 2010 from a blank sheet of paper, would, I submit, be more likely to use words like “computer” and “computation” than “soul” and “cognition.”


pages: 311 words: 94,732

The Rapture of the Nerds by Cory Doctorow, Charles Stross

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

3D printing, Ayatollah Khomeini, butterfly effect, cognitive dissonance, combinatorial explosion, complexity theory, Credit Default Swap, dematerialisation, Drosophila, epigenetics, Extropian, gravity well, greed is good, haute couture, hive mind, margin call, phenotype, Plutocrats, plutocrats, rent-seeking, Richard Feynman, Richard Feynman, telepresence, Turing machine, Turing test, union organizing

Tell your guidebooks or familiars or whatever to download Exhibit B for you. As you can see, the genome of the said item is chimeric and shows signs of crude tampering, but it’s largely derived from Drosophila, Mus musculus, and a twenty-first-century situationist artist or politician called Sarah Palin. Large chunks of its genome appear to be wholly artificial, though, written entirely in Arabic, and there’s an aqueous-phase Turing machine partially derived from octopus ribosomes to interpret them. It looks as if something has been trying to use the sharia code as a platform for implementing a legal virtual machine. We’re not sure why, unless it’s an obscure joke.” “Does the metasphere have a sense of humor?” Huw says. He clears his throat—the dust must be getting to him, because it feels as if he’s developing a ticklish cough.


pages: 366 words: 107,145

Fuller Memorandum by Stross, Charles

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

Any sufficiently advanced technology is indistinguishable from magic, Beeching cuts, British Empire, cognitive dissonance, complexity theory, congestion charging, dumpster diving, finite state, Firefox, HyperCard, invisible hand, land reform, linear programming, peak oil, security theater, sensible shoes, side project, telemarketer, Turing machine

I can't see: my arm is a monstrous, distracting wall of ache, I'm still handcuffed, and now they've hooded me and pinioned my ankles. So much for making a run for it. 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! Think of something! But it all blurs, when you're in pain. Like most of my ilk I work best in a nice warm office, with a honking great monitor on my desk and a can of Pringles in front of me.


pages: 322 words: 88,197

Wonderland: How Play Made the Modern World by Steven Johnson

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

Ada Lovelace, Alfred Russel Wallace, Antoine Gombaud: Chevalier de Méré, Berlin Wall, bitcoin, Book of Ingenious Devices, Buckminster Fuller, Claude Shannon: information theory, Clayton Christensen, colonial exploitation, computer age, conceptual framework, crowdsourcing, cuban missile crisis, Drosophila, Fellow of the Royal Society, game design, global village, Hedy Lamarr / George Antheil, HyperCard, invention of air conditioning, invention of the printing press, invention of the telegraph, Islamic Golden Age, Jacquard loom, Jacquard loom, Jacques de Vaucanson, James Watt: steam engine, Jane Jacobs, John von Neumann, joint-stock company, Joseph-Marie Jacquard, Landlord's Game, lone genius, megacity, Minecraft, Murano, Venice glass, music of the spheres, Necker cube, New Urbanism, Oculus Rift, On the Economy of Machinery and Manufactures, pattern recognition, pets.com, placebo effect, probability theory / Blaise Pascal / Pierre de Fermat, profit motive, QWERTY keyboard, Ray Oldenburg, spice trade, spinning jenny, statistical model, Steve Jobs, Steven Pinker, Stewart Brand, supply-chain management, talking drums, the built environment, The Great Good Place, the scientific method, The Structural Transformation of the Public Sphere, trade route, Turing machine, Turing test, Upton Sinclair, urban planning, Victor Gruen, Watson beat the top human players on Jeopardy!, white flight, Whole Earth Catalog, working poor, Wunderkammern

You could dream up new melodies for it, instruct it to produce new patterns of sound. The water clocks the Banu Musa built were automated. But their “instrument” was endowed with a higher-level property. It was programmable. Conceptually, this was a massive leap forward: machines designed specifically to be open-ended in their functionality, machines controlled by code and not just mechanics. A direct line of logic connects the “Instrument Which Plays by Itself” to the Turing machines that have so transformed life in the modern age. You can think of the instrument as the moment where the Manichean divide between hardware and software first opened up. An invention that itself makes invention easier, faster, more receptive to trial and error. A virtual machine. Yet it must have been hard to see (or hear) its significance at the time. To the untutored spectator, it might have paled beside the animated peacocks.


pages: 561 words: 120,899

The Theory That Would Not Die: How Bayes' Rule Cracked the Enigma Code, Hunted Down Russian Submarines, and Emerged Triumphant From Two Centuries of Controversy by Sharon Bertsch McGrayne

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

bioinformatics, British Empire, Claude Shannon: information theory, Daniel Kahneman / Amos Tversky, double helix, Edmond Halley, Fellow of the Royal Society, full text search, Henri Poincaré, Isaac Newton, John Nash: game theory, John von Neumann, linear programming, meta analysis, meta-analysis, Nate Silver, p-value, placebo effect, prediction markets, RAND corporation, recommendation engine, Renaissance Technologies, Richard Feynman, Richard Feynman, Richard Feynman: Challenger O-ring, Ronald Reagan, speech recognition, statistical model, stochastic process, Thomas Kuhn: the structure of scientific revolutions, traveling salesman, Turing machine, Turing test, uranium enrichment, Yom Kippur War

Their ignorance proved fortunate. Despite the strange reputation of British mathematicians, the operational head of GC&CS prepared for war by quietly recruiting a few nonlinguists—“men of the Professor type”5—from Oxford and Cambridge universities. Among that handful of men was Alan Mathison Turing, who would father the modern computer, computer science, software, artificial intelligence, the Turing machine, the Turing test—and the modern Bayesian revival. Turing had studied pure mathematics at Cambridge and Princeton, but his passion was bridging the gap between abstract logic and the concrete world. More than a genius, Turing had imagination and vision. He had also developed an almost unique set of interests: the abstract mathematics of topology and logic; the applied mathematics of probability; the experimental derivation of fundamental principles; the construction of machines that could think; and codes and ciphers.


pages: 402 words: 110,972

Nerds on Wall Street: Math, Machines and Wired Markets by David J. Leinweber

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

AI winter, algorithmic trading, asset allocation, banking crisis, barriers to entry, Big bang: deregulation of the City of London, butterfly effect, buttonwood tree, buy low sell high, capital asset pricing model, citizen journalism, collateralized debt obligation, corporate governance, Craig Reynolds: boids flock, credit crunch, Credit Default Swap, credit default swaps / collateralized debt obligations, Danny Hillis, demand response, disintermediation, distributed generation, diversification, diversified portfolio, Emanuel Derman, en.wikipedia.org, experimental economics, financial innovation, Gordon Gekko, implied volatility, index arbitrage, index fund, information retrieval, Internet Archive, John Nash: game theory, Khan Academy, load shedding, Long Term Capital Management, Machine translation of "The spirit is willing, but the flesh is weak." to Russian and back, market fragmentation, market microstructure, Mars Rover, moral hazard, mutually assured destruction, natural language processing, Network effects, optical character recognition, paper trading, passive investing, pez dispenser, phenotype, prediction markets, quantitative hedge fund, quantitative trading / quantitative finance, QWERTY keyboard, RAND corporation, random walk, Ray Kurzweil, Renaissance Technologies, Richard Stallman, risk tolerance, risk-adjusted returns, risk/return, Ronald Reagan, semantic web, Sharpe ratio, short selling, Silicon Valley, Small Order Execution System, smart grid, smart meter, social web, South Sea Bubble, statistical arbitrage, statistical model, Steve Jobs, Steven Levy, Tacoma Narrows Bridge, the scientific method, The Wisdom of Crowds, time value of money, too big to fail, transaction costs, Turing machine, Upton Sinclair, value at risk, Vernor Vinge, yield curve, Yogi Berra

Thinking Machines, founded by computational superstar Danny Hillis (son-in-law of Marvin Minsky, the pope of symbolic AI), gathered some of the leading lights to build and program massive machines with up to 64K (65,536) processors. That is a lot more than one, but still a lot less than the 100 billion neurons in the brain. You don’t need a machine with a billion processors to try out solutions that would use them. A simulator will do fine, if not as fast. For theory buffs, this is an example of the idea of a universal computation; a Turing machine or its equivalent can emulate anything you want. The Nintendo 64 emulators you can run on your PC to play Pac-Man are another. The neural net movement exploited this idea, seeking to realize learning by mimicking structure and function. Another branch of the 184 Nerds on Wall Str eet turn to biologically inspired approaches to learning used the intriguing idea of mimicking evolution. The mechanics of evolution at the chromosome level—the processes of mutation and crossover, dominant and recessive traits—are understood well.


pages: 566 words: 122,184

Code: The Hidden Language of Computer Hardware and Software by Charles Petzold

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

Bill Gates: Altair 8800, Claude Shannon: information theory, computer age, Douglas Engelbart, Dynabook, Eratosthenes, Grace Hopper, invention of the telegraph, Isaac Newton, Jacquard loom, Jacquard loom, James Watt: steam engine, John von Neumann, Joseph-Marie Jacquard, Louis Daguerre, millennium bug, Norbert Wiener, optical character recognition, popular electronics, Richard Feynman, Richard Feynman, Richard Stallman, Silicon Valley, Steve Jobs, Turing machine, Turing test, Vannevar Bush, Von Neumann architecture

In Great Britain, the Colossus computer (first operational in 1943) was dedicated to cracking the German "Enigma" code-making machine. Contributing to this project (and to some later British computer projects) was Alan M. Turing (1912–1954), who is most famous these days for writing two influential papers. The first, published in 1937, pioneered the concept of "computability," which is an analysis of what computers can and can't do. He conceived of an abstract model of a computer that's now known as the Turing Machine. The second famous paper Turing wrote was on the subject of artificial intelligence. He introduced a test for machine intelligence that's now known as the Turing Test. At the Moore School of Electrical Engineering (University of Pennsylvania), J. Presper Eckert (1919–1995) and John Mauchly (1907–1980) designed the ENIAC (Electronic Numerical Integrator and Computer). It used 18,000 vacuum tubes and was completed in late 1945.

Jennifer Morgue by Stross, Charles

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

call centre, correlation does not imply causation, disintermediation, dumpster diving, Etonian, haute couture, interchangeable parts, Maui Hawaii, mutually assured destruction, planetary scale, RFID, Silicon Valley, Skype, slashdot, stem cell, telepresence, traveling salesman, Turing machine

This realm, being hosted on Bosch, is scattered with traps that are superclassed into a bunch of scanner routines from Project Aurora and sniff for any taint of the real supernatural. 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." "Running the DM client — " Brains goes cross-eyed for a moment " — is it reentrant" "It will be."


pages: 331 words: 60,536

The Sovereign Individual: How to Survive and Thrive During the Collapse of the Welfare State by James Dale Davidson, Rees Mogg

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

affirmative action, agricultural Revolution, bank run, barriers to entry, Berlin Wall, borderless world, British Empire, California gold rush, clean water, colonial rule, Columbine, compound rate of return, Danny Hillis, debt deflation, ending welfare as we know it, epigenetics, Fall of the Berlin Wall, falling living standards, feminist movement, financial independence, Francis Fukuyama: the end of history, full employment, George Gilder, Hernando de Soto, illegal immigration, income inequality, informal economy, information retrieval, Isaac Newton, Kevin Kelly, market clearing, Martin Wolf, Menlo Park, money: store of value / unit of account / medium of exchange, new economy, New Urbanism, offshore financial centre, Parkinson's law, pattern recognition, phenotype, price mechanism, profit maximization, rent-seeking, reserve currency, road to serfdom, Ronald Coase, school vouchers, seigniorage, Silicon Valley, spice trade, statistical model, telepresence, The Nature of the Firm, the scientific method, The Wealth of Nations by Adam Smith, Thomas L Friedman, Thomas Malthus, trade route, transaction costs, Turing machine, union organizing, very high income

The fact that genetically influenced sacrifice on behalf of the nation-state often militated against the evolutionary purpose of kin selection also tells you that humans are adaptable enough to adjust to many circumstances for which we were not genetically programmed in the conditions of the Stone Age. As Tudge elaborates in describing the "extreme generalness" of human beings: "We are the animal equivalent of the Turing machine: the universal device that can be turned to any task." 72 Which tendency will come to the surface in the coming transition crisis? Probably both. 224 The commercialization of sovereignty itself depends upon the willingness of hundreds of thousands of Sovereign Individuals and many millions of others to deploy their assets in the "First Bank of Nowhere" in order to secure immunity from direct compulsion.


pages: 1,201 words: 233,519

Coders at Work by Peter Seibel

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

Ada Lovelace, bioinformatics, cloud computing, Conway's Game of Life, domain-specific language, fault tolerance, Fermat's Last Theorem, Firefox, George Gilder, glass ceiling, HyperCard, information retrieval, loose coupling, Menlo Park, Metcalfe's law, premature optimization, publish or perish, random walk, revision control, Richard Stallman, rolodex, Saturday Night Live, side project, slashdot, speech recognition, the scientific method, Therac-25, Turing complete, Turing machine, Turing test, type inference, Valgrind, web application

Seibel: Do you ever wish you had focused more on the design of the language, as a language? Knuth: I don't know. I guess so. In a way I resent having every language be universal because they'll be universal in a different way. It's a little bit like Unix having 30 definitions of regular expressions under one roof— depending on which part of Unix you're using you've got a slightly different flavor of regular expressions. If every tool that you have includes a Turing machine inside, is this really the way to go? I was really thinking of TeX as something that the more programming it had in it, the less it was doing its real mission of typesetting. When I put in the calculation of prime numbers into the TeX manual I was not thinking of this as the way to use TeX. I was thinking, “Oh, by the way, look at this: dogs can stand on their hind legs and TeX can calculate prime numbers.”


pages: 798 words: 240,182

The Transhumanist Reader by Max More, Natasha Vita-More

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

23andMe, Any sufficiently advanced technology is indistinguishable from magic, artificial general intelligence, augmented reality, Bill Joy: nanobots, bioinformatics, brain emulation, Buckminster Fuller, cellular automata, clean water, cloud computing, cognitive bias, cognitive dissonance, combinatorial explosion, conceptual framework, Conway's Game of Life, cosmological principle, data acquisition, discovery of DNA, Drosophila, en.wikipedia.org, experimental subject, Extropian, fault tolerance, Flynn Effect, Francis Fukuyama: the end of history, Frank Gehry, friendly AI, game design, germ theory of disease, hypertext link, impulse control, index fund, John von Neumann, joint-stock company, Kevin Kelly, Law of Accelerating Returns, life extension, Louis Pasteur, Menlo Park, meta analysis, meta-analysis, moral hazard, Network effects, Norbert Wiener, P = NP, pattern recognition, phenotype, positional goods, prediction markets, presumed consent, Ray Kurzweil, reversible computing, RFID, Richard Feynman, Ronald Reagan, silicon-based life, Singularitarianism, stem cell, stochastic process, superintelligent machines, supply-chain management, supply-chain management software, technological singularity, Ted Nelson, telepresence, telepresence robot, telerobotics, the built environment, The Coming Technological Singularity, the scientific method, The Wisdom of Crowds, transaction costs, Turing machine, Turing test, Upton Sinclair, Vernor Vinge, Von Neumann architecture, Whole Earth Review, women in the workforce

Other Logics for Nanocomputers Before going into other extensions of conventional digital logic, there is another form of nanocomputer that may appear earlier for technological reasons. That’s the molecular biocomputer. Figure 18.4 Register operation. Originally published in Extropy 13 (1994). Copyright © Max More. Imagine that a DNA molecule is a tape, upon which is written 2 bits of information per base pair (the DNA molecule is a long string of adenine-thymine and guanine-cytosine pairs). Imagine, in particular, this to be the tape of a Turing machine, which is represented by some humongous clump of special-purpose enzymes that reads the “tape,” changes state, replaces a base pair with a new one, and slides up and down the “tape.” If one could design the enzyme clump using conventional molecular biology techniques (and each of the individual functions it needs to do are done somewhere, somehow, by some natural enzyme) you’d have a molecular computer.


pages: 647 words: 43,757

Types and Programming Languages by Benjamin C. Pierce

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

Albert Einstein, combinatorial explosion, experimental subject, finite state, Henri Poincaré, recommendation engine, sorting algorithm, Turing complete, Turing machine, type inference, Y Combinator

., Q, will appear in the position of U—in effect, performing an “indirect branch” through register 1 to the stream of instructions represented by Q. Conditional constructs and arithmetic (successor, predecessor, and zero-test) can be encoded using a generalization of this trick. Putting all of this together, we arrive at a proof of undecidability via a reduction from two-counter machines—a simple variant on ordinary Turing machines, consisting of a finite control and two counters, each holding a natural number—to subtyping statements. 28 28.5.5 Metatheory of Bounded Quantification 431 Theorem [Pierce, 1994]: For each two-counter machine M, there exists a subtyping statement S(M) such that S(M) is derivable in full F<: iff the execution of M halts. Thus, if we could decide whether any subtype statement is provable, then we could also decide whether any given two-counter machine will eventually halt.


pages: 1,758 words: 342,766

Code Complete (Developer Best Practices) by Steve McConnell

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

Ada Lovelace, Albert Einstein, Buckminster Fuller, call centre, choice architecture, continuous integration, data acquisition, database schema, fault tolerance, Grace Hopper, haute cuisine, if you see hoof prints, think horses—not zebras, index card, inventory management, iterative process, late fees, loose coupling, Menlo Park, place-making, premature optimization, revision control, slashdot, sorting algorithm, statistical model, Tacoma Narrows Bridge, the scientific method, Thomas Kuhn: the structure of scientific revolutions, Turing machine, web application

Software Cost Estimation with Cocomo II. Boston, MA: Addison-Wesley. Boehm, Barry. 2000b. "Unifying Software Engineering and Systems Engineering," IEEE Computer, March 2000, 114–116. Boehm-Davis, Deborah , Sylvia Sheppard, and John Bailey. 1987. "Program Design Languages: How Much Detail Should They Include?" International Journal of Man-Machine Studies 27, no. 4: 337–47. Böhm, C., and G. Jacopini. 1966. "Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules." Communications of the ACM 9, no. 5 (5): 366–71. Booch, Grady. 1987. Software Engineering with Ada, 2d ed. Menlo Park, CA: Benjamin/Cummings. Booch, Grady. 1994. Object Oriented Analysis and Design with Applications, 2d ed. Boston, MA: Addison-Wesley. Booth, Rick. 1997. Inner Loops : A Sourcebook for Fast 32-bit Software Development. Boston, MA: Addison-Wesley.


pages: 1,076 words: 67,364

Haskell Programming from first principles by Christopher Allen, Julie Moronuki

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

c2.com, en.wikipedia.org, natural language processing, spaced repetition, Turing complete, Turing machine, type inference, web application, Y Combinator

Chapter 1 All You Need is Lambda Anything from almost nothing Even the greatest mathematicians, the ones that we would put into our mythology of great mathematicians, had to do a great deal of leg work in order to get to the solution in the end. Daniel Tammett 29 CHAPTER 1. ALL YOU NEED IS LAMBDA 1.1 30 All You Need is Lambda This chapter provides a very brief introduction to the lambda calculus, a model of computation devised in the 1930s by Alonzo Church. A calculus is a method of calculation or reasoning; the lambda calculus is one process for formalizing a method. Like Turing machines, the lambda calculus formalizes the concept of effective computability, thus determining which problems, or classes of problems, can be solved. You may be wondering where the Haskell is. You may be contemplating skipping this chapter. You may feel tempted to skip ahead to the fun stuff when we build a project. DON’T. We’re starting from first principles here so that when we get around to building projects you know what you’re doing.


pages: 1,263 words: 371,402

The Year's Best Science Fiction: Twenty-Sixth Annual Collection by Gardner Dozois

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

augmented reality, clean water, computer age, cosmological constant, David Attenborough, Deng Xiaoping, double helix, financial independence, game design, gravity well, jitney, John Harrison: Longitude, Kuiper Belt, Mahatma Gandhi, Paul Graham, Richard Feynman, Richard Feynman, Richard Feynman: Challenger O-ring, Search for Extraterrestrial Intelligence, Skype, stem cell, theory of mind, Turing machine, Turing test, urban renewal, Wall-E

My data mining had quickly turned up recurring segments, chunks of organised data differing only in detail. And it was Wilson’s intuition that these things were bits of executable code: programs you could run. Even as expressed in the Eaglets’ odd flowing language, he thought he recognised logical loops, start and stop statements. Mathematics may or may not be universal, but computing seems to be—my brother had found Turing machines, buried deep in an alien database. Wilson translated the segments into a human mathematical programming language, and set them to run on a dedicated processor. They turned out to be like viruses. Once downloaded on almost any computer substrate they organised themselves, investigated their environment, started to multiply, and quickly grew, accessing the data banks that had been downloaded from the stars with them.


pages: 1,351 words: 385,579

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

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

1960s counterculture, affirmative action, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, availability heuristic, Berlin Wall, Bonfire of the Vanities, British Empire, Broken windows theory, California gold rush, Cass Sunstein, citation needed, clean water, cognitive dissonance, colonial rule, Columbine, computer age, conceptual framework, correlation coefficient, correlation does not imply causation, crack epidemic, cuban missile crisis, Daniel Kahneman / Amos Tversky, David Brooks, delayed gratification, demographic transition, desegregation, Doomsday Clock, Douglas Hofstadter, Edward Glaeser, en.wikipedia.org, European colonialism, experimental subject, facts on the ground, failed state, first-past-the-post, Flynn Effect, food miles, Francis Fukuyama: the end of history, fudge factor, full employment, ghettoisation, Gini coefficient, global village, Henri Poincaré, impulse control, income inequality, informal economy, invention of the printing press, Isaac Newton, lake wobegon effect, libertarian paternalism, loss aversion, Marshall McLuhan, McMansion, means of production, mental accounting, meta analysis, meta-analysis, Mikhail Gorbachev, mutually assured destruction, open economy, Peace of Westphalia, Peter Singer: altruism, QWERTY keyboard, race to the bottom, Ralph Waldo Emerson, random walk, Republic of Letters, Richard Thaler, Ronald Reagan, Rosa Parks, Saturday Night Live, security theater, Skype, Slavoj Žižek, South China Sea, statistical model, stem cell, Steven Levy, Steven Pinker, The Bell Curve by Richard Herrnstein and Charles Murray, The Wealth of Nations by Adam Smith, theory of mind, transatlantic slave trade, transatlantic slave trade, Turing machine, ultimatum game, uranium enrichment, V2 rocket, Walter Mischel, WikiLeaks, women in the workforce

Bennett, “Abducted: The Amber Alert system is more effective as theater than as a way to protect children,” Boston Globe, Jul. 20, 2008. 213. Kids hit by parents driving kids: Skenazy, 2009, p. 176. 214. Counterproductive kidnapping alerts: D. Bennett, “Abducted: The Amber Alert system is more effective as theater than as a way to protect children,” Boston Globe, Jul. 20, 2008. 215. Alan Turing: Hodges, 1983. 216. Turing machines: Turing, 1936. 217. Can machines think?: Turing, 1950. 218. State-sponsored homophobia, past: Fone, 2000. Present: Ottosson, 2009. 219. More homophobia against gay men: Fone, 2000. More laws against male homosexuality: Ottosson, 2006. 220. More hate crimes against men: U.S. Department of Justice, FBI, 2008 Hate crime statistics, table 4, http://www2.fbi.gov/ucr/hc2008/data/table_04.html. 221.