zbMATH — the first resource for mathematics

A note on simple programs with two variables. (English) Zbl 0785.68033
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\).
Reviewer: N.Q.Trân

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68N01 General topics in the theory of software
68Q25 Analysis of algorithms and problem complexity
11Y16 Number-theoretic algorithms; complexity
Full Text: DOI
[1] Barzdin, I.M., Ob odnom klasse machin turinga (machiny minskogo), Russian, Algebra i logika, 1, 42-51, (1963)
[2] Börger, E., Recursively unsolvable algorithmic problems and related questions reexamined, (), 10-24, (Kiel, 1974)
[3] Hardy, G.H.; Wright, E.M., An introduction to the theory of numbers, (1959), Oxford University Press Ely House, London · Zbl 0020.29201
[4] Hopcroft, J.; Ullman, J., Introduction to automata theory, languages, and computation, (1979), Addison-Wesley Reading, MA · Zbl 0426.68001
[5] Ibarra, O.; Jian, T., The power of alternating one-reversal counters and stacks, SIAM J. comput., 20, 278-290, (1991) · Zbl 0722.68054
[6] Ireland, K.; Rosen, M., A classical introduction to modern number theory, (1990), Springer New York · Zbl 0712.11001
[7] Minsky, M., Computation:finite and infinite machines, (1967), Prentice Hall Englewood Cliffs, NJ
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.