Full multiplication bound at κ = 0.000051016920170078

There exist a single deterministic Turing machine $M$ of the following kind, a positive real constant $c$, and a natural-number threshold $n_0$, with the correctness and running-time properties below. The machine has a fixed finite number $k\ge 2$ of tapes, each with cells indexed by the nonnegative integers; a finite alphabet containing five pairwise distinct symbols $\square,\triangleright,0,1,\#$; and a finite set of states containing distinct start and halt states. Tape $0$ is the read-only input tape, tape $1$ is the output tape, and the other tapes are available for work. Its total deterministic transition function takes a state and the $k$ symbols under the heads and returns a new state together with one symbol to write and a left, stationary, or right movement for each tape. In one step all scanned cells are updated, the state changes as prescribed, and all heads move accordingly; a left movement replaces position $p$ by $\max(p-1,0)$. For every state and every tuple of scanned symbols, a scanned $\triangleright$ must be rewritten as $\triangleright$ and its head must stay or move right, a different scanned symbol may never be replaced by $\triangleright$, and the symbol on the input tape must be rewritten unchanged. In the halt state, every transition leaves the state, scanned symbols, and head positions unchanged. For each natural number $n\ge 1$, there exists a real number $T_n$ such that, for every pair of Boolean lists $x,y$ each of length exactly $n$, there exists a natural number $t$ with $t\le T_n$ for which the following holds: starting in the start state with every head at cell $0$, with input tape $\triangleright x\#y\square\square\cdots$ (false bits represented by $0$ and true bits by $1$), and with every other tape $\triangleright\square\square\cdots$, after exactly $t$ transitions the state is the halt state and the entire output tape is $\triangleright w\square\square\cdots$. Here the integer represented by $x=(x_1,\ldots,x_n)$ is $v(x)=\sum_{j=1}^{n}x_j2^{n-j}$, identifying false and true with $0$ and $1$, and similarly for $y$; $w$ is the list of exactly $2n$ bits whose bit in position $j$, for $1\le j\le 2n$, is bit number $2n-j$ of the natural number $v(x)v(y)$, with bit number $0$ the least significant bit. Thus $w$ is the product's binary representation in most-significant-bit-first order, padded on the left with zeros to length $2n$; the product fits in that length. Moreover, for every natural number $n$ satisfying both $n_0\le n$ and $1\le n$, and every such pair $x,y$, there exists a natural number $t$ for which the same halt-state and exact whole-output-tape condition holds and

The decimals here denote exact real numbers, and the exponentiation and displayed time bound use real arithmetic. The machine, its tape count, alphabet, state set, transition function, $c$, and $n_0$ are fixed independently of $n,x,y$; $T_n$ may depend on $n$ but not on $x,y$, and the witnessing time $t$ may depend on the inputs. Inputs may have leading zeros, including all-zero inputs, and $L(1)=1$. The threshold $n_0$ may be $0$, but no computation or running-time requirement is imposed for $n=0$, for unequal input lengths, or for other input formats. No condition is imposed on the final head positions or work-tape contents.