173 Complexity — State Renaming
173.1 Overview
This module transports the actions, configurations, and machines of the multi-tape Turing machine model along maps of the state type: actions and configurations can be renamed along an arbitrary function, while a whole machine is relabelled along a bijection of state sets, and the relabelled machine is shown to simulate the original step by step and, from the initial configuration, at every time.
173.2 Declarations
Given a function \(f\) from one state set to another, the one-step action of a Turing machine with \(k\) work tapes obtained from an action \(a\) by applying \(f\) to its optional successor state. The input-head movement, the write-and-move instructions for the \(k\) work tapes, and the optional output symbol are unchanged, and a halting action (one with no successor state) remains halting.
Given a function \(f\) from one state set to another, the configuration of a Turing machine with \(k\) work tapes on a fixed input word obtained from a configuration \(c\) by applying \(f\) to its optional state component. The input-head position, the work tapes and their head positions, and the output are preserved, and a halted configuration (one with no state) stays halted.
Let \(f\) be an arbitrary function from one state set to another (no injectivity is required), let \(a\) be a one-step action of a Turing machine with \(k\) work tapes, and let \(c\) be a configuration on a fixed input word. Then applying the action \(a\) with states renamed along \(f\) to the configuration \(c\) with state renamed along \(f\) yields the same configuration as first applying \(a\) to \(c\) and then renaming the state of the result along \(f\).
Given a multi-tape Turing machine \(M\) with \(k\) work tapes and state set \(S\), and a bijection \(e\) from \(S\) to another state set \(S'\), the machine over \(S'\) obtained by relabelling the states of \(M\) along \(e\): its initial state is \(e(q_0)\), and its transition on a state \(q'\), the scanned input symbol, and the \(k\) scanned work-tape symbols is the action that \(M\) prescribes in the state \(e^{-1}(q')\) for the same scanned symbols, with its successor state renamed along \(e\). A bijection, rather than an arbitrary function, is required here: a map identifying two states with different transitions would leave no well-defined transition table.
Let \(M\) be a multi-tape Turing machine with \(k\) work tapes and state set \(S\), let \(e\) be a bijection from \(S\) to another state set, and let \(c\) be a configuration of \(M\) on a fixed input word. Then one step of the machine obtained by relabelling the states of \(M\) along \(e\), taken from the configuration \(c\) with state renamed along \(e\), equals the configuration obtained by one step of \(M\) from \(c\) with state renamed along \(e\). The equality includes the case of a halted \(c\), where both sides leave the configuration unchanged.
Let \(M\) be a multi-tape Turing machine with \(k\) work tapes and state set \(S\), let \(e\) be a bijection from \(S\) to another state set, let \(x\) be an input word, and let \(t \in \mathbb {N}\). Then the configuration reached by the machine obtained by relabelling the states of \(M\) along \(e\) after \(t\) steps from its initial configuration on \(x\) equals the configuration that \(M\) reaches after \(t\) steps from its own initial configuration on \(x\), with its state renamed along \(e\).