There are many references to it in public discussions, but trying to learn about it from Wikipedia is like reading in a new foreign language.
In: 283
I see a lot of answers describing the machine, but I want to give a little background on why this machine was even thought up.
The core idea that the Turing machine tries to capture is *computability*. Think of a problem with a numeric answer. How many ways are there to arrange a deck of cards? Or what is the shortest amount of time it would take to get from San Francisco to LA by car? Those questions have *computable* answers. The cards question is pretty simple, just take a deck and methodically count the arrangements. The car question is a bit more complex, but given a map you could calculate which route would be the shortest.
But it turns out there are some problems with numeric answers that *aren’t computable*. You can verify the answers, but there’s no way to calculate the answer from scratch. One such problem is called the halting problem: how long will a computer take to run an algorithm? This is easy to verify if you have the answer, just run the algorithm and see if it matches your answer. But it turns out that it’s impossible to calculate this before hand. You can make educated guesses, but you cannot compute an exact answer
This is where Turing machines come in. Once you prove a few things about Turing machines, you can use them to prove things about algorithms and whether or not they are computable.
Latest Answers