A deterministic Turing machine with a read-only input tape, \(k\) work tapes, and a write-only output tape, over an alphabet of symbols extended by a blank. It consists of an initial state \(q_0\) and a transition function that, given the current state, the (possibly blank) symbol under the input head, and the \(k\) symbols under the work-tape heads, returns a one-step action: a movement of the input head, a write-and-move instruction for each work tape, an optional symbol to append to the output, and a successor state or the decision to halt. Neither the alphabet nor the state set is required to be finite.

The successor of a configuration \(c\) of a multi-tape Turing machine \(M\): if \(c\) is halted (its state component is empty), the step returns \(c\) unchanged; otherwise it applies to \(c\) the action that the transition function of \(M\) prescribes for the current state, the symbol under the input head, and the symbols under the \(k\) work-tape heads.

The symbol, if any, that a multi-tape Turing machine \(M\) appends to its output tape when executing one step from a configuration \(c\): the optional output component of the action prescribed by the transition function for the current state and scanned symbols, and no symbol at all when \(c\) is halted.

The starting configuration of a multi-tape Turing machine \(M\) on an input word: the machine is in its initial state \(q_0\), the input head is at the first input symbol, all work tapes are blank with heads at the origin, and the output is empty.

The configuration reached by iterating the one-step function of a multi-tape Turing machine \(t\) times starting from a configuration \(c\). Since halted configurations are fixed points of the step function, a machine that halts stays in its halting configuration.

The finite set of integer positions occupied by the head of work tape \(i\) during the computation of a multi-tape Turing machine from a configuration \(c\), over steps \(0\) through \(t\) inclusive.

The number of distinct work-tape cells touched by the head of work tape \(i\) in the computation of a multi-tape Turing machine from a configuration \(c\) up to step \(t\), i.e. the cardinality of the set of positions visited by that head.

The total number of work-tape cells touched by the computation of a multi-tape Turing machine with \(k\) work tapes from a configuration \(c\) up to step \(t\): the sum over the \(k\) work tapes of the number of distinct cells visited by each head. This is the space measure used throughout; the read-only input tape and the write-only output tape do not count.

The proposition that a multi-tape Turing machine \(M\), started in its initial configuration on an input word, is halted after \(t\) steps (hence halts within \(t\) steps, since halting is absorbing), that its output tape then holds exactly the given output word, and that the computation up to step \(t\) touches exactly \(s\) work-tape cells. Neither the alphabet nor the state set is required to be finite.

Given injective encodings of the domain and codomain into words over the machine’s alphabet, a multi-tape Turing machine \(M\) computes a function \(f\) within time bound \(t\) and space bound \(s\) (both functions of the input) if for every input \(a\) there are \(t' \le t(a)\) and \(s' \le s(a)\) such that \(M\), on the encoding of \(a\), halts within \(t'\) steps with output the encoding of \(f(a)\), touching exactly \(s'\) work-tape cells. The alphabet and state set need not be finite.

A function \(f\) is computable within input-indexed time bound \(t\) and space bound \(s\), with respect to injective encodings of its domain and codomain into binary words, if there exist a number \(k\) of work tapes, a finite state set, and a multi-tape Turing machine over the binary alphabet with those tapes and states that computes \(f\) between the given encodings within the bounds \(t\) and \(s\).

A function \(f\) is computable within time bound \(t\) and space bound \(s\), where \(t, s : \mathbb {N} \to \mathbb {N}\) are functions of the encoded input length, if there is a binary Turing machine with finitely many states that, for every input \(a\), computes the encoding of \(f(a)\) from the encoding of \(a\) in at most \(t(n)\) steps and touching at most \(s(n)\) work-tape cells, where \(n\) is the length of the encoding of \(a\).

The Boolean indicator function of a set \(L \subseteq \alpha \): the function mapping \(x\) to true when \(x \in L\) and to false otherwise.

A set \(L \subseteq \alpha \) is decidable within input-indexed time bound \(t\) and space bound \(s\), with respect to an injective binary encoding of \(\alpha \), if the Boolean indicator function of \(L\) is computable within these bounds, the one-bit answer being encoded as the single-symbol output word.

The Boolean predicate stating that a multi-tape Turing machine \(M\) on a given input halts after exactly \(t\) steps: started from its initial configuration, \(M\) is halted after \(t\) steps but not after \(t - 1\) steps (truncated subtraction). In particular the predicate is never true at \(t = 0\): a machine must perform at least one step to halt.