Simple programming languages and restricted classes of Turing machines
type: Item
instance of: scholarly article
title: Simple programming languages and restricted classes of Turing machines
zbMATH Open document ID: 0537.68045
DOI: 10.1016/0304-3975(83)90085-3
author: Oscar H. Ibarra
author: Louis E. Rosier
published in: Theoretical Computer Science
publication date: 1983-01-01T00:00:00Z
review text: The computational power of simple programming languages is investigated and characterisations (or partial characterisations) of the functions computable by such programs are given in terms of some space and/or time complexity classes of Turing machines. Calling a function \(f(x_ 1,...x_ t)\) over the nonnegative integers linearly bounded (LBF) if \(f(x_ 1,...,x_ t)\leq 0(x_ 1+...+x_ t),\) it is shown that any LBF computable by a Turing machine in 0(n) space and \(0(2^{\lambda n})\) time, where \(\lambda<1\) and n is the length of the binary representation of \(x_ 1+...+x_ t,\) can be computed by a program without nested loops using only the instruction set \(R=\{x\leftarrow x\dot-1\), if \(x=0\) then \(y\leftarrow y+1\), do \(x...\) end\}. Thus, functions like \(\lfloor x/y\rfloor\), \(\gcd \{x,y\}\), \(\lfloor^ k\sqrt{x}\rfloor\), \(\lfloor \log x\rfloor\), etc. can be computed by R-programs. Any function computable by an R-program can be computed by a Turing machine in \(0(n)\) space and \(0(2^ n)\) time. It is open whether or not the time can be reduced to \(0(2^{\lambda n})\) for some \(\lambda<1\) (which may depend on the program). Simple programming languages are also introduced which are complete characterisations of the functions computable by certain space bounded (linear bounded, polynomial bounded, etc.) classes of Turing machines.
reviewed by: J.Tanko
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q60
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 03D60
zbMATH DE Number: 3854418
zbMATH Keywords: computational power of simple programming languages
zbMATH Keywords: complexity classes of Turing machines
MaRDI profile type: Publication
full work available at URL: 0304-3975(83)90085-3
OpenAlex ID: W2009880057
cites work: Loop-programs and polynomially computable functions
cites work: Simple Programs Realize Exactly Presburger Formulas
cites work: A Complete and Consistent Hoare Axiomatics for a Simple Programming Language
cites work: Counter machines and counter languages
cites work: Predecessor machines
cites work: The Complexity of the Equivalence Problem for Simple Programs
cites work: Q3664434
cites work: A characterization of time complexity by simple loop programs
cites work: Q5590814
cites work: Q4162478
cites work: The Equivalence Problem of Simple Programs
description: scientific article; zbMATH DE number 3854418