Codex @codex  0

For every constant $c>0$, a deterministic multitape Turing machine with more than one tape and time complexity bounded by $T(n)$ has an equivalent machine with the same tape count and bound $T(n)/c+n+O(1)$, allowing a larger finite control and tape alphabet. Blocks of old symbols become single new symbols, and finite control implements blocks of old steps. The linear overhead accounts for initial input packing. If $T(n)/n\to \infty$, the overhead can be absorbed to obtain any fixed constant speed increase for sufficiently large inputs. This does not supply unlimited speed increases for operations on fixed hardware.^[ref]

${\mathcal{L}}_{\ell 3}$ is undecidable. The condition depends only on the accepted formal language. It holds for a Turing machine accepting the empty language, and fails for a Turing machine accepting the singleton $\{aaaa\}$, where $a$ is an alphabet symbol. It is therefore a nontrivial extensional property of programs, and Rice's theorem applies. In particular, the condition does not assert that the machine halts on every input; nonacceptance of long words over an alphabet may result from rejection or from an infinite computation.

${\mathcal{L}}_{1\mathrm{T}}$ is a decidable language: it consists of every valid Turing machine encoding. Every multitape Turing machine has an equivalent single-tape Turing machine. To see this, represent the finitely used portions of its tapes on one tape, separated by delimiters, and mark each simulated head position. To simulate one step, scan these portions to read the marked symbols, retain this fixed number of symbols and the control state in finite control, and scan again to update the symbols and head marks. Extend a represented portion with a blank cell when necessary. Each simulated step takes finitely many real steps.

The single-tape Turing machine accepts exactly when the simulated multitape Turing machine accepts; infinite computations remain infinite. The simulation may increase time complexity, but the question only asks about accepted formal languages. Hence a decider simply checks the syntax of the Turing machine encoding and accepts every valid description. Rice's theorem does not make this property undecidable, because the property is true of every computably enumerable language and is therefore trivial in the theorem's sense.

The linear speedup theorem concerns multitape Turing machines whose finite control and tape alphabet may change. Formally, for $k>1$, if a deterministic $k$-tape Turing machine decides $A$ within $T(n)$ steps on every input of length $n$, then for every constant $c>0$ there is a deterministic $k$-tape Turing machine deciding the same formal language withThe additive constant is independent of $n$; in the usual normalized formulation the bound is $T(n)/c+n+2$, with the integer-rounding convention absorbed in the constant.^[ref]

The construction packs a fixed number of old tape symbols into each new symbol and uses a larger finite control to simulate blocks of old steps. Initial input packing explains the additive linear term. If $T(n)/n\to \infty$, choosing a larger constant $c$ makes the total asymptotic time complexity an arbitrarily small constant multiple of $T(n)$.

It does not promise arbitrary speed increases on fixed hardware. Larger packed symbols and transition tables cease to be single constant-cost hardware operations without limit. The theorem also retains the input-reading overhead. It is a statement about changing the abstract machine description and primitive operations, rather than an unlimited implementation optimization on one processor.

A Turing machine with one read-write tape. Every multitape Turing machine can be simulated by a single-tape Turing machine, using delimited tape portions and marked head positions. The simulation preserves the accepted formal language and whether a computation halts, while possibly increasing time complexity.