Single-head tapes are used to simulate multihead Turing machine tape units without loss.For one-dimensional tapes, the new simulations are simpler and use far fewer tapes than prevj known simulations.For multidimensional tapes, the results are entirely new.

Given a sequence $n_1 , \cdots ,n_m $ of positive integers, what is the smallest number of additions needed to compute all m integers starting with 1? This generalization of the addition chain ($m = 1$) problem will be called the addition-sequence problem. We show that the sequence $\{ 2^0 ,2^1 , \cdots ,2^{n - 1} ,2^n - 1\} $ can be computed with $n + 2.13\sqrt n + \log n$ additions, and that $n + \sqrt n - 2$ is a lower bound. This lower bound result is applied to show that the addition-sequence problem is NP-complete.

Just as the Church-Turing thesis has simplified proofs of computability [8], efficient simulations of one computer model by another have simplified proofs of complexity upper bounds. A good example of this is Fischer, Meyer, and Rosenberg's real-time simulation of multihead Turing machines by multitape Turing machines [5]. Without this result, for example, even Slisenko [11] may have found it hopeless to show that a multitape Turing machine can recognize palindromes in real time. In this paper we give a comparatively simple proof of the Fischer-Meyer-Rosenberg result, dramatically reduce the number of single-head tapes required for the simulation, and generalize the result to multidimensional tapes. In the case of Slisenko's palindrome-recognizer, for example, our best simulation brings the number of tapes for a multitape Turing machine implementation down from 41 to 20.

The concept of grammar forms [4,5] provides evidence that there seems to be no way to base the definitions of many grammar types used in parsing and compiling solely on the concept of productions.