if two or more registers are available then the simpler INC, DEC etc. are adequate (but the Gödel number is still required to demonstrate Turing equivalence; also demonstrated in Elgot-Robinson 1964).

Formal definition

A counter machine consists of:
# Labeled unbounded integer-valued registers: a finite (or infinite in some models) set of registers r₀ ... r_n each of which can hold any single non-negative

1.Previous
3.Next