Counter machines and counter languages

Abstract

The languages recognizable by time- and space-restricted multiple-counter machines are compared to the languages recognizable by similarly restricted multipletape Turing machines. Special emphasis is placed on languages definable by machines which operate in "real time". Time and space requirements for counter machines and Turing machines are analyzed. A number of questions which remain open for time-restricted Turing machines are settled for their counter machine counterparts. © 1968 Springer-Verlag New York Inc.