It may be a surprise to some that there are theoretical limits on a computer’s ability. Don’t worry, your next phone will run Angry Birds and Ingress faster than today. But a program that is given another program as input, will never decide whether that program will terminate or run forever. This is known as the halting problem and while it may not practically sound that limiting, it shows that there indeed are limits to what can be done with a computer.
Then there are classes of problems for which there are no known efficient solutions. Even worse, it is not known whether there can be an efficient solutions for these problems. Among computer scientists, this is known as the problem and it is this problem that Lance Fortnow has devoted his new book, The Golden Ticket, to explaining. Continue reading “This book contains The Golden Ticket of computer science”
Hopefully reading Fermat’s Enigma will make up for time I should have been studying. Although, it is a theory of computation class, so it’s apropos, I’m hoping 🙂
For some reason, the story of Andrew Wiles proving Fermat’s Last Theorem had escaped me. I seemed to recall that I knew it was a “theorem” and not a conjecture, but I had never really known the story before. Simon Singh, author of The Code Book, describes the incredible journey of Andrew Wiles’ lifetime passion of trying to prove this problem.
From the human perspective alone, it’s amazing to read how Professor Wiles works in near solitude for eight years, presents his proof, nearly has it shattered in front of his eyes, and recovers! It’s about as exciting as math can get. Along the way, Singh fills in the mathematical history around the problem and while you don’t have to be a mathematician to read the book, well, let’s face it, it’s a book about mathematics, so expect some equations.
Ok… back to studying…