TCSLib

169 Complexity — Oblivious Schedule

169.1 Overview

This chapter defines obliviousness for multitape Turing machines — head trajectories that depend only on the input length and the elapsed time — and builds the generic layers of the oblivious-simulation construction: the masked clock (an input-insensitive replay of a witness machine on the constant input of the same length), schedule decoration (data transducers whose extra tapes follow one designated schedule head), the transverse binary coding (a symbol-per-track realization of a machine over a large alphabet by a binary machine, exact at every physical step), and finally the concrete length-only schedule machine together with its trajectory certificate.

169.2 Declarations

Definition 169.1 Oblivious machine
✓

A multitape Turing machine \(M\) over an alphabet \(\Gamma \) is oblivious if its head positions are a function of the input length and the time only: for all inputs \(x, y \in \Gamma ^*\) with \(\left\lvert x\right\rvert = \left\lvert y\right\rvert \) and every time \(t \in \mathbb {N}\), the configuration reached after \(t\) steps of \(M\) started on \(x\) has the same input-head position (read as a natural number) and the same tuple of work-tape head positions as the configuration reached after \(t\) steps of \(M\) started on \(y\).

Definition 169.2 Configuration with masked input
✓
#

Given a symbol \(z\) and a configuration \(c\) of a \(k\)-tape machine on an input word \(x\), the masked configuration is the configuration on the constant input \(z^{\left\lvert x\right\rvert }\) (the word consisting of \(\left\lvert x\right\rvert \) copies of \(z\)) that has the same control state, the same numerical input-head position, the same work-tape contents and head positions, and the same output stream as \(c\).

Lemma 169.3 Input read of the masked configuration
✓

Let \(z\) be a symbol and \(c\) a configuration of a \(k\)-tape machine on an input word \(x\). The symbol scanned by the input head of the masked configuration on \(z^{\left\lvert x\right\rvert }\) is blank exactly when the symbol scanned in \(c\) is blank, and equals \(z\) whenever \(c\) scans any nonblank symbol.

Lemma 169.4 Masking commutes with actions
✓

Let \(z\) be a symbol, \(a\) an action (an input-head move, a write and a move for each work tape, an optional emitted symbol, and a next state), and \(c\) a configuration on an input word \(x\). Then masking the input by \(z\) after applying \(a\) yields the same configuration as applying \(a\) to the masked configuration.

Definition 169.5 Masked clock machine
✓
#

Given a machine \(W\) over an alphabet \(A\) and a distinguished symbol \(z\), the masked clock is the machine with the same number of tapes, the same state set, and the same start state as \(W\), whose transition function first replaces every nonblank scanned input symbol by \(z\) (leaving blank reads blank) and then consults \(W\)’s transition table. Its behaviour on any input therefore matches \(W\)’s behaviour on the constant input of the same length.

Lemma 169.6 One masked step matches one witness step
✓

Let \(W\) be a machine over an alphabet \(A\), let \(z \in A\), and let \(c\) be a configuration of the masked clock of \(W\) on an input word \(x\). Masking the result of one step of the masked clock at \(c\) yields the same configuration as performing one step of \(W\) at the masked configuration of \(c\); this includes the absorbing case in which \(c\) is already halted.

Lemma 169.7 Lockstep of the masked clock with its witness
✓

Let \(W\) be a machine over an alphabet \(A\), let \(z \in A\), let \(x\) be an input word, and let \(t \in \mathbb {N}\). Masking the configuration reached by the masked clock of \(W\) after \(t\) steps from its initial configuration on \(x\) yields exactly the configuration reached by \(W\) after \(t\) steps from its initial configuration on the constant input \(z^{\left\lvert x\right\rvert }\) — an equality of all five configuration components (state, input position, work tapes, work-head positions, and output), at live and halted times alike.

For every machine \(W\) over an alphabet \(A\) and every symbol \(z \in A\), the masked clock of \(W\) with mask \(z\) is oblivious: on any two inputs of the same length its input-head position and all of its work-head positions agree at every time. No halting hypothesis is required.

Lemma 169.9 Input-insensitive machines are oblivious
✓

Let \(P\) be a machine over an alphabet \(A\) and let \(z \in A\). Suppose the transition table of \(P\) is insensitive to nonblank input contents: for every state \(q\), scanned input symbol \(s\), and tuple of work-tape reads \(w\), the transition of \(P\) on the read obtained from \(s\) by replacing any nonblank symbol with \(z\) coincides with the transition of \(P\) on \(s\) itself. Then \(P\) is oblivious.

Lemma 169.10 The masked clock retains its computation
✓

