2 docs tagged with "turing-machine"

What does it mean for a machine to "guess perfectly" — and why that strange idea is at the heart of the entire P vs NP problem.

Before we can talk about fast or slow algorithms, we need to agree on what computation even means — and that meaning comes from a deceptively simple thought experiment invented in 1936.