What's a Turing machine?

Question

What is a Turing machine and why do people keep mentioning it? My IBM PC is all I need to do my computation! Why does anyone care about these machines?

Answer 1

It's an abstraction for the most general class of computing devices that is useful in analyzing certain algorithms and certain problems in computability and complexity. It's the most capable of the three classes of abstract machines:

1. Finite State Machines, which can recognize regular expression grammars (https://en.wikipedia.org/wiki/Finite-state_machine)
2. Push-down Automata, which can recognize context-free grammars problems (https://en.wikipedia.org/wiki/Pushdown_automaton)
3. Touring Machines, which can solve any solvable problem in the domain of human algorithms (https://en.wikipedia.org/wiki/Turing_machine)