## Computability Turning Machines are a simple, purely hypothetical, machines that have allowed computer scientists/mathematicians to conclude very profound pr

## Computability Turning Machines are a simple, purely hypothetical, machines that have allowed computer scientists/mathematicians to conclude very profound properties of computation. Although they are mentioned with some frequency here, it's not a subject that most of us have any training in. I had the good fortune to study computer science while in college many years ago. There was a lot less to learn back then and I was introduced to the theory of computation at the undergraduate level. For those that haven't had the pleasure of problem sets covering Turing Machines but would like to learn something about them, I recommend the Stanford Encyclopedia of Philosophy entry on Turing machines [1]. It goes into more depth than Wikipedia while being very easy to understand. Turing machines are extraordinarily simple, much simpler than any real computer. The fact that Turing Machines deserve an entry in a Philosophy reference is because of their power in elucidating the very nature of computation. About 80+ years ago, it was discovered that the set of problems that can be solved/computed by a Turing Machine is exactly the same set that can be solved with the Church's Lambda Calculus, [2] and recursive functions as formalized by Gödel's [3]. This, to me surprising, result led to the Church-Turing thesis: the hypothesis that any effectively computable (i.e. solvable through some mechanistic procedure) can be solved by a Turning Machine. From this we know, for example, that true algorithms don't exist for a whole host of problems. This isn't the same claim that some problems are hard and don't have tractable exact solutions (e.g. the knapsack problem or the traveling salesman problem [4]); there are algorithms for these problems--they simply take a very long time. Some interesting problems on the other hand have no algorithm at all. This can be shown by demonstrating that no Turing Machine could be constructed to solve the problem (e.g. the halting problem [5]). What about quantum computers? They look like an approach so different and so powerful that maybe they will provide a stronger model of computation than that limited by the bounds of Church-Turing. Unfortunately, the qubit based approaches that we are now pursuing have been demonstrated to be "equivalent" to classical (Turing) machines, just with different performance time/space tradeoffs. So qubit based quantum computers may someday solve challenging, exponential time problems, but they won't solve every problem. ## Turing machines Turing's insight was that any mechanical procedure for computation could be modeled by a simple machine, the Turing Machine. A Turing Machine has a "tape", think of it as an infinite strip of paper divided into cells, like an infinite array: tape[k]. Each cell can hold a symbol from some finite alphabet. There is a single read/write head positioned at a location on the tape. The head can read a symbol from the location or erase/write a symbol the location, and then it can move one location left or right. Turing machines also have a state from some finite range of states, say 1...N. One state is designated as the initial state. Finally, there is a state transition table in the Turing Machine that determines its operation. For each combination of (1) current state and (2) current symbol under the read/write head, the transition table gives (a) the new internal state and (b) the symbol that should be written on the tape at the current location and (c) the direction the head should move--left or right. When I first saw the definition of a Turing Machine, I thought that it looked unlike a computer. The state table seemed to encode the entire operation of the machine. It could potentially be a huge table of specific operations to solve some problem. Turing machines seemed to me to be special purpose constructions unlike the more flexible architectures of programmable computers. Indeed, we studied a number of different Turing Machines that would solve simple problems with inputs from the tape. The big surprise for me was seeing a Universal Turing Machine. It turns out that there are Turing Machines, having a fixed reasonably small state transition table that can do anything that any other Turing Machine can do. These "Universal" machines use a program on the tape that provides the instructions to process the remaining input data from the tape. The idea of a Turing Machine doesn't rely on lots of states, a few is enough to construct a universal machine. Likewise, there are Universal machines that need a tape that extends in only one direction and tape vocabularies that have a very limited number of symbols. [1] https://plato.stanford.edu/entries/turing-machine/ https://plato.stanford.edu/entries/turing-machine/ [2] https://plato.stanford.edu/entries/lambda-calculus/ https://plato.stanford.edu/entries/lambda-calculus/ [3] https://plato.stanford.edu/entries/recursive-functions/ https://plato.stanford.edu/entries/recursive-functions/ [4] https://en.wikipedia.org/wiki/Travelling_salesman_problem https://en.wikipedia.org/wiki/Travelling_salesman_problem [5] https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Halting_problem