Definition:Turing Machine/Computable Function

Definition

Let $T = \struct {Q, \Sigma, \Gamma, \delta, q_0, B, F}$ be a Turing machine.

Let $D$ be the set of finite strings $w \in \Sigma^*$ such that $T$ halts on $w$.

For each $w \in D$, let $\alpha, \beta \in \Gamma^*$, $X \in \Gamma$, $q \in Q$ be unique such that:

$q_0 w \vdash^* \alpha q X \beta$

where $\map \delta {q, X}$ is undefined.

This article, or a section of it, needs explaining. In particular: A lot of symbol taken for granted here, in particular the $*$ versions of some of the symbols. We might want to provide a glossary that we can transclude into whatever page needs it. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Explain}} from the code.

Let:

$\alpha \beta = B \dotso B s_1 s_2 \dotso s_{n - 1} s_n B \dotso B$

where:

$s_i \in \Gamma$ for each $1 \le i \le n$

$s_1 \ne B$ and $s_n \ne B$

That is, $s_1 \dotso s_n$ is the concatenation $\alpha \beta$, excluding any leading or trailing $B$ symbols.

Then, the mapping $f : D \to \Gamma^*$ defined as:

$\map f w = s_1 s_2 \dotso s_{n - 1} s_n$

is the function computed by $T$.

A mapping computed by some Turing machine is a computable function.

Sources

• 2013: Michael Sipser: Introduction to the Theory of Computation (3rd ed.): $5.3$ Mapping Reducibility