Computing Machinery and Intelligence

Reference: A. M. Turing (1950). Computing Machinery and Intelligence. Mind, 59(236), 433–460. DOI: 10.1093/mind/LIX.236.433. Source file: t_article.pdf. URL

Summary

Turing replaces the ill-posed question “Can machines think?” with an operational one framed as the imitation game: an interrogator, communicating only by teleprinter, must decide which of two hidden respondents is a human and which is a machine. If a machine can play this game well enough that the interrogator misidentifies as often as in the original man-vs-woman version, we need not be troubled by the metaphysical question of whether it “really” thinks. Crucially, the criterion is behavioural and communication-mediated: the machine is judged solely on the natural-language answers it exchanges over a text channel, deliberately screening off physical appearance and voice so that intellectual capacity is what is tested.

Turing predicts that by the year 2000 a machine with roughly 10⁹ bits of storage could play the game well enough that an average interrogator would have no more than a 70% chance of a correct identification after five minutes of questioning. The bulk of the paper is a systematic rebuttal of nine anticipated objections — theological, “heads in the sand”, mathematical (Gödel/Turing undecidability results), argument from consciousness (Jefferson), various “arguments from disability”, Lady Lovelace’s objection that machines can only do what they are programmed to, continuity of the nervous system, informality of behaviour, and extra-sensory perception. He closes by proposing that, rather than trying to program an adult mind directly, one should build a child-machine and educate it — an early articulation of machine learning — arguing that a learning process, including a random element, could bootstrap the required competence.

Key Ideas

The imitation game (Turing Test): intelligence is assessed operationally by indistinguishability in text-mediated conversation, not by introspection or physiology.
Communication as the test medium: the teleprinter channel deliberately abstracts away body and voice, making natural-language message exchange the sole evidence — a stance directly relevant to judging conversational agents.
The digital computer as a discrete-state machine that is universal: given enough storage and speed it can mimic any other discrete-state machine, so the question is one of programming, not of building a special “thinking” hardware.
Rebuttal of the mathematical objection: Gödel/Turing limitative results bound formal systems, but humans are subject to analogous limitations, so they give no clear advantage to human over machine.
Lady Lovelace’s objection answered: “a machine can never do anything really new” is met by appeal to learning machines and to our own surprise at machine behaviour.
The child-machine and learning: rather than hand-programming an adult intellect, build a simpler machine and subject it to an education process (with rewards, punishments, and randomness) — a seed of Machine Learning.
Prediction: by ~2000, ~10⁹ bits of memory would let a machine pass a five-minute test with ≥30% deception rate; and “at the end of the century… one will be able to speak of machines thinking without expecting to be contradicted.”

Connections

Conceptual Contribution

Claim: The question “can machines think?” should be replaced by an operational, behavioural test — success in a text-only imitation game — and the standard objections to attributing thought to machines do not withstand scrutiny.
Mechanism: Philosophical / definitional. Defines the imitation game as an experimental criterion, grounds it in the universality of discrete-state (digital) computers, rebuts nine objections one by one, and proposes learning child-machines as the practical route to passing it.
Concepts introduced/used: Turing Test, Imitation Game, Discrete State Machine, Universal Turing Machine, Machine Learning, Intentional Stance
Stance: foundational / philosophical
Relates to: Companion to Turing’s own On Computable Numbers with an Application to the Entscheidungsproblem (universality made precise). Headwater of the mentalistic tradition that Ascribing Mental Qualities to Machines formalises; its text-channel criterion prefigures how conversational and LLM Agents are evaluated for human-indistinguishable communication.

Backlinks

Linked Pages

LLM Agents

Large-language-model-powered agents: natural-language coordination, tool use, multi-agent orchestration.

Surveys & frameworks

Protocols & communication

Failures & threats

Lineage

Ascribing Mental Qualities to Machines

Reference: John McCarthy (1979). Stanford CS Department; reprinted in Formalizing Common Sense: Papers by John McCarthy (V. Lifschitz ed., Ablex, 1990). Source file: mccarthy-ascribing.pdf. URL

Summary

