Why are Turing Machines important? - Part 2

An important point that many of the above writers make is that if that problem can be solved by an algorithm (ie. a sequence of finite steps), then a Turing Machine can solve the problem. However, it is also very important to note that the opposite is also true. That is: Any problem of computation that CANNOT be solved by a Turing machine (this includes nondeterministic Turing machines as well as the simpler deterministic systems described above) CANNOT be solved by any known computer. The most famous example of an unsolvable problem is the Halting Problem.

This is the main reason that Turing Machines are so important to the field of Computer Science; They define the ultimate criteria of whether or not a problem is solvable in the general sense.

Of course, the ability to solve a problem is this case assumes alot of things (an arbitrarily large amount of time, a nondeterministic automa, etc). Therefore, it is important to note that while a problem may be solvable in the Turing Machine sense, the reality may be that the problem will not be solvable in any useful manner.