Turing machines
Abstract computational models consisting of a tape, a read/write head, and a state machine that can implement any algorithm; used to study fundamental limits of computability
As defined in What We've Learned from NKS 20 Years Later: The Making and Current State of NKS [Part 1]
Where it comes up · 1
Most important claims · 3 of 3Search all claims for “Turing machines” →
- Simple-rule complexity was initially observed only in cellular automata, but in September 1991 Wolfram systematically tested other computational systems (Turing machines, tag systems, generalized mobile automata) and discovered that complex behavior from simple rules was a ubiquitous phenomenon, not restricted to cellular automata.What We've Learned from NKS 20 Years Later: The Making and Current State of NKS [Part 1]
- One of the most complex diagrams in NKS shows evidence that satisfiability is equivalent to non-deterministic Turing machines, which Wolfram describes as 'probably a bit of an extreme overkill type self-explanatory diagram', suggesting that the principle of self-explanatory diagrams could sometimes become over-elaborate.What We've Learned from NKS 20 Years Later: The Making and Current State of NKS [Part 1]
- By early 1992, Wolfram had written hundreds of pages for NKS with substantial sections on cellular automata, substitution systems, mobile automata, and neighbor-dependent substitution systems; the table of contents at that time was still organized around a 'complexity-driven story' rather than the computational paradigm emphasis that would later dominate.What We've Learned from NKS 20 Years Later: The Making and Current State of NKS [Part 1]