Predecessor machines

摘要

A predecessor machine is a random-access machine with a predecessor operation (i.e., an instruction which subtracts 1 from the contents of a memory cell), but with no operation which can increase the contents of a cell. A regressing function is a partial function which never yields an output larger than the maximum of its inputs and a constant. Unlike the situation for random-access machines with a successor operation, it does not matter whether or not predecessor machines with loop control also have conditional transfer instructions. Furthermore, the class of functions computable by predecessor loop machines consists of exactly those regressing functions which are computable by deterministic linear-bounded automata.