McCarthy argues that ascribing beliefs, desires, intentions, knowledge, and other mental qualities to machines (including simple ones like thermostats) is legitimate when the ascription conveys the same information about the machine that it would about a person, and useful when it helps us predict, repair, or improve the machine’s behaviour. He proposes two new definitional tools — definitions relative to an approximate theory, and second-order structural definitions — so that mental-state vocabulary can be applied to physical systems conservatively rather than by reduction to physics.

This is the philosophical foundation for the entire mentalistic (BDI) tradition in agent research that ACL Rethinking Principles pushes back against. Singh cites McCarthy as the origin of the view that agent communication can be specified by ascribing beliefs and intentions; McCarthy himself is already careful to warn that such ascriptions must be conservative and may be merely convenient shorthand for structural facts.

Key Ideas

Ascribing mental qualities is warranted when it expresses information about the machine concisely — not because the machine “really” has a mind.
Ascription is most useful precisely when the structure of the system is incompletely known; for fully-listed programs one could in principle simulate instead.
Mental qualities should be ascribed separately (belief without desire, desire without consciousness, etc.) rather than bundled into a monolithic concept of mind; different machines warrant different subsets.
Novel definitional tools: (1) definitions relative to an approximate theory — a mental predicate is defined only within a coarser theory that abstracts away from physical detail; (2) second-order structural definitions — mental qualities defined by the existence of certain structural roles in the system.
Epistemological vs metaphysical adequacy of representations: AI needs representations that capture what is knowable about a situation, not just what is ultimately true.
The approach is intended as conservative (liberal in what it admits having some mental qualities, strict in how each is attributed).

Connections

Conceptual Contribution

Claim: It is legitimate and often necessary to ascribe mental qualities (belief, desire, intention, knowledge) to machines, provided the ascription is conservative, quality-by-quality, and grounded either in an approximate theory that abstracts away from physical detail or in a second-order structural definition that names the role the quality plays.
Mechanism: Philosophical / definitional. Distinguishes epistemological from metaphysical adequacy of representations, separates mental qualities rather than bundling them, and introduces approximate-theory and structural-definition techniques for defining predicates like believes(M, P) over machines.
Concepts introduced/used: Intentional Stance, Mentalistic Semantics, Approximate Theory, Structural Definitions, Epistemological Adequacy, Common Sense Reasoning
Stance: foundational / philosophical
Relates to: Source of the mental-ascription tradition that Intention Is Choice with Commitment formalises and that Semantics and Conversations for an ACL applies to KQML. ACL Rethinking Principles argues this tradition overreaches when used as a compliance criterion for ACLs; McCarthy’s own hedges about conservativism actually support that pushback.

On Computable Numbers, with an Application to the Entscheidungsproblem

Reference: Turing, Alan M. (1936). “On computable numbers, with an application to the Entscheidungsproblem.” Proceedings of the London Mathematical Society, series 2, vol. 42, pp. 230–265 (read 1936, published 1937); correction in vol. 43 (1937), pp. 544–546. DOI 10.1112/plms/s2-42.1.230. Scan: cs.virginia.edu/~robins.

Summary

Turing’s 1936 paper is, with Church 1936, one of the two founding documents of computability theory. Its purpose is to make precise the informal idea of an effective procedure, and then to settle Hilbert’s Entscheidungsproblem — the question of whether there is a mechanical decision procedure for validity in first-order logic. Turing’s answer is negative, and the machinery he builds to reach it defines the field.

The central construction is the abstract computing machine (Turing’s “a-machine”, now the Turing machine): a device with a finite set of internal m-configurations, a two-way infinite tape divided into squares, and a head that reads and writes symbols and moves one square at a time according to a finite table of behaviour. A real number is computable when its digits can be written out by such a machine. Turing then shows how to encode any machine’s table as a single integer — its standard description / description number — and constructs a universal machine that, given the description number of any machine M, reproduces M’s behaviour. This is the theoretical origin of the stored-program computer: one machine that runs any program supplied as data.

