Freedman, Michael H. Limit, logic, and computation. (English) Zbl 0891.68041 Proc. Natl. Acad. Sci. USA 95, No. 1, 95-97 (1998). Summary: 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. Cited in 2 Documents MSC: 68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) Keywords:ultrafilter limits; decidability PDFBibTeX XMLCite \textit{M. H. Freedman}, Proc. Natl. Acad. Sci. USA 95, No. 1, 95--97 (1998; Zbl 0891.68041) Full Text: DOI References: [1] THEORY OF ALGORITHMS 44 pp 387– (1985) [2] J DIFF GEOM 2 pp 1– (1968) [3] DOKL AK NAUK USSR 105 pp 32– (1955) [4] PUBLICATIONS MATHEMATIQUES IHES 53 pp 53– (1981) · Zbl 0474.20018 [5] THEOR COMPUT SCI 18 pp 105– (1982) · Zbl 0484.03003 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.