Let \(W\) be a machine over the Boolean alphabet, \(T : \mathbb {N} \to \mathbb {N}\), and \(b \in \mathbb {N}\). Suppose that on every input \(x\), after \(b \cdot (T(\left\lvert x\right\rvert ) + 1)\) steps \(W\) has halted with output exactly the list of binary digits of \(T(\left\lvert x\right\rvert )\). Then the masked clock of \(W\) (with mask the symbol \(\mathsf{false}\)) satisfies the same specification: on every input \(x\) it halts within \(b \cdot (T(\left\lvert x\right\rvert ) + 1)\) steps with output the binary digits of \(T(\left\lvert x\right\rvert )\).

Definition 169.11 Schedule decoration by a data transducer
✓
#

Let \(P\) be a machine over an alphabet \(A\) with \(k\) work tapes, let \(l \in \mathbb {N}\), let a designated head index \(h \in \{ 0, \dots , k-1\} \) be given, and let \(D\) be a finite set of data states with a distinguished initial element. A visit function maps a state of \(P\), a data state, the scanned input symbol, the \(k\) schedule reads, and the \(l\) data reads to a new data state, a write for each of the \(l\) data tapes, and an optional emitted symbol. The decorated machine has \(k + l\) work tapes and state set \(P\)’s states paired with \(D\). On the first \(k\) tapes it performs exactly \(P\)’s transitions; each of the \(l\) extra tapes performs the write chosen by the visit function and moves exactly as the designated head \(h\) does; the emitted output is the one chosen by the visit function; and the decorated machine halts exactly when \(P\) halts.

Definition 169.12 Projection onto the schedule
✓
#

Given a configuration of a \((k+l)\)-tape machine whose state set is a product \(S \times D\), on an input word \(x\), the schedule projection is the configuration of a \(k\)-tape machine with state set \(S\) on the same input that keeps the \(S\)-component of the control state (halted projects to halted), the input-head position, and the first \(k\) work tapes with their head positions, and whose output stream is empty.

Lemma 169.13 One decorated step projects to one schedule step
✓

Let \(P\) be a machine over an alphabet \(A\) whose transition table never emits an output symbol, and consider its decoration by any data transducer with \(l\) extra tapes, designated head, initial data state, and visit function. For every configuration \(c\) of the decorated machine, the schedule projection of one step of the decorated machine at \(c\) equals one step of \(P\) at the schedule projection of \(c\). This is an equality of entire configurations, not merely a correspondence at macrostep boundaries.

Lemma 169.14 Exact schedule projection at every time
✓

Let \(P\) be a machine over an alphabet \(A\) whose transition table never emits an output symbol, decorated by any data transducer. For every input word \(x\) and every time \(t \in \mathbb {N}\), the schedule projection of the decorated machine’s configuration after \(t\) steps from its initial configuration on \(x\) equals the configuration of \(P\) after \(t\) steps from its initial configuration on \(x\).

Lemma 169.15 Data heads follow the designated schedule head
✓

Let a machine \(P\) over an alphabet \(A\) be decorated by any data transducer with \(l\) extra tapes and designated head \(h\). For every input word \(x\), every time \(t \in \mathbb {N}\), and every extra-tape index \(i \lt l\), the head position of the \(i\)-th data tape of the decorated machine after \(t\) steps equals the head position of the designated schedule head \(h\) at the same time — including at all times after halting. Consequently no data-selected write can alter a head trajectory.

Lemma 169.16 Decoration preserves obliviousness
✓

Let \(P\) be a machine over an alphabet \(A\) whose transition table never emits an output symbol, and suppose \(P\) is oblivious. Then for every choice of data transducer — number of extra tapes, designated head, finite data-state set with initial element, and visit function — the decorated machine is oblivious. The data states, emitted answers, and data-selected writes may depend arbitrarily on the actual input; none of them can choose a head movement or terminate the schedule early.

Definition 169.17 Transverse binary encoding of a symbol
✓
#

An injection from possibly-blank symbols over an alphabet \(A\) (with decidable equality) into families of possibly-blank Booleans indexed by \(A\): a nonblank symbol \(a\) is sent to the indicator family whose track \(j \in A\) holds the bit \([\, j = a\, ]\), and the blank symbol is sent to the all-blank family. A symbol is thus stored transversely, one track per element of \(A\), so that all tracks of a logical cell share one head coordinate and a logical read or write takes exactly one physical transition.

Definition 169.18 Transverse decoding
✓
#

A total (noncomputable) decoding function from families of possibly-blank Booleans indexed by \(A\) back to possibly-blank symbols of \(A\): on the image of the transverse encoding it returns the unique preimage, and on malformed families it returns a fixed chosen value. Initialized simulations only ever read encoded blocks.

Lemma 169.19 Decoding inverts the transverse encoding
✓

