Archive for the ‘proof’ tag
The Halting Problem: There’s No App for That
Think software can do anything? Think again. Theoretical computer scientists have come up with all kinds of airtight proofs about what computers can and cannot do. The most famous of these is the Halting Problem.
Wouldn’t it be nice to have a program that tells you when your software has crashed and will never quit? According to the Halting Problem, no such program exists. And, the proof is actually quite simple.
P vs. NP: The Problem Showdown
P vs. NP: The battle of the new millenium
Mathematics is chock full of unsolved problems. Sometimes a problem can last for centuries before the next genius comes along and solves it. P vs. NP is one of those problems. However, unlike many other unsolved problems, P vs. NP has gotten special attention from educators and the media in recent years.
In this article, we’ll briefly talk about the most popular of unsolved mysteries of theoretical computer science: P vs. NP.