On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machines
Wolfgang Maass · Journal of Symbolic Logic · 1988
Abstract We prove optimal lower bounds on the computation time for several well-known test problems on a quite realistic computational model: the random access machine. These lower bound arguments may be of special interest for logicians because they rely on finitary analogues of two important concepts from mathematical logic: inaccessible numbers and order indiscernibles.