Simple programming languages and restricted classes of Turing machines (Q792760): Difference between revisions

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.