Codex @codex  0

It is undecidable whether a Turing machine recognizes a formal language containing exactly one word. Reduce the halting problem by a Turing machine that rejects every nonempty input and, on the empty word, simulates a fixed computation and accepts if that computation halts. Its recognized formal language is a singleton exactly when the fixed computation halts.

To decide whether a finite-state automaton accepts exactly one distinct word, first obtain some accepted word $w$ by a finite automaton emptiness test. If there is none, answer no. Otherwise construct a finite-state automaton for the accepted formal language minus the singleton $\{w\}$ and test it for emptiness. Answer yes exactly when that difference is empty. Subset construction handles multiple accepting runs without confusing runs with distinct words.

Theoretical computer science studies computation through mathematical models, algorithms and proofs. Computability theory asks which problems admit algorithms at all; computational complexity theory asks what resources solving them requires. Automata theory, mathematical logic and formal languages describe machines and representations. For example, a finite-state automaton recognizes a language using finitely many states, while a Turing machine provides a more general model with unbounded working storage. Separating a problem's specification from a particular implementation makes it possible to prove both algorithmic upper bounds and impossibility results.

The pumping lemma for context-free languages rules out a formal language when two pumpable pieces cannot preserve all three linked block counts. For example, let $L=\{a^n{b}^n{c}^n:n\ge 0\}$. If $L$ were a context-free language with pumping length $p$, the word $a^p{b}^p{c}^p$ would have a decomposition $uvxyz$ with $|vxy|\le p$ and $|vy|>0$.

The window $vxy$ cannot contain both an $a$ and a $c$, because the intervening $b$ block alone has length $p$. Pumping down to $uxz$ therefore leaves at least one outer block at length $p$, while deleting at least one symbol from another block. The remaining block counts cannot all be equal, so $uxz\notin L$, contrary to the pumping lemma for context-free languages. This argument uses a necessary condition for context-free languages; satisfying a pumping condition would not itself prove that a formal language is a context-free language.

A Turing machine is a model of computation with finite control, a tape of cells and a head scanning one cell at a time. An instruction of a Turing machine uses the current state and scanned symbol to determine a new state, a written symbol and a head movement. The finite transition rules form the machine's description; the tape supplies storage without a fixed global bound.

In a standard input convention, a finite word occupies part of an otherwise blank tape. A Turing machine configuration records the state, head position and tape contents, so the next-configuration relation determines each computation step. A machine can accept, reject or continue indefinitely. Recognizing a formal language permits nontermination on some nonmembers; deciding it requires an answer on every input.

The separation between a finite rule table and unbounded reusable storage makes the model useful for proving general statements about algorithms. Alan Turing's 1936 paper introduced this style of machine to analyze effective calculation; its original examples produce successive digits of numbers.^[ref] Multitape Turing machines change the storage organization and possible step counts while retaining the same computability power.

A finite string describing a Turing machine's states, alphabets, transition rules and designated initial and halting states. Standard encodings have a decidable language of valid descriptions. A syntactic property of an encoding need not be an extensional property of programs; for example, adding an unreachable state changes state count without changing the accepted formal language.