Turing's Cathedral
by George Dyson · 6 Mar 2012
sense on a finite no matter how large model),” noted Ulam, who then sketched out how he and von Neumann had hypothesized the evolution of Turing-complete (or “universal”) cellular automata within a digital universe of communicating memory cells. The definitions had to be made mathematically precise: A “universal” automaton is a
…
must depend on error-correcting codes in translating from one generation to the next. “Ulam!” probably refers to Ulam’s interest in the powers of Turing-complete cellular automata, now evidenced by many of the computational processes surrounding us today. The triplicate appearance of “Turing!” reflects how central Turing’s proof of
…
result seems to be related to the self-reproducing machines of von Neumann.”19 They were right. Codes populating the growing digital universe soon became Turing-complete, much as envisioned by Ulam and von Neumann in 1952. Turing’s ACE, a powerful Universal Machine, was to have had a memory of 25
…
whether a purely digital universe could capture some of the evolutionary processes we see in our universe. He envisioned an unbounded two-dimensional matrix where Turing-complete digital organisms (operating in two dimensions, unlike Barricelli’s one-dimensional, cross-breeding genetic strings) would compete for resources, and evolve. Ulam also suggested carrying
…
way to change the individual or collective human mind to prepare it for a future that nobody can now imagine.”36 Hordes of self-replicating Turing-complete digital organisms, much as he imagined them in 1952, now populate an unbounded matrix, while the companies and individuals who nurture them are ever more
In Our Own Image: Savior or Destroyer? The History and Future of Artificial Intelligence
by George Zarkadakis · 7 Mar 2016 · 405pp · 117,219 words
off for further processing by the interlinked difference engines. It was a very cybernetic design indeed! These innovative, self-referential features made the Analytical Engine ‘Turing complete’, meaning that it was a machine that could simulate every other machine.9 Unfortunately, Babbage never completed building the machine of his dreams, although he
…
central to computer theory. When a machine can simulate every other machine this is called ‘Turing complete’. We saw how Babbage’s Analytical Engine was the first ‘Turing complete’ machine in the world. Our modern computers are also Turing complete. But to get from the Analytical Engine to modern computers required a giant leap in the
…
Atlantic, the Americans were also developing their own electronic computational machines, culminating in the design and construction of ENIAC (1946),6 an electronic, programmable and Turing-complete machine that was used for artillery-timing tables for the US Army’s Ballistic Research Laboratory. ENIAC represented a watershed in computer history. Its architecture
…
. In the early 1980s, the English mathematician Stephen Wolfram conjectured that a particular cellular automaton called ‘Rule 110’ might be ‘Turing complete’,21 a conjecture that was later proved by Matthew Cook. ‘Turing complete’ means that Rule 110 is capable of universal computation, i.e. any calculation or computer program can be simulated using
…
a general law for biology. However, we have discovered something that seems to point towards such a law: Rule 110, a recursive algorithm that is Turing complete and lifelike – and there might be more.23 This profound correlation between cellular automata and biological phenomena suggests that life is governed by recursive computations
…
Turing invents the ‘Turing machine’. 1938: Claude Shannon demonstrates that symbolic logic can be implemented using electronic relays. 1941: Konrad Zuse constructs Z3, the first Turing-complete computer. 1942: Alan Turing and Claude Shannon work together at Bell Labs. 1943: Warren McCulloch and Walter Pitts demonstrate the equivalence between electronics and neurons
…
Joseph Marie Charles, nicknamed Jacquard. It was based on an earlier invention by the master of automata, Jacques Vaucanson – of mechanical duck fame. 9The next ‘Turing-complete’ machine after the Analytical Engine would be ENIAC, which was constructed in 1946. 10Ada Lovelace called her notes simply ‘Notes’. 11The Bernoulli numbers are a
…
. 20Rebeck, J. (1994), ‘Synthetic Self-Replicating Molecules’, in: Scientific American, July 1994, pp. 48–55. 21Wolfram had conjectured that Rule 110 was Turing complete. Proof that Rule 110 is Turing complete was published by Matthew Cook. The proof is found in: Wolfram, S. (2002), A New Kind of Science, Wolfram Media. 22Or a transition
…
an ecosystem. 23There exist 88 possible unique elementary cellular automata, but only Rule 110 has been proven to be Turing complete so far. It is possible that other unique cellular automata are also Turing complete, but more complex. 24Baron-Cohen, S. (1997), Mindblindness: an essay on autism and theory of mind, New York: MIT
The Stack: On Software and Sovereignty
by Benjamin H. Bratton · 19 Feb 2016 · 903pp · 235,753 words
of billions of Users, the interfacial image is also partially a function of sheer machinic quantity. With the comparatively instantaneous adoption of mobile devices (a Turing complete processor + camera + homing tether + telephonic voice relay), we have seen an explosion in the absolute volume of mechanical images of and in the world, dwarfing
How to Create a Mind: The Secret of Human Thought Revealed
by Ray Kurzweil · 13 Nov 2012 · 372pp · 101,174 words
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). A block diagram of a
…
electronic calculator called Bombe that helped decode messages that had been encrypted by the Nazi Enigma coding machine. By 1943, an engineering team influenced by Turing completed what is arguably the first computer, the Colossus, that enabled the Allies to continue decoding messages from more sophisticated versions of Enigma. The Bombe and
Coders at Work
by Peter Seibel · 22 Jun 2009 · 1,201pp · 233,519 words
on their hind legs and TeX can calculate prime numbers.” Seibel: But people use the fact that it's a Turing-complete programming language to do typesetting-related computations. If it wasn't Turing-complete they would be unable to do those things. Knuth: Yeah, that's right. I wrote a programming language for
Think Complexity
by Allen B. Downey · 23 Feb 2012 · 247pp · 43,430 words
this topic in Free Will. Structures The behavior of Class 4 CAs is even more surprising. Several 1-D CAs, most notably Rule 110, are Turing complete, which means that they can compute any computable function. This property, also called universality, was proved by Matthew Cook in 1998. See http://en.wikipedia
…
. 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
…
interesting stable patterns: some oscillate (with various periods), and some move like the spaceships in Wolfram’s Rule 110 CA. Like Rule 110, GoL is Turing complete. Conway posed an intriguing conjecture—that there is no initial condition that yields unbounded growth in the number of live cells—and offered $50 to
…
we believe Wolfram’s Principle of Computational Equivalence, we expect GoL to be in Class 4, and it is. The Game of Life was proved Turing complete in 1982 (and again, independently, in 1983). Since then, several people have constructed GoL patterns that implement a Turing machine or another machine known to
…
be Turing complete. Example 7-3. Many named patterns are available in portable file formats. Modify Life.py to parse one of these formats and initialize the grid
…
jam, Traffic Jams traverse list, List Comprehensions TreeMap, Hashtables triangle of influence, Stephen Wolfram tuple methods, Analysis of Basic Python Operations tuple type, Representing Graphs Turing complete, Structures, Game of Life, Conway’s Conjecture Turing machine, Universality Turing, Alan, Universality, Turmites turmite, Turmites Turtles, Termites, and Traffic Jams, Traffic Jams U U
Turing's Vision: The Birth of Computer Science
by Chris Bernhardt · 12 May 2016 · 210pp · 62,771 words
given any algorithm, there is a tag system that computes it. This fact is sometimes expressed in the literature by saying that tag systems are Turing complete. It has even been shown that you only ever need to consider systems that drop the first two letters — 2-tag systems — to get
…
Turing completeness.10 Given an algorithm, we can in theory design a Turing machine that implements it, and then convert to a tag system. However, the resulting
…
of the rules could be considered as algorithms for computations. Surprisingly, they can also simulate universal Turing machines. Stephen Wolfram conjectured that Rule 110 was Turing complete. This is one of the rules that shows a mixture of chaos and stability depending on the starting tape. For some starting tapes the rule
…
computer science. As Robert Soare has commented, you can think of your laptop being a Turing machine and the oracle as being the web. After Turing completed his Ph.D., von Neumann offered him a position as his assistant, but Turing decided not to accept and instead returned to England. During the
…
, 153, 155 String, 27 Successor function, 73, 76, 77 Tag systems, 16, 71, 79, 103 Traps, 34 Tunny, 152 Turing, Alan, 1, 11, 145, 147 Turing complete, 80 Turing machine, 48 Turing test, 157, 158, 163 Ulam, Stanisław, 148, 164 Ullman, Jeffrey, 165 Unary alphabet, 29 Unary notation, 59 Uncomputable function, 119
The Art of UNIX Programming
by Eric S. Raymond · 22 Sep 2003 · 612pp · 187,431 words
expertise baked into them. Some task-specific imperative minilanguages start to border on being general-purpose interpreters. They reach this level when they are explicitly Turing-complete—that is, they can do both conditionals and loops (or recursion)[80] with features that are designed to be used as control structures. Some languages
…
, by contrast, are only accidentally Turing-complete — they have features that can be used to implement control structures as a sort of side effect of what they are actually designed to do
…
. The bc(1) and dc(1) interpreters we looked at in Chapter 7 are good examples of specialized imperative minilanguages that are explicitly Turing-complete. We are over the border into general-purpose interpreters when we reach languages like Emacs Lisp and JavaScript that are designed to be full programming
…
many other kinds of derivation; makefiles can express almost all of them. [80] Any Turing-complete language could theoretically be used for general-purpose programming, and is theoretically exactly as powerful as any other Turing-complete language. In practice, some Turing-complete languages would be far too painful to use for anything outside a specified and
…
', `operating system') The m4 macro language supports conditionals and recursion. The combination can be used to implement loops, and this was intended; m4 is deliberately Turing-complete. But actually trying to use m4 as a general-purpose language would be deeply perverse. The m4 macro processor is usually employed as a preprocessor
…
. XSLT is described by a World Wide Web Consortium standard and has several open-source implementations. XSLT and m4 macros are both purely declarative and Turing-complete, but XSLT supports only recursions and not loops. It is quite complex, certainly the most difficult language to master of any in this chapter's
…
good example of an imperative minilanguage that borders on being a full-fledged interpreter (it has conditionals and recursion but not loops; it is accidentally Turing-complete). The postprocessors (‘drivers’ in DWB terminology) are normally not visible to troff users. The original troff emitted codes for the particular typesetter the Unix development
…
C, with variables and conditionals and loops and an ontology of types including integers, strings, and (unlike C) dictionaries.[89] The awk action language is Turing-complete, and can read and write files. In some versions it can open and use network sockets. But awk has primarily seen use as a report
…
images written in it are far smaller than the bitmaps they render to, and so take up less storage and communication bandwidth. PostScript is explicitly Turing-complete, supporting conditionals and loops and recursion and named procedures. The ontology of types includes integers, reals, strings, and arrays (each element of an array may
…
'll return to the importance of the Rule of Least Surprise in interfaces in Chapter 11. These minilanguages have both conditionals and loops; they are Turing-complete, but have a very restricted ontology of types including only unlimited-precision integers and strings. This puts them in the borderland between interpreted minilanguages and
…
executable code in Web pages to be run by any JavaScript-capable browser. That is the version we will survey here. JavaScript is a fully Turing-complete interpreted language with integers, real numbers, booleans, strings, and lightweight dictionary-based objects resembling those of Python. Values are typed, but variables can hold any
…
problem are weak, ad-hoc control structures and poor or nonexistent facilities for declaring procedures. It's risky to design minilanguages that are only accidentally Turing-complete. If you do this the odds are good that, sometime in the future, some clever fellow is going to think he needs to press your
…
; more powerful ones can actually get you in worse trouble. The TeX formatting language (see Chapter 18) well illustrates the general problem. TeX is intentionally Turing-complete (it has conditionals, loops, and recursion), but while it can be made to do amazing things, TeX code tends to be unreadable and painful to
Accelerando
by Stross, Charles · 22 Jan 2005 · 489pp · 148,885 words
use the bidet. Everything is crystal clear, and her touch is electrifying. While she showers, he sits on the toilet seat lid and rants about Turing-completeness as an attribute of company law, about cellular automata and the blind knapsack problem, about his work on solving the Communist Central Planning problem using
…
legal instrument – about ninety percent of it, in fact – is a set of self-modifying corporate mechanisms coded in a variety of jurisdictions that permit Turing-complete company constitutions, and which act as an ownership shell for the slavery contract. At the far end of the corporate shell game is a trust
Filterworld: How Algorithms Flattened Culture
by Kyle Chayka · 15 Jan 2024 · 321pp · 105,480 words
computational system that can compute anything that a Turing Machine can is said to be “Turing-complete.” All programming languages, for example, are Turing-complete because they can model any kind of equation. (Even the spreadsheet software Excel became Turing-complete in 2021.) What Turing correctly concluded was that any computing machine would be able to
The Innovators: How a Group of Inventors, Hackers, Geniuses and Geeks Created the Digital Revolution
by Walter Isaacson · 6 Oct 2014 · 720pp · 197,129 words
Silence on the Wire: A Field Guide to Passive Reconnaissance and Indirect Attacks
by Michal Zalewski · 4 Apr 2005 · 412pp · 104,864 words
Ways of Being: Beyond Human Intelligence
by James Bridle · 6 Apr 2022 · 502pp · 132,062 words
Einstein's Fridge: How the Difference Between Hot and Cold Explains the Universe
by Paul Sen · 16 Mar 2021 · 444pp · 111,837 words
When Einstein Walked With Gödel: Excursions to the Edge of Thought
by Jim Holt · 14 May 2018 · 436pp · 127,642 words
Mastering Ethereum: Building Smart Contracts and DApps
by Andreas M. Antonopoulos and Gavin Wood Ph. D. · 23 Dec 2018 · 960pp · 125,049 words
Engineering Security
by Peter Gutmann
Augmented: Life in the Smart Lane
by Brett King · 5 May 2016 · 385pp · 111,113 words
Life After Google: The Fall of Big Data and the Rise of the Blockchain Economy
by George Gilder · 16 Jul 2018 · 332pp · 93,672 words
Blockchain: Blueprint for a New Economy
by Melanie Swan · 22 Jan 2014 · 271pp · 52,814 words
Mastering Blockchain, Second Edition
by Imran Bashir · 28 Mar 2018
Concepts, Techniques, and Models of Computer Programming
by Peter Van-Roy and Seif Haridi · 15 Feb 2004 · 931pp · 79,142 words
Blockchain Revolution: How the Technology Behind Bitcoin Is Changing Money, Business, and the World
by Don Tapscott and Alex Tapscott · 9 May 2016 · 515pp · 126,820 words
The Infinite Machine: How an Army of Crypto-Hackers Is Building the Next Internet With Ethereum
by Camila Russo · 13 Jul 2020 · 349pp · 102,827 words
Rationality: From AI to Zombies
by Eliezer Yudkowsky · 11 Mar 2015 · 1,737pp · 491,616 words
Masterminds of Programming: Conversations With the Creators of Major Programming Languages
by Federico Biancuzzi and Shane Warden · 21 Mar 2009 · 496pp · 174,084 words
On the Edge: The Art of Risking Everything
by Nate Silver · 12 Aug 2024 · 848pp · 227,015 words
More Everything Forever: AI Overlords, Space Empires, and Silicon Valley's Crusade to Control the Fate of Humanity
by Adam Becker · 14 Jun 2025 · 381pp · 119,533 words
The Truth Machine: The Blockchain and the Future of Everything
by Paul Vigna and Michael J. Casey · 27 Feb 2018 · 348pp · 97,277 words
Enshittification: Why Everything Suddenly Got Worse and What to Do About It
by Cory Doctorow · 6 Oct 2025 · 313pp · 94,415 words
This Will Make You Smarter: 150 New Scientific Concepts to Improve Your Thinking
by John Brockman · 14 Feb 2012 · 416pp · 106,582 words
Cryptoassets: The Innovative Investor's Guide to Bitcoin and Beyond: The Innovative Investor's Guide to Bitcoin and Beyond
by Chris Burniske and Jack Tatar · 19 Oct 2017 · 416pp · 106,532 words
Attack of the 50 Foot Blockchain: Bitcoin, Blockchain, Ethereum & Smart Contracts
by David Gerard · 23 Jul 2017 · 309pp · 54,839 words
The Age of Cryptocurrency: How Bitcoin and Digital Money Are Challenging the Global Economic Order
by Paul Vigna and Michael J. Casey · 27 Jan 2015 · 457pp · 128,838 words
Types and Programming Languages
by Benjamin C. Pierce · 4 Jan 2002 · 647pp · 43,757 words
The Business Blockchain: Promise, Practice, and Application of the Next Internet Technology
by William Mougayar · 25 Apr 2016 · 161pp · 44,488 words
Lurking: How a Person Became a User
by Joanne McNeil · 25 Feb 2020 · 239pp · 80,319 words
Track Changes
by Matthew G. Kirschenbaum · 1 May 2016 · 519pp · 142,646 words
Practical OCaml
by Joshua B. Smith · 30 Sep 2006
Beautiful Architecture: Leading Thinkers Reveal the Hidden Beauty in Software Design
by Diomidis Spinellis and Georgios Gousios · 30 Dec 2008 · 680pp · 157,865 words
Haskell Programming: From First Principles
by Christopher Allen and Julie Moronuki · 1 Jan 2015 · 1,076pp · 67,364 words
The Cryptopians: Idealism, Greed, Lies, and the Making of the First Big Cryptocurrency Craze
by Laura Shin · 22 Feb 2022 · 506pp · 151,753 words
Chokepoint Capitalism
by Rebecca Giblin and Cory Doctorow · 26 Sep 2022 · 396pp · 113,613 words
Clojure Programming
by Chas Emerick, Brian Carper and Christophe Grand · 15 Aug 2011 · 999pp · 194,942 words
Software Engineering at Google: Lessons Learned From Programming Over Time
by Titus Winters, Tom Manshreck and Hyrum Wright · 17 Mar 2020 · 214pp · 31,751 words
Confessions of a Crypto Millionaire: My Unlikely Escape From Corporate America
by Dan Conway · 8 Sep 2019 · 218pp · 68,648 words
Bitcoin: The Future of Money?
by Dominic Frisby · 1 Nov 2014 · 233pp · 66,446 words
Bitcoin Internals: A Technical Guide to Bitcoin
by Chris Clark · 16 Jun 2013 · 52pp · 13,257 words