A note on simple programs with two variables
type: Item
instance of: scholarly article
title: A note on simple programs with two variables
zbMATH Open document ID: 0785.68033
DOI: 10.1016/0304-3975(93)90028-R
author: Oscar H. Ibarra
author: Nicholas Q. Tran
published in: Theoretical Computer Science
publication date: 1993-05-24T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68N01
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 11Y16
zbMATH DE Number: 178045
zbMATH Keywords: counter machines
zbMATH Keywords: simple programs
zbMATH Keywords: partial recursive functions
zbMATH Keywords: recursively enumerable sets
MaRDI profile type: Publication
cites work: Q5547585
cites work: Q4100083
cites work: Q5772619
cites work: Q3862379
cites work: The Power of Alternating One-Reversal Counters and Stacks
cites work: Q3999066
cites work: Q5590814
full work available at URL: 0304-3975(93)90028-r
OpenAlex ID: W2062671195
description: scientific article; zbMATH DE number 178045