[FOM] 2,3 Turing machine proof controversy

[Kreinovich, Vladik]

This (and more general) idea is implemented in a known extension of
Turing machines which was
specifically designed to take into account the possibility of adding
new cells and/or new processors. This extension was originally
proposed by Kolmogorov and Uspensky in the 1950s; overviews of the
resulting Kolmogorov-Uspensky
algorithms can be found, e.g., in Gurevich's papers (since
Kolmogorov-Uspensky algorithms served as a basis for the
notion of an Abstract State Machine). Such algorithms are known to have
several advantages over more traditional Turing machine-type
definitions: e.g., Leonid Levin
used a universal Kolmogorov machine to construct his algorithm for
NP problems that is optimal up to a multiplicative constant. The
up-to-a-multiplicative-constant form is not believed to be
achievable for the multi-tape Turing machine model.

> From Clive Gifford

> Let us now imagine an augmented version of  Turing's original model by
> specifically including a tape extension unit (TEU) of some kind or
another,
> which we can consider as a separate component within the larger
system.