A note on simple programs with two variables (Q1210303)

Simple programs are programs consisting of only the following constructs: \(\{x \leftarrow x+1\), \(x \leftarrow x \dot-1\), if \(x=0\) then goto \(l\), goto \(l\), halt\}. Minsky showed that simple programs using three variables compute all partial recursive functions with one argument, and hence they recognize all recursively enumerable sets. It is clear that simple programs using a single variable compute only trivial functions. On the other hand, simple programs using two variables are surprisingly powerful: Minsky's result implies that they can compute recursive functions growing arbitrarily large in value, and that they accept all sets \(S'=\{2^ s:s \in\) recursive set \(S\}\). However, Barzdin showed that simple programs using two variable do not compute all partial recursive functions with one argument. We improve this result by showing that simple programs using two variables do not recognize all recursively enumerable sets. Counterexamples include the set of prime numbers and the sets \(L_ e\) of integers raised to the \(e\)th power for some fixed integer \(e \geq 2\).