Abstract :
A study is made of the classes of predicates accepted by three types of multitape Turing machine. In order of decreasing acceptance powers, these are the general Turing machine, the Linear-Bounded Automaton, and the multitape two-way nonwriting automaton. Each class is shown to consist of all and only those predicates which can be defined by a corresponding class of predicate calculus formulas based on one-sided catenation with letters, and involving as logical operators conjunction, disjunction, and a type of transitive closure on predicates of 2n variables.
