161 Complexity — Finite
161.1 Overview
This module bundles a deterministic multi-tape Turing machine with a finite state set, giving the machine model of Arora–Barak §1.2 over which all the headline complexity-theoretic definitions are stated. On top of the bundled machines it defines what it means to compute an output within a time bound, to compute a string function in time \(T(n)\) (also across an alphabet embedding), and to compute a function with no time constraint, and it proves the basic laws of these notions: time bounds can be weakened, no machine halts in zero steps, completed outputs are unique, and a total machine’s completed outputs are exactly its prescribed values. Two raw-layer lemmas record that the output tape gains at most one symbol per step and only ever grows.
161.2 Declarations
Let \(M\) be a deterministic multi-tape Turing machine, let \(x\) be an input word, and let \(t \in \mathbb {N}\). Then the word written on the output tape after \(M\) runs for \(t\) steps from its initial configuration on \(x\) has length at most \(t\).
Let \(M\) be a deterministic multi-tape Turing machine, let \(c\) be any configuration of \(M\), and let \(t \le t'\) be natural numbers. Then the word on the output tape after running \(M\) for \(t\) steps from \(c\) is a prefix of the word on the output tape after running \(M\) for \(t'\) steps from \(c\).
For an alphabet \(\Sigma \), a finite Turing machine consists of a number \(k \in \mathbb {N}\) of work tapes, a finite state set with decidable equality, and a deterministic multi-tape Turing machine with \(k\) work tapes and those states, whose tape cells hold either a symbol of \(\Sigma \) or a blank. This is the machine model of Arora–Barak §1.2, up to the declared model variations (append-only output tape, start-marker-free initialization).
A finite Turing machine \(M\) over an alphabet \(\Sigma \) computes the output \(w\) from the input \(x\) within \(t\) steps if there exists a space bound \(s\) such that \(M\), started on \(x\), halts within \(t\) steps using space \(s\) with exactly \(w\) written on its output tape; that is, the space used is existentially quantified away from the time-and-space notion of computation (Arora–Barak, Definition 1.3).
A finite Turing machine \(M\) over an alphabet \(\Sigma \) computes the string function \(f \colon \Sigma ^{*} \to \Sigma ^{*}\) in time \(T \colon \mathbb {N} \to \mathbb {N}\) if for every input word \(x\), the machine \(M\) halts on \(x\) within \(T(\left\lvert x\right\rvert )\) steps with \(f(x)\) written on its output tape (Arora–Barak, Definition 1.3).
Let \(\alpha \) and \(\Gamma \) be alphabets, let \(e \colon \alpha \hookrightarrow \Gamma \) be an injection, and let \(M\) be a finite Turing machine over \(\Gamma \). The machine \(M\) computes the string function \(f \colon \alpha ^{*} \to \alpha ^{*}\) via \(e\) in time \(T \colon \mathbb {N} \to \mathbb {N}\) if for every word \(x\) over \(\alpha \), on the input obtained by applying \(e\) letterwise to \(x\), the machine \(M\) halts within \(T(\left\lvert x\right\rvert )\) steps with the letterwise image of \(f(x)\) under \(e\) written on its output tape. This is how a machine over a larger alphabet is said to compute a function on a smaller one (Arora–Barak §1.3.1).
A finite Turing machine \(M\) over an alphabet \(\Sigma \) computes the string function \(f \colon \Sigma ^{*} \to \Sigma ^{*}\) if for every input word \(x\) there exists a number of steps \(t\) such that \(M\) halts on \(x\) within \(t\) steps with \(f(x)\) written on its output tape. This is the notion of computability underlying the uncomputability results (Arora–Barak §1.4–1.5).
Let \(M\) be a finite Turing machine over an alphabet \(\Sigma \), let \(x\) and \(w\) be words over \(\Sigma \), and let \(t \le t'\) be natural numbers. If \(M\), started on \(x\), halts within \(t\) steps with \(w\) on its output tape, then it also halts within \(t'\) steps with \(w\) on its output tape.
For every finite Turing machine \(M\) over an alphabet \(\Sigma \) and all words \(x\) and \(w\) over \(\Sigma \), the machine \(M\) does not compute the output \(w\) from the input \(x\) within \(0\) steps: after zero steps the machine is still in its initial, non-halted state.
Let \(M\) be a finite Turing machine over an alphabet \(\Sigma \) and let \(x\) be a word over \(\Sigma \). If \(M\), started on \(x\), halts within \(t\) steps with \(w\) on its output tape and also halts within \(t'\) steps with \(w'\) on its output tape, then \(w = w'\). In other words, a machine has at most one completed output on a given input.
Let \(M\) be a finite Turing machine over an alphabet \(\Sigma \). If \(M\) computes the string function \(f \colon \Sigma ^{*} \to \Sigma ^{*}\) in time \(T \colon \mathbb {N} \to \mathbb {N}\) (halting within \(T(\left\lvert x\right\rvert )\) steps on every input \(x\) with \(f(x)\) on its output tape), then \(M\) computes \(f\), i.e. on every input it eventually halts with the value of \(f\) on its output tape.
Let \(M\) be a finite Turing machine over an alphabet \(\Sigma \), let \(x\) and \(w\) be words over \(\Sigma \), and let \(t \in \mathbb {N}\). Then \(M\) computes the output \(w\) from the input \(x\) within \(t\) steps if and only if the configuration reached after running \(M\) for \(t\) steps from its initial configuration on \(x\) is halted and carries exactly the word \(w\) on its output tape.
Let \(M\) be a finite Turing machine over an alphabet \(\Sigma \) that computes the string function \(g \colon \Sigma ^{*} \to \Sigma ^{*}\), and let \(x\) and \(w\) be words over \(\Sigma \). Then there exists a number of steps \(t\) such that \(M\), started on \(x\), halts within \(t\) steps with \(w\) on its output tape if and only if \(w = g(x)\).