Polynomial time computations in models of ET

摘要

This paper investigates formal notions of computation in nonstandard models of the weak arithmetic theory ET—the theory of exponential time. It is shown that ET is sufficiently weak that many of the natural notions of computation are not preserved. A slightly richer theory ET(Elem) is introduced and it is shown that all sets that have infinitely many easily decidable initial segments are easily decidable in certain nonstandard models of this theory.