Simple programming languages and restricted classes of turing machines

AbstractIn this paper we investigate the computational power of simple programming languages and provide characterizations (or partial characterizations) of the functions computable by such programs in terms of some space and/or time complexity classes of Turing machines. Call a function f(x1,…,x1) over the nonnegative integers linearly bounded if f(x1,…,x1)< O(x1+…+x1). We show that any linearly bounded function f(x1,…,x1) computable by a Turing machine in O(n) space and O(2λn) time, where λ<1 and n=¦x1+…+x1¦ is the length of the binary representation of x1+…+x1, can be computed by a program without nested loops using only the instruction set R=x←x−1, if x=0 then y←y+1, do x…lcubendrcub. Thus, functions like ¦xy¦, ged{x,y}, xk, [log x], etc. can be computed by R-programs. Any function computable by an R-program can be computed by a Turing machine in O(n) space and O(2n) time. It is open whether or not the time can be reduced to O(2λ) for some λ