Limit, logic, and computation

AUTOR(ES)

Freedman, Michael H.

FONTE

The National Academy of Sciences

RESUMO

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.

Documentos Relacionados

• No evidence backs reduction in abortion time limit, minister says
• Logic, signs and nature in the Renaissance: the case of learned medicine
• DIGITAL COMPUTATIONAL METHODS IN SYMBOLIC LOGIC, WITH EXAMPLES IN BIOCHEMISTRY*
• DIGITAL COMPUTATIONAL METHODS IN SYMBOLIC LOGIC, WITH EXAMPLES IN BIOCHEMISTRY
• BOOK REVIEW: CARNIELLI, W., CONIGLIO, M. Paraconsistent Logic: Consistency, Contradiction and Negation. Logic, Epistemology, and the Unity of Science Series. (New York: Springer, 2016. ISSN: 2214-9775.)