Computer science

Start here

• ConceptTuring machine

  A Turing machine is an abstract model of computation with a finite set of states and an unbounded tape of symbols. A moving head reads and writes the symbols one cell at a time. Alan Turing introduced it in 1936 to make the notion of an algorithm precise. A function is computable when some Turing machine computes it, and by the Church–Turing thesis this matches the informal idea of an algorithm. Turing machines are the standard model in computability theory and in complexity theory.

• ConceptCellular automaton

  A cellular automaton is a grid of cells, each in one of finitely many states. All cells update at the same time by one local rule. The new state of a cell depends only on the old states of the cells in a fixed finite neighbourhood. As a dynamical system it is a continuous map of the configuration space that commutes with the shifts, by the Curtis–Hedlund–Lyndon theorem. Very simple rules can produce complex behaviour, so cellular automata serve as models in physics and biology and as a model of computation.

• ConceptChurch–Turing thesis

  The Church–Turing thesis is a claim about the informal notion of an algorithm. It says that a function on the natural numbers can be calculated by an effective method exactly when a Turing machine computes it. It is not a theorem, because "effective method" is an informal notion and cannot be the subject of a proof. It is supported by the fact that all proposed formal models of computation define the same class of functions. These models include general recursive functions, the lambda calculus and Turing machines. The thesis lets one prove that a problem has no algorithm at all by proving that no Turing machine solves it.

• TheoremUndecidability of the halting problem

  Fix a Gödel numbering $e \mapsto M_e$ of all Turing machines with input and output in the natural numbers. Let $H = \set{(e, x) \in \N^2 : M_e \text{ halts on input } x}$. Then $H$ is not a computable set: no Turing machine halts on every input $(e, x)$ and outputs $1$ if $(e, x) \in H$ and $0$ otherwise.

• TheoremRice's theorem

  Fix a standard Gödel numbering of programs, and let $\varphi_e$ be the partial computable function of one argument computed by program $e$. Let $\mathcal P$ be a set of partial computable functions $\N \rightharpoonup \N$ that is neither empty nor the set of all partial computable functions. Then the index set $\set{e \in \N : \varphi_e \in \mathcal P}$ is not a computable set.

• TheoremSmn theorem

  Fix a standard Gödel numbering of programs, and let $\varphi^{(k)}_e$ be the partial computable function of $k$ arguments computed by program $e$. Let $m, n \ge 1$. Then there is a primitive recursive function $s^m_n \colon \N^{m+1} \to \N$ such that for all $e \in \N$, $\bar x \in \N^m$ and $\bar y \in \N^n$: $$\varphi^{(n)}_{s^m_n(e, \bar x)}(\bar y) \simeq \varphi^{(m+n)}_e(\bar x, \bar y).$$ Here $\simeq$ means that both sides are undefined, or both are defined and equal.