158 Complexity — Configuration
158.1 Overview
This module defines the configurations of a multi-tape Turing machine with a read-only input tape, \(k\) work tapes and one write-only output tape, together with the notion of a single-step action and its effect on a configuration, and the space measure read off a list of configurations. Nothing here mentions a machine: a step is split into an action (what is done) and its application (how a configuration changes).
158.2 Declarations
An action of a \(k\)-tape Turing machine over a symbol alphabet and a set of states records everything the machine does in one step: an attempted movement of the input head (left, stay, or right, encoded as a sign in \(\{ -1,0,1\} \)); for each of the \(k\) work tapes, optionally a value to write into the scanned cell (either a symbol or the blank) together with a head movement; an optional symbol to emit on the output tape; and an optional successor state, where the absence of a successor state means the machine halts.
A configuration of a \(k\)-tape Turing machine, relative to a fixed input string of length \(n\), consists of: an optional internal state (absence of a state denoting the halting state); the position of the input head, one of the \(n + 2\) positions obtained by flanking the input with one blank cell on each side (so the head position is shifted by one relative to the input indices); the contents of the \(k\) work tapes, each a function from \(\mathbb {Z}\) to optional symbols (blank cells carrying no symbol); the integer position of the head on each work tape; and the contents of the write-only output tape, a finite string of symbols.
Consider a Turing machine with no work tapes (\(k = 0\)) on a fixed input string. If two configurations of such a machine have the same internal state, the same input head position, and the same output tape contents, then they are equal.
Given a position among the \(n + 2\) input-head positions (the input of length \(n\) flanked by one blank cell on each side) and a sign \(m \in \{ -1, 0, 1\} \), this operation attempts to move the head by \(m\): the sum is computed in \(\mathbb {Z}\) and clamped to the valid range, so an attempted move past either boundary cell results in no movement.
For any input-head position \(p\) among the \(n + 2\) positions of an input of length \(n\), attempting to move the head by the sign \(0\) leaves the position unchanged: the clamped move of \(p\) by \(0\) equals \(p\).
On an input of length \(n\), attempting to move the input head left (by the sign \(-1\)) from the leftmost position \(0\) results in no movement: the clamped move of \(0\) by \(-1\) is again \(0\).
On an input of length \(n\), attempting to move the input head right (by the sign \(1\)) from the rightmost position \(n + 1\) results in no movement: the clamped move of \(n + 1\) by \(1\) is again \(n + 1\).
Let \(p\) be an input-head position on an input of length \(n\) with \(p \ne 0\). Then the clamped move of \(p\) by the sign \(-1\) is exactly the position \(p - 1\): a left move that does not start at the left boundary decrements the position.
Let \(p\) be an input-head position on an input of length \(n\) with \(p \ne n + 1\). Then the clamped move of \(p\) by the sign \(1\) is exactly the position \(p + 1\): a right move that does not start at the right boundary increments the position.
The symbol currently scanned by the input head of a configuration: if the head sits on either boundary blank cell (position \(0\) or position \(n + 1\) for an input of length \(n\)), no symbol is read; otherwise, when the head is at position \(p\) with \(1 \le p \le n\), the symbol read is the \(p\)-th symbol of the input string.
Let a configuration of a \(k\)-tape machine on an input string be given, and suppose its input head position equals \(1 + p\) for some natural number \(p\) strictly less than the length of the input. Then the symbol under the input head is precisely the \(p\)-th symbol (zero-indexed) of the input string.
For a configuration of a \(k\)-tape machine and an index \(i \lt k\), the symbol read by work tape \(i\): the (optional) content of the cell of tape \(i\) at the current position of that tape’s head.
A configuration is halted when it carries no internal state to continue from, i.e. its optional state component is absent.
The configuration in which a machine starts on a given input, for a starting state \(q_0\): the internal state is \(q_0\), the input head is at position \(1\) (scanning the first input symbol), every cell of every work tape is blank, every work tape head is at cell \(0\), and the output tape is empty.
The result of carrying out an action on a configuration: the internal state becomes the action’s (optional) successor state; the input head is moved by the action’s sign using the clamped move, so it never leaves the input region and its two flanking blank cells; on each work tape, the scanned cell is overwritten with the action’s value for that tape when one is prescribed (and left unchanged otherwise) and the head then moves by the action’s sign for that tape; and the action’s emitted symbol, if any, is appended to the output tape. This is the part of a machine step that does not depend on how the action was chosen.
For every action of a \(k\)-tape machine, every configuration, and every work tape index \(i \lt k\), the head position of tape \(i\) after applying the action differs from its position before by at most one: \(\left\lvert p' - p\right\rvert \le 1\), where \(p\) and \(p'\) are the positions of the head of tape \(i\) before and after the action is applied.
Given a list of configurations of a \(k\)-tape machine and a tape index \(i \lt k\), the finite set of integer cell indices occupied by the head of work tape \(i\) in some configuration of the list.
The number of work tape cells touched by the heads along a list of configurations of a \(k\)-tape machine: the sum, over the tape indices \(i \lt k\), of the cardinality of the set of cells visited by the head of tape \(i\).