{ "model": { "rank": 4508, "code": "thing-q163310", "model_id": "vr.tr.turing-machine", "name": "Turing machine", "purpose": "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.", "family": "Thing Registry", "category": "Information and virtual systems", "status": "research-draft", "kind": "thing", "plane": "INF", "domain": "INF.KNW", "industry": "", "version": "", "url": "/models/thing/q163310/", "tier": 2, "score": 75, "payload": { "layer": "wikidata", "aliases": [ "non-deterministic Turing machine", "multitape Turing machine", "busy beaver", "decider", "Post–Turing machine", "universal Turing machine", "Turmite", "Alternating Turing machine", "random-access Turing machine", "read-only Turing machine", "read-only right moving Turing machines", "quantum Turing machine", "Symmetric Turing machine", "non-ambiguous Turing machine", "linear bounded automaton", "probabilistic Turing machine", "unambiguous Turing machine" ], "aliasCount": 17, "merged": 17, "knownIn": 75, "facets": null, "markers": [], "lexicalClass": "", "senseRank": null, "alsoRegisteredAs": null, "source": { "dataset": "wikidata", "item": "Q163310", "url": "https://www.wikidata.org/wiki/Q163310", "license": "CC0 1.0" } }, "research": { "vercy": "1.0-draft", "publication": { "status": "research-draft", "adjudicationStatus": "unreviewed", "publishableCanonical": false, "generatedAt": "2026-09-13T03:46:20Z", "providers": [ "Claude" ], "breadth": "written by Claude from model knowledge without web access - no source was read, every claim is a lead to verify", "pass": 2, "wave": 3, "engine": "claude" }, "metaModel": { "id": "THING-Q163310", "registryId": "vr.tr.turing-machine", "name": "Turing machine", "version": "0.2.0-wave.3", "entryKind": "thing", "family": "Thing Registry", "domain": [ "INF.KNW" ], "status": "research-draft" }, "canonicalUrl": "https://ver.cy/models/thing/q163310/", "model": { "registry_id": "vr.tr.turing-machine", "name": "Turing machine", "purpose": "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.", "definition": "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.", "affordances": [ "explain the model", "relay variants and results", "describe role in complexity", "distinguish from other models" ], "distinguishing_features": [ "Unbounded tape", "Finite control", "Universality", "Halting undecidability" ], "appearance": "Not a visible object; a tape, head and state table in diagrams.", "visual_identification": [ "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" ], "physical_properties": [ { "quantity": "introduced", "typical_range": "1936", "unit": "year", "note": "On Computable Numbers" }, { "quantity": "busy beaver BB(5)", "typical_range": "47176870", "unit": "steps", "note": "proved 2024" } ], "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" ], "related_models": [ { "relation": "is a kind of", "target": "non-finite-state machine", "why": "in registry terms" }, { "relation": "was introduced by", "target": "Alan Turing", "why": "in 1936" }, { "relation": "underlies", "target": "Church-Turing thesis", "why": "on computability" }, { "relation": "defines", "target": "computational complexity theory", "why": "classes such as P and NP" } ], "identifiers": [], "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" ], "in_scope": [], "out_of_scope": [], "characteristics": [] }, "sources": [], "structure": { "bundles": [ { "id": "understand", "name": "Understand", "description": "What a Turing machine is.", "rationale": "Mathematics.", "layers": [ { "id": "definition", "name": "Definition", "description": "Definition.", "findings": [ { "id": "definition-finding", "name": "Definition", "description": "Definition.", "questions": [ { "text": "What is a Turing machine, and how do tape, head, states and transitions work?", "kind": "definition" }, { "text": "Is the question about Turing machines, finite automata or another model of computation?", "kind": "boundary" } ] } ] }, { "id": "variants", "name": "Variants", "description": "Variants.", "findings": [ { "id": "variants-finding", "name": "Variants", "description": "Variants.", "questions": [ { "text": "How do multitape, non-deterministic, universal and Post-Turing machines relate, and what is a decider?", "kind": "definition" }, { "text": "Which entry fits the specific variant?", "kind": "action" } ] } ] } ] }, { "id": "theory", "name": "Theory", "description": "Computability.", "rationale": "Mathematics.", "layers": [ { "id": "computability", "name": "Computability", "description": "Computability and halting.", "findings": [ { "id": "computability-finding", "name": "Computability", "description": "Computability.", "questions": [ { "text": "What is the Church-Turing thesis, and why is the halting problem undecidable?", "kind": "provenance" }, { "text": "Which references are standard?", "kind": "provenance" } ] } ] }, { "id": "busybeaver", "name": "Busy beaver", "description": "Busy beaver.", "findings": [ { "id": "busybeaver-finding", "name": "Busy beaver", "description": "Busy beaver.", "questions": [ { "text": "What is the busy beaver function, and what values are known?", "kind": "provenance" }, { "text": "Which entry fits busy beaver?", "kind": "action" } ] } ] } ] }, { "id": "complexity", "name": "Complexity", "description": "Complexity.", "rationale": "Mathematics.", "layers": [ { "id": "classes", "name": "Classes", "description": "Complexity classes.", "findings": [ { "id": "classes-finding", "name": "Classes", "description": "Classes.", "questions": [ { "text": "How do Turing machines define time and space complexity and classes such as P, NP and PSPACE?", "kind": "provenance" }, { "text": "Which sources are cited?", "kind": "provenance" } ] } ] }, { "id": "simulation", "name": "Simulation", "description": "Simulation and equivalence.", "findings": [ { "id": "simulation-finding", "name": "Simulation", "description": "Simulation.", "questions": [ { "text": "How do variants simulate each other, and what does that show about robustness of the model?", "kind": "provenance" }, { "text": "Which entry fits computational complexity theory?", "kind": "action" } ] } ] } ] }, { "id": "context", "name": "Context", "description": "History and teaching.", "rationale": "Context.", "layers": [ { "id": "history", "name": "History", "description": "History.", "findings": [ { "id": "history-finding", "name": "History", "description": "History.", "questions": [ { "text": "How did Turing, Church, Post and others develop the model, and how did it shape computing?", "kind": "provenance" }, { "text": "Which entry fits the history of computer science?", "kind": "action" } ] } ] }, { "id": "teaching", "name": "Teaching", "description": "Teaching and simulators.", "findings": [ { "id": "teaching-finding", "name": "Teaching", "description": "Teaching.", "questions": [ { "text": "How are Turing machines taught, and what simulators and physical models exist?", "kind": "provenance" }, { "text": "Which entry fits theory of computation education?", "kind": "action" } ] } ] } ] } ] }, "openQuestions": [ "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?" ], "statistics": { "bundles": 4, "layers": 8, "findings": 8, "questions": 16 } }, "draft": { "generator": "vr.draft.v3", "status": "draft-generated", "researched": false, "archetype": "discipline or field of knowledge", "method": "Written from the archetype playbook - what this kind of thing needs beyond identity and provenance - and from the structure that recurred across 6,333 models already researched by two engines. Applied to this entry by rule. No source was read for this thing and no claim here is researched. This entry carries no facets of its own, so they were inferred from its domain - a guess about a whole domain applied to one thing.", "facetsInferred": true, "nextPass": "A researcher replaces this draft with a sourced specification. Treat every sentence below as a proposal to argue with.", "purpose": "Give an agent a durable, checkable way to recognise a Turing machine, record what state it is in, and decide what may be done with it.", "whatItIs": "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.", "characteristics": { "substance": "information", "origin": "conceptual", "agency": "inert" }, "whatYouCanDoWithIt": [ "read and interpreted" ], "distinguishingFeatures": [ "Names folded into this entry, which a task may need to split apart again: non-deterministic Turing machine, multitape Turing machine, busy beaver, decider, Post–Turing machine, universal Turing machine, Turmite, Alternating Turing machine, random-access Turing machine, read-only Turing machine, read-only right moving Turing machines, quantum Turing machine.", "17 finer distinctions are held as aliases rather than separate entries, because telling them apart needs a task that asks for it.", "Described in 75 Wikipedia languages, which is a measure of how widely the thing is known, not of how important it is." ], "openQuestionsForResearch": [ "Which of the bundles below does a real task actually need, and which are ceremony?", "What does this thing have that the facets do not capture at all?", "Which neighbouring kind is most often confused with a Turing machine, and on what evidence are they told apart?" ], "whatItIsMadeOf": "content that has to be carried by something else", "physicalCharacter": [ "Does nothing on its own; everything it does, something else did to it.", "These come from the domain this entry sits in rather than from the entry itself, so treat them as a first guess about the whole domain applied to one thing." ], "whatCanBeDoneWithIt": [ "read it and act on what it says" ], "howItIsRecognised": [], "relatedModels": [ { "relation": "covers", "note": "Finer kinds folded into this entry because telling them apart needs a task that asks for it. Each is a model waiting to be split out when one does.", "targets": [ "non-deterministic Turing machine", "multitape Turing machine", "busy beaver", "decider", "Post–Turing machine", "universal Turing machine", "Turmite", "Alternating Turing machine", "random-access Turing machine", "read-only Turing machine", "read-only right moving Turing machines", "quantum Turing machine" ] } ], "standing": "Described in 75 Wikipedia languages, which measures how widely it is written about rather than how important or how common it is. 17 finer distinctions are held inside this entry as names rather than as separate models.", "structure": { "bundles": [ { "id": "identity-and-classification", "name": "Identity, naming and classification", "description": "How an agent tells one Turing machine from another, and a Turing machine from things that resemble it.", "rationale": "Recognition comes before every other claim. Without stable identity nothing else in the model can be trusted to be about the same thing twice.", "layers": [ { "id": "naming-and-identifiers", "name": "Names and identifiers", "description": "The names this thing goes by and the identifiers that survive translation and time.", "findings": [ { "id": "preferred-name-and-aliases", "name": "Preferred name, aliases and local names", "description": "Which name to use, which names mean the same thing, and which merely sound similar.", "questions": [ { "id": "preferred-name-and-aliases-q01", "text": "What identifies and describes the name of a Turing machine, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "preferred-name-and-aliases-q02", "text": "Who or what asserted this about the name of a Turing machine, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "preferred-name-and-aliases-q03", "text": "What may an agent decide or do once the name of a Turing machine is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] }, { "id": "stable-identifiers", "name": "Stable identifiers and external keys", "description": "Identifiers that keep pointing at this kind of thing across systems and languages.", "questions": [ { "id": "stable-identifiers-q01", "text": "What identifies and describes an identifier for a Turing machine, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "stable-identifiers-q02", "text": "Who or what asserted this about an identifier for a Turing machine, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "stable-identifiers-q03", "text": "What may an agent decide or do once an identifier for a Turing machine is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] } ] }, { "id": "classification-and-granularity", "name": "Classification and granularity", "description": "Where a Turing machine sits among kinds, and how finely a task needs to cut it.", "findings": [ { "id": "kind-and-parents", "name": "Kind, parents and neighbouring kinds", "description": "The classes this thing belongs to and the ones it is next to.", "questions": [ { "id": "kind-and-parents-q01", "text": "What identifies and describes the kind of a Turing machine, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "kind-and-parents-q02", "text": "Who or what asserted this about the kind of a Turing machine, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "kind-and-parents-q03", "text": "What may an agent decide or do once the kind of a Turing machine is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] }, { "id": "distinguishing-features", "name": "Distinguishing features", "description": "What separates a Turing machine from the things most often confused with it.", "questions": [ { "id": "distinguishing-features-q01", "text": "What identifies and describes what distinguishes a Turing machine, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "distinguishing-features-q02", "text": "Who or what asserted this about what distinguishes a Turing machine, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "distinguishing-features-q03", "text": "What may an agent decide or do once what distinguishes a Turing machine is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] } ] } ] }, { "id": "state-and-lifecycle", "name": "State and lifecycle", "description": "The states a Turing machine passes through and the events that move it between them.", "rationale": "Most decisions about a thing depend on what state it is in now, which is a claim with a time on it, not a property.", "layers": [ { "id": "lifecycle-stages", "name": "Lifecycle stages", "description": "From coming into existence to ceasing to be one of these.", "findings": [ { "id": "stages-and-transitions", "name": "Stages and transitions", "description": "The stages worth naming and what moves a Turing machine between them.", "questions": [ { "id": "stages-and-transitions-q01", "text": "What identifies and describes the lifecycle of a Turing machine, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "stages-and-transitions-q02", "text": "Who or what asserted this about the lifecycle of a Turing machine, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "stages-and-transitions-q03", "text": "What may an agent decide or do once the lifecycle of a Turing machine is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] } ] }, { "id": "observations-and-status", "name": "Observations and current status", "description": "What is observed about a Turing machine, how often and by whom.", "findings": [ { "id": "observation-record", "name": "Observation record", "description": "How an observation of a Turing machine is recorded so that it can be superseded rather than overwritten.", "questions": [ { "id": "observation-record-q01", "text": "What identifies and describes an observation of a Turing machine, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "observation-record-q02", "text": "Who or what asserted this about an observation of a Turing machine, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "observation-record-q03", "text": "What may an agent decide or do once an observation of a Turing machine is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] } ] } ] }, { "id": "content-and-access", "name": "Content, encoding and access", "description": "What a Turing machine says, how it is encoded and who may read it.", "rationale": "An informational thing carries content that can be copied, versioned and withheld, none of which its physical carrier explains.", "layers": [ { "id": "content-and-encoding", "name": "Content and encoding", "description": "The content itself, its format and its language.", "findings": [ { "id": "content-and-format", "name": "Content, format and language", "description": "What a Turing machine contains and in what form it is held.", "questions": [ { "id": "content-and-format-q01", "text": "What identifies and describes the content of a Turing machine, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "content-and-format-q02", "text": "Who or what asserted this about the content of a Turing machine, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "content-and-format-q03", "text": "What may an agent decide or do once the content of a Turing machine is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] } ] }, { "id": "access-and-rights", "name": "Access, rights and retention", "description": "Who may read, copy or change it, and for how long it is kept.", "findings": [ { "id": "access-rules", "name": "Access rules and retention", "description": "The permissions attached to a Turing machine and the period it survives.", "questions": [ { "id": "access-rules-q01", "text": "What identifies and describes access to a Turing machine, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "access-rules-q02", "text": "Who or what asserted this about access to a Turing machine, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "access-rules-q03", "text": "What may an agent decide or do once access to a Turing machine is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] } ] } ] }, { "id": "subject-and-method", "name": "Subject matter and method", "description": "What Turing machine studies and how it establishes anything.", "rationale": "A field is identified by its questions and its methods, and those are what distinguish it from the fields next to it.", "layers": [ { "id": "subject", "name": "Subject matter", "description": "The questions it takes as its own.", "findings": [ { "id": "subject-record", "name": "Questions and objects of study", "description": "What it is about, stated so a neighbouring field can be told apart.", "questions": [ { "id": "subject-record-q01", "text": "What questions and objects does Turing machine take as its own?", "kind": "definition" }, { "id": "subject-record-q02", "text": "Which questions does it share with a neighbouring field, and who claims them?", "kind": "boundary" } ] } ] }, { "id": "method", "name": "Method and evidence", "description": "How claims are established and what counts as evidence.", "findings": [ { "id": "method-record", "name": "Methods and standards of evidence", "description": "The methods used and what they are taken to establish.", "questions": [ { "id": "method-record-q01", "text": "By what methods does Turing machine establish claims, and what counts as sufficient evidence?", "kind": "provenance" }, { "id": "method-record-q02", "text": "What kind of claim can this field not settle, and where should an agent look instead?", "kind": "action" } ] } ] } ] }, { "id": "institutions-and-classification", "name": "Institutions and classification", "description": "Where Turing machine is practised and how catalogues place it.", "rationale": "The institutional footprint is the evidence that a field exists as a field rather than as a topic.", "layers": [ { "id": "institutions", "name": "Institutional markers", "description": "Societies, journals, degrees and departments.", "findings": [ { "id": "institution-record", "name": "Bodies and venues", "description": "Where the field organises itself.", "questions": [ { "id": "institution-record-q01", "text": "Which societies, journals or degrees mark Turing machine as an established field?", "kind": "provenance" }, { "id": "institution-record-q02", "text": "What would show that it is emerging or dissolving rather than established?", "kind": "boundary" } ] } ] }, { "id": "classification", "name": "Classification schemes", "description": "Where library and research classifications put it.", "findings": [ { "id": "classification-record", "name": "Codes and their disagreements", "description": "The classification codes that place it, and where they differ.", "questions": [ { "id": "classification-record-q01", "text": "Which classification schemes place Turing machine, under what codes?", "kind": "definition" }, { "id": "classification-record-q02", "text": "Where do those schemes disagree about its scope?", "kind": "boundary" } ] } ] } ] }, { "id": "provenance-and-evidence", "name": "Provenance, evidence and time", "description": "Where every claim about a Turing machine came from and when it held.", "rationale": "A claim without a source and a time cannot be superseded, only overwritten, and an agent that overwrites loses the ability to explain itself.", "layers": [ { "id": "source-and-authority", "name": "Source and authority", "description": "Who said it, on what evidence, and how strongly.", "findings": [ { "id": "claim-provenance", "name": "Claim provenance and confidence", "description": "The authority behind each claim about a Turing machine and how confident it is.", "questions": [ { "id": "claim-provenance-q01", "text": "What identifies and describes a claim about a Turing machine, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "claim-provenance-q02", "text": "Who or what asserted this about a claim about a Turing machine, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "claim-provenance-q03", "text": "What may an agent decide or do once a claim about a Turing machine is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] } ] }, { "id": "time-and-versions", "name": "Time, versions and supersession", "description": "When a claim was true, when it was learnt, and what replaced it.", "findings": [ { "id": "validity-and-supersession", "name": "Validity period and supersession", "description": "How an old claim about a Turing machine is retired without being erased.", "questions": [ { "id": "validity-and-supersession-q01", "text": "What identifies and describes the validity of a claim about a Turing machine, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "validity-and-supersession-q02", "text": "Who or what asserted this about the validity of a claim about a Turing machine, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "validity-and-supersession-q03", "text": "What may an agent decide or do once the validity of a claim about a Turing machine is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] } ] } ] } ] }, "statistics": { "bundles": 6, "layers": 12, "findings": 14, "questions": 38 } } } }