For every possibly-blank symbol \(a\) over an alphabet \(A\) with decidable equality, decoding the transverse encoding of \(a\) returns \(a\); this includes the blank block.

Definition 169.20 Output-bit decoder
✓
#

Given an embedding \(e\) of the Booleans into an alphabet \(A\) with decidable equality, the decoded bit of a symbol \(a \in A\) is \(\mathsf{true}\) exactly when \(a = e(\mathsf{true})\).

Lemma 169.21 The output-bit decoder is correct on embedded bits
✓
#

For every embedding \(e\) of the Booleans into an alphabet \(A\) with decidable equality and every bit \(b\), decoding the embedded symbol \(e(b)\) recovers \(b\).

Definition 169.22 Transverse binary realization of a machine
✓

Let \(P\) be a machine with \(k\) work tapes over a finite alphabet \(A\) and let \(e\) be an embedding of the Booleans into \(A\). The transverse binary realization is a machine over the Boolean alphabet with the same state set and one work tape per pair \((i, a) \in \{ 0, \dots , k-1\} \times A\) (so \(k \cdot \left\lvert A\right\rvert \) tapes in all). At each step it decodes the scanned tracks of every logical tape to a symbol of \(A\), maps the scanned input bit through \(e\), consults \(P\)’s transition, re-encodes the chosen write transversely on the corresponding block of tracks, moves all tracks of each block by \(P\)’s move for that tape, and decodes any emitted symbol to a bit. Every logical step takes exactly one physical step.

Definition 169.23 Transverse encoding of configurations
✓

Let \(A\) be a finite alphabet with decidable equality, \(e\) an embedding of the Booleans into \(A\), \(x\) a binary word, and \(c\) a configuration of a \(k\)-tape machine over \(A\) on the input obtained by embedding \(x\) symbolwise. The encoded configuration over the Boolean alphabet has the same control state, the same numerical input-head position, work tapes indexed by pairs \((i, a)\) whose contents are track \(a\) of the transverse encoding of tape \(i\) of \(c\), head positions on every track of block \(i\) equal to \(c\)’s head position on tape \(i\), and output stream obtained from \(c\)’s by decoding each symbol to a bit.

Lemma 169.24 The encoded configuration reads the same input
✓

Let \(c\) be a configuration of a machine over a finite alphabet \(A\) on the symbolwise embedding of a binary word \(x\) under an embedding \(e\) of the Booleans into \(A\). Mapping the (possibly blank) input bit scanned by the encoded configuration through \(e\) recovers exactly the (possibly blank) input symbol scanned by \(c\).

Lemma 169.25 Scanned tracks decode to the scanned symbol
✓

Let \(c\) be a configuration of a \(k\)-tape machine over a finite alphabet \(A\) on the symbolwise embedding of a binary word. For every logical tape index \(i \lt k\), decoding the family of bits scanned on the tracks of block \(i\) in the encoded configuration yields exactly the symbol scanned by \(c\) on tape \(i\).

Let \(P\) be a machine over a finite alphabet \(A\), \(e\) an embedding of the Booleans into \(A\), and \(c\) a configuration of \(P\) on the symbolwise embedding of a binary word \(x\). Then one step of the transverse binary realization of \(P\) at the encoded configuration of \(c\) equals the encoded configuration of one step of \(P\) at \(c\): both the read and the write of a logical cell happen simultaneously across its fixed collection of tracks, and the halted case is absorbing on both sides.

Lemma 169.27 The transverse code preserves initial configurations
✓

Let \(P\) be a machine over a finite alphabet \(A\), \(e\) an embedding of the Booleans into \(A\), and \(x\) a binary word. Encoding the initial configuration of \(P\) on the symbolwise embedding of \(x\) yields exactly the initial configuration of the transverse binary realization of \(P\) on \(x\).

Lemma 169.28 Exact binary correspondence at every time
✓

Let \(P\) be a machine over a finite alphabet \(A\), \(e\) an embedding of the Booleans into \(A\), \(x\) a binary word, and \(t \in \mathbb {N}\). The configuration of the transverse binary realization of \(P\) after \(t\) steps from its initial configuration on \(x\) equals the encoding of the configuration of \(P\) after \(t\) steps from its initial configuration on the symbolwise embedding of \(x\) — with no intermediate coding states and no variable-duration memory accesses.

Lemma 169.29 Transverse coding preserves obliviousness
✓

Let \(P\) be a machine over a finite alphabet \(A\) and \(e\) an embedding of the Booleans into \(A\). If \(P\) is oblivious, then the transverse binary realization of \(P\) is oblivious — at all intermediate physical times and at all times after halting.

