Two-Tape Simulation of Multitape Turing Machines

摘要: It has long been known that increasing the number of tapes used by a Turing machine does not provide ability to compute any new functions. On other hand, use extra make it possible speed up computation certain is square factor sometimes required for one-tape behave as two-tape and always sufficient.The purpose this paper show that, if given function requires time T k-tape realization, then at most log realization. The proof fact constructive; machine, shown how design an equivalent operates within stated bounds. In addition being interesting in its own right, trade-off relation between can be diagonalization argument T(n) U(n) are two functions such inf ÷ = 0 there exists computed bound but T(n).