Simple programming languages and restricted classes of Turing machines

Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60)

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.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Simple programming languages and restricted classes of Turing machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q792760)