Let \(P\) be a machine over a finite alphabet \(A\), \(e\) an embedding of the Booleans into \(A\), \(x\) and \(w\) binary words, and \(t \in \mathbb {N}\). If, started on the symbolwise embedding of \(x\), the machine \(P\) has halted after \(t\) steps with output exactly the symbolwise embedding of \(w\), then the transverse binary realization of \(P\), started on \(x\), has halted after the same \(t\) steps with output exactly \(w\).

Definition 169.31 The schedule alphabet
✓
#

A finite logical alphabet in which schedule symbols and data cells occupy disjoint parts. Its symbols are: a tagged bit (\(\mathsf{bit}\, b\) for \(b\) Boolean), an origin marker, a unary unit marker, an interior marker, a tagged edge marker (\(\mathsf{edge}\, b\)), and a data cell carrying two payloads, each a pair of a possibly-blank bit and an allocation phase in \(\{ 0, 1, 2\} \); in a data cell the second payload is the cached left neighbour.

Definition 169.32 Embedding of bits into the schedule alphabet
✓
#

The injection of the Booleans into the schedule alphabet that sends a bit \(b\) to the tagged bit symbol \(\mathsf{bit}\, b\).

Definition 169.33 Clock-tape bit decoder
✓
#

The decoder from possibly-blank schedule symbols to possibly-blank bits that sends a tagged bit symbol \(\mathsf{bit}\, b\) to the bit \(b\) and every other symbol (including blank) to blank; only actual bit tags carry clock data.

Definition 169.34 Control phases of the length-only schedule
✓
#

A finite type of control phases, parameterized by a set \(S\) (the states of the clock witness) and a natural number \(a\). It comprises an initial phase; a clock phase carrying a state of \(S\); phases for rescanning the input, copying and reversing the clock’s output, decrementing the binary budget (an append counter ranging over \(\{ 0, \dots , a+1\} \) and a borrow phase carrying a carry bit), and building the unary counter; layout phases for the sweep guide, each carrying an allocation phase in \(\{ 0, 1, 2\} \), together with edge and reset phases; and the sweep phases (start, macrostep check, seek left, forward, backward, return to centre). The source decider’s state is absent from this type.

Definition 169.35 Schedule action on the three extra tapes
✓
#

An action builder for a machine with \(k + 3\) work tapes over the schedule alphabet. Given an optional next state (blank meaning halt), an input-head move, and a write–move pair for each of three extra tapes — the binary budget, the unary macrostep counter, and the sweep guide — it produces the action that leaves all \(k\) clock work tapes unwritten and stationary, performs the three given write–move pairs on the extra tapes, and emits no output.

Definition 169.36 Advancing an allocation phase
✓
#

The successor operation on the three-element allocation phase \(\{ 0, 1, 2\} \): it sends \(0 \mapsto 1\), \(1 \mapsto 2\), and \(2 \mapsto 0\). A caller advances its unary counter only when the phase returns to zero.

Definition 169.37 The length-only schedule machine
✓

Given a clock witness machine \(W\) over the Boolean alphabet and a parameter \(a \in \mathbb {N}\), the length-only schedule is a machine over the schedule alphabet with \(W.k + 3\) work tapes (the clock’s tapes plus a binary budget tape, a unary macrostep counter, and a sweep guide) whose states are the schedule phases over \(W\)’s state set. It first runs the input-masked clock, recording the clock’s emitted bits; copying and rescanning branch only on blank versus nonblank. Each successful decrement of the captured fixed-width binary budget appends \(a + 1\) unary markers, after an initial batch of \(a + 1\) markers, so the intended unary budget is \((a+1)(T(n)+1)\) where \(T(n)\) is the value emitted by the clock. The guide has radius three cells per unary marker; every macrostep starts at the guide’s marked origin, traverses the entire guide in both directions, and returns to the origin before advancing the unary counter, halting when the markers are exhausted. All of these actions are independent of the source decider and of all decorated data tapes.

Lemma 169.38 The schedule emits no output
✓

For every clock witness \(W\) over the Boolean alphabet, every parameter \(a \in \mathbb {N}\), every state \(q\) of the length-only schedule, every scanned input symbol, and every tuple of work-tape reads, the transition of the length-only schedule emits no output symbol. A decoration supplies the final answer at the schedule’s final halting transition.

Lemma 169.39 Trajectory certificate for the schedule
✓

For every clock witness \(W\) over the Boolean alphabet and every parameter \(a \in \mathbb {N}\), the length-only schedule built from \(W\) and \(a\) is oblivious: on arbitrary equal-length inputs over the schedule alphabet, its input head and every clock, budget, counter, and guide head occupy the same position at every time. No computation or halting hypothesis is needed.