← Back to catalogue
Research draft

Turing machine

vr.tr.turing-machine · INF.KNW

Let an agent explain Turing machines and their variants, relay the model, the Church-Turing thesis and key results from computability references, describe their role in complexity theory, and distinguish Turing machines from finite automata and real computers.

Thing Registry Information and virtual systems

Research draft, second pass

A second pass drafted this model: the structure a model of this thing needs, and what is known about it in the world. The line under this one says how the second half was obtained - researched against sources, or recalled without web access, in which case nothing here was read anywhere and every claim is a lead to verify. Unreviewed either way.

written by Claude from model knowledge without web access - no source was read, every claim is a lead to verify

Researched by: Claude

Purpose and description

Let an agent explain Turing machines and their variants, relay the model, the Church-Turing thesis and key results from computability references, describe their role in complexity theory, and distinguish Turing machines from finite automata and real computers.

An abstract mathematical model of computation introduced by Alan Turing in 1936, consisting of an infinite tape of cells, a head that reads and writes symbols and moves left or right, and a finite set of states with transition rules, capable of computing anything computable according to the Church-Turing thesis, with variants such as multitape, non-deterministic and Post-Turing machines, the universal Turing machine that simulates any other, deciders that always halt, and the busy beaver problem on maximal behaviour; Turing machines define computability and complexity classes.

What it is for: Not applicable; a theoretical model.

It can be explain the model; relay variants and results; describe role in complexity; distinguish from other models.

Distinguishing features

Unbounded tape

Finite control

Universality

Halting undecidability

What it looks like

Not a visible object; a tape, head and state table in diagrams.

Physical character

introduced: 1936 year - On Computable Numbers

busy beaver BB(5): 47176870 steps - proved 2024

How it is recognised

Abstract tape-and-head computing model

Deterministic, non-deterministic, multitape, universal, Post-Turing machines; deciders; busy beaver

Finite automata lack unbounded memory; lambda calculus is an equivalent model; real computers have finite memory

Related models

is a kind of - in registry terms

non-finite-state machine

was introduced by - in 1936

Alan Turing

underlies - on computability

Church-Turing thesis

defines - classes such as P and NP

computational complexity theory

In practice

Families and kinds

deterministic single-tape Turing machines

multitape Turing machines

non-deterministic Turing machines

universal Turing machines

deciders and recognisers

Post-Turing machines

busy beaver machines

oracle and probabilistic Turing machines

Standards and regulation

No regulation; standard definitions in computability theory

Failure modes and hazards

Confusing Turing machines with finite automata

Misreading the Church-Turing thesis as a theorem

Assuming real computers are Turing complete in the strict sense

Also called

non-deterministic Turing machinemultitape Turing machinebusy beaverdeciderPost–Turing machineuniversal Turing machineTurmiteAlternating Turing machinerandom-access Turing machineread-only Turing machineread-only right moving Turing machinesquantum Turing machineSymmetric Turing machinenon-ambiguous Turing machinelinear bounded automatonprobabilistic Turing machineunambiguous Turing machine

Where this came from

wikidata · CC0 1.0

Source repository Registry entry point

Drafted structure

Bundle to layer to finding to question, as the second pass will find it: 4 bundles · 8 layers · 8 findings · 16 questions.

Understand What a Turing machine is.

Mathematics.

Definition

Definition.

Definition

Definition.

  1. What is a Turing machine, and how do tape, head, states and transitions work? definition
  2. Is the question about Turing machines, finite automata or another model of computation? boundary

Variants

Variants.

Variants

Variants.

  1. How do multitape, non-deterministic, universal and Post-Turing machines relate, and what is a decider? definition
  2. Which entry fits the specific variant? action
Theory Computability.

Mathematics.

Computability

Computability and halting.

Computability

Computability.

  1. What is the Church-Turing thesis, and why is the halting problem undecidable? provenance
  2. Which references are standard? provenance

Busy beaver

Busy beaver.

Busy beaver

Busy beaver.

  1. What is the busy beaver function, and what values are known? provenance
  2. Which entry fits busy beaver? action
Complexity Complexity.

Mathematics.

Classes

Complexity classes.

Classes

Classes.

  1. How do Turing machines define time and space complexity and classes such as P, NP and PSPACE? provenance
  2. Which sources are cited? provenance

Simulation

Simulation and equivalence.

Simulation

Simulation.

  1. How do variants simulate each other, and what does that show about robustness of the model? provenance
  2. Which entry fits computational complexity theory? action
Context History and teaching.

Context.

History

History.

History

History.

  1. How did Turing, Church, Post and others develop the model, and how did it shape computing? provenance
  2. Which entry fits the history of computer science? action

Teaching

Teaching and simulators.

Teaching

Teaching.

  1. How are Turing machines taught, and what simulators and physical models exist? provenance
  2. Which entry fits theory of computation education? action

What the second pass must settle

  • Should universal Turing machine and busy beaver be separate primary entries?
  • How should computability references be linked?
  • The registry entry has merged aliases naming variants and problems; should they be split off?
Draft as JSON