Real time counter mchines preliminary version

Abstract

Parallel ling recent work on time and spacerestricted Turing machine computations, we consider in this paper similar restrictions on counter machines (CM's). Although Turing machines provide a useful model of a computer for the theory of computability, many details in their definition seem unnatural when one considers restrictions on time or space. CM's are as powerful as Turing machines and can be defined formally using little more mathematics than vector addition. For this reason CM's lead to notions of computation time and space which are at least as natural and somewhat more tractable than the corresponding notions for Turing machines. As an example of the tractability of CM's, we obtain a straight forward relation (Theorem Bl) between time and space requirements for CM's. We also prove (Theorem D2) that m+1 counters can generate sequences faster than m counters. The corresponding questions for multitape Turing machines have not yet been settled.