Time bounded random access machines

摘要

The RAM, an abstract model for a random access computer, is introduced. A unique feature of the model is that the execution time of an instruction is defined in terms of l(n), a function of the size of the numbers manipulated by the instruction. This model has a fixed program, but it is shown that the computing speeds of this model and a stored-program model can differ by no more than a constant factor. It is proved that a T(n) time-bounded Turing machine can be simulated by an O(T(n)·l(T(n))) timebounded RAM, and that a T(n) time-bounded RAM can be simulated by a Turing machine whose execution time is bounded by (T(n))3 if l(n) is constant, or (T(n))2 if l(n) is logarithmic.The main result states that if T2(n) is a function such that there is a RAM that computes T2(n) in time O(T2(n)), and if T1(n) is any function such that liminfn→∞T1(n)T2(n)=0, then there is a set S that can be recognized by some RAM in time O(T2(n)), but no RAM recognizes S in time O(T1(n)). This is a sharper diagonal result than has been obtained for Turing machines.The proofs of most of the above results are constructive and are aided by the introduction of an ALGOL-like programming language for RMA's.