Turing machine
An abstract model of a classical (non-quantum) computer; the theoretical basis for what ordinary computers can compute.
As defined in lex_demis-hassabis-2
Where it comes up · 33
- The Grand Theory of Intelligence – Gwern7 claims
- The future of intelligence | Demis Hassabis (Co-founder and CEO of DeepMind)5 claims
- Sir Demis Hassabis on The Future of Knowledge | Institute for Advanced Study4 claims
- 155 | Stephen Wolfram on Computation, Hypergraphs, and Fundamental Physics3 claims
- 282 | Joel David Hamkins on Puzzles of Reality and Infinity3 claims
- AMA | August 20213 claims
- Scott Aaronson - Quantum Computing, Complexity, and Creativity3 claims
- Stephen Wolfram's Take on Artificial Intelligence & The Future of Humanity2 claims
and 25 more
Most important claims · 10 of 60Search all claims for “Turing machine” →
- Von Neumann showed in 1951, before the structure of DNA was known, that open-ended self-replication and evolution require a Turing tape carrying instructions for building oneself, a machine A that reads the tape and builds what it specifies, and a machine B that copies the tape — anticipating the roles of DNA, ribosomes, and DNA polymerase respectively.286 | Blaise Agüera y Arcas on the Emergence of Replication and Computation
- Colored tile sets that bind only when colors match can be designed to simulate Turing machines and cellular automata, following Hao Wang's aperiodic tiling work, so physical molecular tapestries can embody algorithmic self-assembly grounded in mathematical tiling theory.372 | Erik Winfree on DNA Computers and Robots
- In John Conway's Game of Life (a deterministic cellular automaton with simple rules), gliders emerge as stable moving patterns that don't exist in the physics of the world (which only has individual on/off cells) but that our visual system interprets as objects; you cannot invent a Turing machine using gliders without believing gliders are real, despite everything being determined by micro-level physics.Agency, Attractors, & Observer-Dependent Computation in Biology & Beyond
- Although the halting problem is undecidable, it has a 'black hole': there is a computable procedure that correctly decides almost every instance, because the asymptotic density of programs whose head falls off the tape (via random-walk behavior, by Pólya's recurrence theorem) before repeating a state goes to 100% as the number of states grows.Joel David Hamkins
- Set theories that determine more and more busy beaver numbers must become more and more complicated (e.g. via large cardinal axioms asserting larger infinities), and there is no surefire systematic way to discover such axioms while being confident they remain consistent — sometimes proposed large cardinal axioms turn out inconsistent.Scott Aaronson - Quantum Computing, Complexity, and Creativity
- The busy beaver function BB(n) is defined as the largest finite number of steps any n-state Turing machine can run before halting (on a blank input), and it provably grows faster than any computable function, so naming BB(1000) would utterly defeat any opponent in a largest-number contest who doesn't know the function.Scott Aaronson - Quantum Computing, Complexity, and Creativity
- All intelligence is search over Turing machines: anything that happens can be described by Turing machines of various lengths, and learning or scaling is simply searching over more and longer Turing machines and applying them case by case; there is no general master algorithm or special 'intelligence fluid', just a tremendous number of learned special cases encoded into the brain.Gwern — Anonymous writer who predicted AI trajectory on $12K/year salary
- Computational models like the Turing machine constitute a distinct scientific mode of acquiring knowledge: a good model has robustness, meaning its captured notion does not change when small parts of the definition are altered, and educability is offered as satisfying this robustness criterion, justifying it as a scientific approach even without direct human experiments.272 | Leslie Valiant on Learning and Educability in Computers and People
- The principles Alan Turing laid out in 1936 for how general computing devices are possible turn out to be exactly the principles hackers exploit, meaning the very things that make computers possible make hacking possible.238 | Scott Shapiro on the Technology and Philosophy of Hacking
- Because a computer can compute anything computable, human tasks like driving and diagnosis are computation that machines will do phenomenally well, with a diagnostic system likely to outperform humans soon.World After Capital