title: Limit, logic, and computation.
abstract: We introduce "ultrafilter limits" into the classical Turing model of computation and develop a paradigm for interpreting the problem of distinguishing the class P from NP as a logical problem of decidability. We use P(NP) to denote decision problems which can be solved on a (nondeterministic) Turing machine in polynomial time. The concept is that in an appropriate limit it may be possible to prove that problems in P are still decidable, so a problem whose limit is undecidable would be established as lying outside of P.
authors.affiliation: Microsoft Research 9N, 1 Microsoft Way, Redmond, WA 48052, USA.
authors.forename: M H
authors.initials: MH
authors.lastname: Freedman