upcarta
  • Sign In
  • Sign Up
  • Explore
  • Search

Limit, logic, and computation

  • Paper
  • Sep 27, 1997
  • #ComputerScience
Michael Freedman
@MichaelFreedman
(Author)
www.pnas.org
Read on www.pnas.org
1 Recommender
1 Mention
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 log... Show More

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.

Show Less
Recommend
Post
Save
Complete
Collect
Mentions
See All
Michael Nielsen @michael_nielsen · Jan 27, 2022
  • Post
  • From Twitter
(I've always liked this idea. It probably goes nowhere, but it's just so imaginative! And the paper is a treat to read - lots of very interesting conceptual paragraphs.)
  • upcarta ©2025
  • Home
  • About
  • Terms
  • Privacy
  • Cookies
  • @upcarta