156 Complexity — Code Parser
156.1 Overview
This module documents the parser and decoder layer for the fixed bit-string serialization of coded Turing machines (one-work-tape machines over the binary alphabet, bundled with their state count). It provides field readers for each component of the serialization grammar, a total decoder mapping every malformed string to a fixed fallback machine together with its padded round-trip law, soundness of the parser (acceptance characterizes a canonical serialization followed by all-1 padding), and an erased suffix scanner underlying a canonizer that computes the serialization of the machine a string denotes. Throughout, bit strings are written over \(\{ 0,1\} \), with \(1\) for true and \(0\) for false, and a reader maps a bit string either to failure or to a decoded value paired with the unconsumed suffix.
156.2 Declarations
A reader for unary numerals: on an input beginning with \(n\) ones followed by a zero it succeeds, returning the natural number \(n\) together with the suffix after that zero; it fails if the input is exhausted before a zero is found.
For every \(n \in \mathbb {N}\) and every bit string \(x\), the unary numeral reader applied to the string consisting of \(n\) ones, then a zero, then \(x\), succeeds and returns the pair \((n, x)\); in particular the suffix \(x\) is left untouched.
Given a bound \(n\), the reader that decodes a unary numeral (ones terminated by a zero) from a bit string and succeeds only when the decoded value \(i\) satisfies \(i \lt n\), in which case it returns \(i\) as an element of \(\{ 0, \dots , n-1\} \) together with the unconsumed suffix.
A reader decoding a fixed two-bit dictionary for a head movement: a leading \(11\) denotes moving left, \(00\) staying put, and \(10\) moving right, in each case returning the movement together with the remaining suffix; a leading \(01\), or an input of fewer than two bits, is rejected.
A reader decoding a fixed two-bit dictionary for an optional output bit: a leading \(00\) denotes producing no output, \(10\) outputting the bit \(0\), and \(11\) outputting the bit \(1\); a leading \(01\), or an input of fewer than two bits, is rejected. On success the decoded value is returned with the remaining suffix.
A reader decoding a fixed two-bit dictionary for an optional work-tape write, whose possible values are: write nothing, write the blank symbol, write the bit \(0\), or write the bit \(1\), denoted by the leading pairs \(00\), \(01\), \(10\), \(11\) respectively. Inputs of fewer than two bits are rejected; on success the decoded value is returned with the remaining suffix.
Given a bound \(n\), a reader for a successor-state field: a leading \(0\) denotes halting (no successor state) and consumes only that bit, while a leading \(1\) is followed by a unary index that must be smaller than \(n\) and is returned as the live successor state, in each case together with the unconsumed suffix.
Given a state-count parameter \(n\), a reader for one transition record of a one-work-tape machine over the binary alphabet with \(n + 1\) states. It reads, in order: an input-head movement, an optional work-tape write, a work-head movement, an optional output bit, and a successor-state field over \(n + 1\) states, failing as soon as any of the five fields fails, and assembles the results into a single transition record together with the unconsumed suffix.
Given a field reader producing values in a type \(A\), the reader that decodes three consecutive \(A\)-entries and returns the function assigning them to the three tape symbols blank, \(0\), \(1\) in that fixed order, together with the unconsumed suffix; it fails as soon as any of the three reads fails.
Given a field reader producing values in a type \(A\) and a length \(n\), the reader that decodes \(n\) consecutive \(A\)-entries and returns them as a vector indexed by \(\{ 0, \dots , n-1\} \), together with the unconsumed suffix; it fails as soon as any entry fails.
The natural number denoted by a bit string read in least-significant-bit-first binary, so the string \(b_0 b_1 \cdots b_{k-1}\) denotes \(\sum _{j\lt k} b_j 2^j\). The function is total: it also assigns a value to noncanonical strings (for instance those with trailing zeros); canonicity is checked separately by the parser.
The fixed fallback coded machine: a machine with a single state that immediately halts without moving any head, writing to the work tape, or producing output.
The partial parser for the fixed serialization of coded machines. On a bit string it: reads a doubled-bit header (each data bit repeated twice, terminated by the separator \(01\)) and requires the recovered word to be the canonical little-endian binary representation of its value \(n\); rejects unless the remaining input has length at least \(81(n+1)\); reads a unary initial state smaller than \(n + 1\); reads the full transition table, namely for each of the \(n + 1\) states a three-by-three grid of transition records indexed by the input and work symbols in blank/\(0\)/\(1\) order; and finally requires every remaining bit to be \(1\). On success it returns the coded machine with \(n + 1\) states assembled from these data.
The total decoding function from bit strings to coded machines: apply the machine parser, and return the fixed fallback machine (one state, immediately halting and silent) whenever parsing fails.
For a bound \(n\), an index \(i \lt n\), and any bit string \(x\): the range-checked unary reader with bound \(n\), applied to the self-delimiting unary code of \(i\) (\(i\) ones followed by a zero) concatenated with \(x\), succeeds and returns \((i, x)\).
For every head movement \(s\) (left, stay, or right) and every bit string \(x\), the head-movement reader applied to the two-bit dictionary code of \(s\) (\(11\), \(00\), or \(10\) respectively) followed by \(x\) succeeds and returns \((s, x)\).
For every optional output bit \(b\) (no output, output \(0\), or output \(1\)) and every bit string \(x\), the optional-output reader applied to the two-bit dictionary code of \(b\) (\(00\), \(10\), or \(11\) respectively) followed by \(x\) succeeds and returns \((b, x)\).
For every optional work-tape write \(b\) (write nothing, write the blank symbol, write \(0\), or write \(1\)) and every bit string \(x\), the optional-write reader applied to the two-bit dictionary code of \(b\) (\(00\), \(01\), \(10\), or \(11\) respectively) followed by \(x\) succeeds and returns \((b, x)\).
For a bound \(n\), a successor-state field \(s\) (either halt or a live state \(i \lt n\)), and any bit string \(x\): the successor-state reader with bound \(n\), applied to the encoding of \(s\) (a single \(0\) for halt; a \(1\) followed by the unary code of \(i\) for a live state) followed by \(x\), succeeds and returns \((s, x)\).
For every transition record \(a\) of a one-work-tape binary machine with \(n + 1\) states and every bit string \(x\), the transition-record reader applied to the serialization of \(a\) (the dictionary codes of its input-head movement, work-tape write, work-head movement, and output, followed by its successor-state field) concatenated with \(x\) succeeds and returns \((a, x)\).
Let a field reader and a field writer for values in a type \(A\) be given such that reading from any written value followed by any suffix returns exactly that value and suffix. Then for every function \(f\) from the three tape symbols (blank, \(0\), \(1\)) to \(A\) and every bit string \(x\), the three-symbol row reader applied to the concatenation of the written values \(f(\mathrm{blank})\), \(f(0)\), \(f(1)\) in that order, followed by \(x\), succeeds and returns \((f, x)\).
Let a field reader and a field writer for values in a type \(A\) be given such that reading from any written value followed by any suffix returns exactly that value and suffix. Then for every \(n\), every vector \(f\) indexed by \(\{ 0, \dots , n-1\} \), and every bit string \(x\), the length-\(n\) vector reader applied to the concatenation of the written entries \(f(0), \dots , f(n-1)\) in order, followed by \(x\), succeeds and returns \((f, x)\).
For every natural number \(n\), interpreting the canonical least-significant-bit-first binary representation of \(n\) (the empty string for \(n = 0\)) as a binary numeral yields \(n\) again.
Every serialized transition record of a one-work-tape binary machine with \(n + 1\) states has length at least \(9\): its four two-bit dictionary fields contribute eight bits, and its successor-state field is nonempty.
If every element of a finite list maps under a function \(f\) to a bit string of length at least \(c\), then the concatenation of all these bit strings, in list order, has length at least \(c\) times the length of the list.
For every coded machine with state-count parameter \(n\) (so \(n + 1\) states), the concatenation of the serialized transition records over all states and all nine input/work symbol pairs has length at least \(81(n+1)\).
Let \(M\) be a coded machine with state-count parameter \(n\). Applying the table reader — the length-\((n+1)\) vector reader whose entries are three-by-three grids of transition records indexed by the input and work symbols — to the concatenated serializations of all of \(M\)’s transition records (states in order, input and work symbols each in blank/\(0\)/\(1\) order) followed by any bit string \(x\) succeeds, returning the function that assigns to each state, input symbol, and work symbol the corresponding transition of \(M\), together with \(x\) untouched.
For every coded machine \(M\) and every \(m \in \mathbb {N}\), the machine parser applied to the canonical serialization of \(M\) followed by \(m\) additional \(1\)-bits succeeds and returns exactly \(M\).
For every coded machine \(M\) and every \(m \in \mathbb {N}\), the total decoder maps the canonical serialization of \(M\) followed by \(m\) additional \(1\)-bits back to \(M\).
If the unary numeral reader succeeds on a bit string \(x\), returning the value \(n\) and the suffix \(r\), then \(x\) is exactly \(n\) ones, followed by a zero, followed by \(r\).
If the range-checked unary reader with bound \(n\) succeeds on a bit string \(x\), returning an index \(i \lt n\) and a suffix \(r\), then \(x\) is exactly the self-delimiting unary code of \(i\) (\(i\) ones and a closing zero) followed by \(r\).
If the doubled-bit header parser succeeds on a bit string \(x\), returning a data word \(a\) and a suffix \(r\), then \(x\) is exactly the doubled-bit encoding of \(a\) — each bit of \(a\) repeated twice, then the separator \(01\) — followed by \(r\). This includes the case of an empty data word.
If the head-movement reader succeeds on a bit string \(x\), returning a movement \(s\) and a suffix \(r\), then \(x\) is exactly the two-bit dictionary code of \(s\) followed by \(r\).
If the optional-output reader succeeds on a bit string \(x\), returning a value \(b\) and a suffix \(r\), then \(x\) is exactly the two-bit dictionary code of \(b\) followed by \(r\).
If the optional-write reader succeeds on a bit string \(x\), returning a value \(b\) and a suffix \(r\), then \(x\) is exactly the two-bit dictionary code of \(b\) followed by \(r\).
If the successor-state reader with bound \(n\) succeeds on a bit string \(x\), returning a field \(s\) and a suffix \(r\), then \(x\) is exactly the encoding of \(s\) (a single \(0\) for halt, or a \(1\) followed by the unary code of a live state below \(n\)) followed by \(r\).
If the transition-record reader with state-count parameter \(n\) succeeds on a bit string \(x\), returning a record \(a\) and a suffix \(r\), then \(x\) is exactly the serialization of \(a\) — the codes of its five fields concatenated in order — followed by \(r\).
Let a field reader and a field writer for values in a type \(A\) be such that every successful read on a string exhibits that string as the written value followed by the returned suffix. Then whenever the three-symbol row reader succeeds on a bit string \(x\), returning a row \(f\) and a suffix \(r\), the string \(x\) is exactly the concatenation of the written values \(f(\mathrm{blank})\), \(f(0)\), \(f(1)\) followed by \(r\).
Let a field reader and a field writer for values in a type \(A\) be such that every successful read on a string exhibits that string as the written value followed by the returned suffix. Then whenever the length-\(n\) vector reader succeeds on a bit string \(x\), returning a vector \(f\) and a suffix \(r\), the string \(x\) is exactly the in-order concatenation of the written entries \(f(0), \dots , f(n-1)\) followed by \(r\).
A bit string all of whose bits are \(1\) is equal to the constant-\(1\) string of its own length.
If the machine parser accepts a bit string \(x\), returning a coded machine \(M\), then \(x\) is the canonical serialization of \(M\) followed by some number of \(1\)-bits.
Given a validity predicate on pairs of bits, the reader that consumes exactly two bits from its input, succeeds precisely when the consumed pair satisfies the predicate, and returns only the unconsumed suffix. Inputs of fewer than two bits are rejected.
Given a bound \(n\), the reader that consumes a unary numeral (ones terminated by a zero), succeeds precisely when its value is smaller than \(n\), and returns only the unconsumed suffix.
Given a bound \(n\), the reader that consumes a successor-state field — either a single \(0\) (halt), or a \(1\) followed by a unary index that must be smaller than \(n\) — and returns only the unconsumed suffix.
Given a state-count parameter \(n\), the reader that consumes one five-field transition record: four two-bit dictionary fields (input-head movement, work-tape write, work-head movement, output), each validated against its dictionary, followed by a successor-state field over \(n + 1\) states. It returns only the unconsumed suffix.
Given a skipping reader mapping a bit string to an optional suffix, and a count \(n\), the reader that applies the skipper \(n\) times in sequence, threading the suffix through, and returns the final suffix; it fails as soon as any iteration fails.
For every bound \(n\) and bit string \(x\): discarding the parsed index from the result of the range-checked unary reader (keeping only the suffix, or failure) yields exactly the result of the unary index skipper with bound \(n\) on \(x\).
For every bit string \(x\): discarding the parsed movement from the head-movement reader yields exactly the two-bit skipper whose validity predicate accepts a pair \((a, b)\) precisely when \(a\) is \(1\) or \(b\) is \(0\) (that is, it rejects only the pair \(01\)).
For every bit string \(x\): discarding the parsed value from the optional-output reader yields exactly the two-bit skipper whose validity predicate rejects only the pair \(01\).
For every bit string \(x\): discarding the parsed value from the optional-write reader yields exactly the two-bit skipper that accepts every pair of bits.
For every bound \(n\) and bit string \(x\): discarding the parsed field from the successor-state reader with bound \(n\) yields exactly the successor-field skipper with bound \(n\).
For an optional parse result \(r\) — either failure or a pair of a value and a suffix — and a partial continuation \(f\) on suffixes: binding \(r\) through the function applying \(f\) to the suffix component equals first discarding the value component of \(r\) and then binding through \(f\).
For every state-count parameter \(n\) and bit string \(x\): discarding the parsed record from the transition-record reader with parameter \(n\) yields exactly the transition-record skipper with parameter \(n\), which validates the four dictionary fields and the successor field without constructing the record.
For every field reader with values in a type \(A\) and every bit string \(x\): discarding the parsed row from the three-symbol row reader equals iterating the value-discarding version of the field reader three times.
For every field reader with values in a type \(A\), every length \(n\), and every bit string \(x\): discarding the parsed vector from the length-\(n\) vector reader equals iterating the value-discarding version of the field reader \(n\) times.
A variant of the machine parser following exactly the same grammar — doubled-bit canonical state count, minimum-length guard, unary initial state, full transition table, and an all-\(1\) remainder — but returning the decoded coded machine together with the unconsumed all-\(1\) suffix, rather than the machine alone.
The erased parser: it follows the same grammar as the machine parser — doubled-bit canonical state count \(n\), minimum-length guard \(81(n+1)\), a skipped unary initial state below \(n + 1\), then \((n+1) \cdot 3 \cdot 3\) skipped transition records, and an all-\(1\) remainder — but validates the fields without constructing any machine, returning only the unconsumed all-\(1\) suffix.
For every bit string \(x\), the result of the machine parser on \(x\) equals the result of the suffix-retaining machine parser on \(x\) with the suffix component discarded: both fail together, and on success they return the same machine.
For every bit string \(x\), the result of the erased suffix scanner on \(x\) equals the result of the suffix-retaining machine parser on \(x\) with the machine component discarded: both fail together, and on success the scanner returns exactly the unconsumed suffix that the parser would return.
If the suffix-retaining machine parser succeeds on a bit string \(x\), returning a coded machine \(M\) and a suffix \(t\), then \(x\) is exactly the canonical serialization of \(M\) followed by \(t\).
The canonical serialization denoted by a bit string \(x\): if the erased suffix scanner accepts \(x\) with unconsumed suffix \(t\), the result is the prefix of \(x\) of length \(|x| - |t|\) (the consumed part); if the scanner rejects \(x\), the result is the serialization of the fixed fallback machine.
For every bit string \(x\), the canonical serialization denoted by \(x\) equals the serialization of the coded machine that \(x\) decodes to under the total decoder.