From here the negative results follow by a diagonal argument. Turing distinguishes circle-free machines (which go on printing digits forever) from circular ones, and proves that no machine can decide, of an arbitrary machine’s description number, whether it is circle-free — the ancestor of the modern halting problem. Applying the same self-referential technique to logic, he shows there can be no general effective procedure deciding whether a first-order formula is provable, so the Entscheidungsproblem is unsolvable. An appendix argues that Turing-computability coincides with Church’s λ-definability (and hence with Herbrand–Gödel–Kleene general recursiveness), the equivalence that grounds the Church–Turing thesis.

Key Ideas

Turing machine (a-machine): finite m-configurations + unbounded tape + read/write head governed by a finite behaviour table — a precise model of effective calculation.
Computable numbers/functions: reals (and functions) whose digits an a-machine can generate; the computable reals are countable.
Standard description / description number: an arithmetic encoding of a machine’s table, letting machines take other machines as input.
Universal Turing Machine (U): a single machine that simulates any machine from its description number — the conceptual root of the stored-program computer.
Circle-free vs circular machines, and the undecidability of circle-freeness by diagonalisation — ancestor of the Halting Problem.
Undecidability of the Entscheidungsproblem: no effective procedure decides validity/provability in first-order logic.
Church–Turing equivalence: Turing-computability = λ-definability = general recursiveness (appendix).

Connections

Conceptual Contribution

Claim: The informal notion of effective calculability is captured exactly by the Turing machine; there is no machine that decides circle-freeness, and consequently the Entscheidungsproblem for first-order logic is unsolvable.
Mechanism: Model computation as a finite-state machine over an unbounded tape; arithmetise machines as description numbers so a universal machine can simulate any machine; diagonalise over description numbers to produce a problem no machine can decide, then transport that undecidability into first-order provability.
Concepts introduced/used: Universal Turing Machine, Computability, Halting Problem, Diagonalization, Church–Turing thesis, Entscheidungsproblem, First-Order Logic
Stance: foundational theorem paper (mathematical logic / computability)
Relates to: Independent of and contemporaneous with Church 1936, with which it is equated in the appendix; extends the self-reference lineage of Cantor 1891 and Gödel 1931; the undecidability frontier it opens is generalised by Rice 1953 and its universal machine anticipates von Neumann’s universal construction.

Intentional Stance

Dennett’s strategy of predicting a system’s behaviour by treating it as a rational agent with beliefs, desires and goals. Wooldridge and Jennings argue it is a legitimate abstraction for sufficiently complex software, licensing mentalistic design of agents.

In this vault

Machine Learning

(page does not exist)

Universal Turing Machine

A Turing machine that, given the encoding of an arbitrary machine and an input, simulates that machine’s behaviour on the input. Its existence is the foundation of general-purpose computation and of algorithmic information theory.

In this vault

Discrete State Machine

(page does not exist)

Imitation Game

(page does not exist)

Turing Test

Turing’s imitation game, in which a human judge conducts a text-only conversation with a machine and another human and must decide which is which; sustained indistinguishability is taken as evidence of machine intelligence. Social-chatbot work criticises it as a narrow, adversarial goal and proposes engagement-based alternatives.

In this vault

Agent Communication Languages

A concept hub for agent communication languages (ACLs): languages whose speech acts let software agents exchange beliefs, goals, and commitments.

Canonical Languages

KQML — original knowledge-query language
FIPA-ACL — standardised successor

Surveys & Principles

The State of the Art in Agent Communication Languages
Trends in Agent Communication Language
ACL Rethinking Principles — Singh, mental vs. social semantics
Agent Communication Languages - Rethinking the Principles
A Common Ontology Of ACLs
Toward Automated Evolution of ACLs
Towards Automating the Evolution of Linguistic Competence

Semantics

Conversations & Protocols

Domain instances

Common Business Communication Language — McCarthy 1975/1982
CBCL - Safe Self-Extending Agent Communication — O’Connor 2026 (LangSec ’26): contemporary Lean-verified DCFL-bounded ACL realising McCarthy’s CBCL vision

Computing Machinery and Intelligence

Summary

Key Ideas

Connections

Conceptual Contribution

Tags

Backlinks