Karatsuba–Ofman: multiplication in time $O(n^{\log_2 3})$ on a multitape Turing machine

Theorem IntMul.TM.karatsuba. Let

where the exponent is the real number $\log_2 3 = \ln 3/\ln 2 \approx 1.585$ and the power is the real power function (for $n \ge 1$ the base is positive, so this is the ordinary value $e^{(\log_2 3)\ln n}$). The theorem asserts that there exists a deterministic multitape Turing machine $M$ such that:

1. (Correctness for every $n \ge 1$.) For every $n \ge 1$ and all bit strings $x, y \in \{0,1\}^n$ (leading zeros allowed), $M$ started on input $x\#y$ halts after finitely many steps with output $\mathrm{bin}_{2n}(\mathrm{val}(x)\cdot \mathrm{val}(y))$ (no time bound required in this clause).
2. (Time bound.) There exist a real constant $c > 0$ and a threshold $n_0 \in \mathbb N$ (both chosen after $M$, independent of $n, x, y$) such that for every $n$ with $n \ge n_0$ and $n \ge 1$ and all $x, y \in \{0,1\}^n$, $M$ on input $x\#y$ reaches the halting state with that output within some $t \le c\, g(n)$ steps.

Definitions unfolded. $\mathrm{val}(x) = \sum_{i} x_i 2^{|x|-1-i}$ reads $x$ as binary with the first (leftmost) bit most significant; $\mathrm{val}(\varepsilon)=0$. $\mathrm{bin}_{2n}(z)$ is the length-$2n$ list whose $i$-th entry ($i = 0,\dots,2n-1$) is bit number $2n-1-i$ of $z$, i.e. $z$ written MSB-first, left-padded with zeros to exactly $2n$ bits; since $\mathrm{val}(x)\mathrm{val}(y) < 2^{2n}$ this is the exact product. "Started on input $x\#y$" means: state $q_{\mathrm{start}}$, tape $0$ holds $\triangleright\, x\, \#\, y\, \square\square\cdots$ (bits as symbols $\mathtt 0/\mathtt 1$), every other tape $\triangleright\square\square\cdots$, all heads at cell $0$. "Halts with output $w$ at step $t$" means: after exactly $t$ steps the state is $q_{\mathrm{halt}}$ and the whole output tape (tape $1$) is $\triangleright\, w\, \square\square\cdots$ — no other non-blank cells; work tapes and head positions are unconstrained. Since $q_{\mathrm{halt}}$ freezes the configuration, "some $t \le T$" is the same as halting within $T$ steps. The machine model: finite alphabet containing pairwise distinct $\square, \triangleright, \mathtt 0, \mathtt 1, \#$ (plus any extra symbols), finite state set with $q_{\mathrm{start}} \ne q_{\mathrm{halt}}$, $k \ge 2$ one-way-infinite tapes (tape $0$ input, read-only; tape $1$ output; the rest work tapes; $k$ fixed by $M$), $\triangleright$ only in cell $0$ and never moved left from, one step = simultaneous write/move on all tapes.

Edge cases. $n = 0$ (input "$\#$") is not constrained at all. Inputs with $|x| \ne |y|$, or not of the form $x\#y$, are not constrained. $g(n) \ge 1 > 0$ for all $n \ge 1$, so no degenerate values arise. Small $n < n_0$ are covered only by the untimed correctness clause. The statement concerns a single machine for all $n$ (uniform), with only a big-$O$ (eventual, constant-factor) bound — no explicit constant.