Mathematical proofs based on a technique called diagonalization can be relentlessly contrarian, but they help reveal the limits of algorithms. The post Alan Turing and the Power of Negative Thinking first appeared on Quanta Magazine
Algorithms have become ubiquitous. They optimize our commutes, process payments and coordinate the flow of internet traffic. It seems that for every problem that can be articulated in precise mathematical terms, there’s an algorithm that can solve it, at least in principle. But that’s not the case — some seemingly simple problems can never be solved algorithmically.