Search code examples
algorithmmathinfiniteautomataturing-machines

What is the difference between a Turing Machine and an Algorithm?


According to my understanding, the Turing machine is just a machine representation of an algorithm. Is there any difference between an algorithm and a Turing machine?


Solution

  • They are very different.

    An algorithm is a procedure. It can be specified in a wide variety of ways, usually by writing down a program in some programming language. By contrast Turing machine describes a procedure adapted to run on a very specific and unrealistic machine.

    However the characteristics of the algorithm depend on the machine that it runs on. And Turing machines look nothing like any machine of real-world interest. Therefore while every algorithm can be represented by a Turing machine, Turing machines are not the preferred representation. And the Turing machine representation obscures the most interesting properties of the algorithm.

    For example merge sort is widely known to be O(n log(n)). It scales that way for everything from Donald Knuth's artificial MIX architecture from the 1960s to highly parallelized distributed implementations in the cloud today.

    But in a Turing machine, iterating through two arrays in parallel and writing to a third requires constantly seeking back and forth between two distant places in tape to compare them, then seeking again to find where to write the output. Therefore while you can build a Turing machine that implements a recognizable merge sort, but it WON'T be O(n log(n)). Not by a country mile. And in fact will perform much worse than a bubble sort. (Because bubble sort only compares things close on tape, so spends less time seeking back and forth.)