Rise of the Machines II

In my last entry, we introduced a formal definition of a Turing machine (TM). In this article we will look closer at this mental device and see how it works. To begin with, we can examine what a physical TM might look like. I have included a picture from Wikipedia.

Turing Machine Illustration, Wikipedia, (Drawing after Minsky, 1967, p.121)

A TM is made of tape of infinite length, consisting of chain of cells. In each cell there is a symbol which the machine can read or write over, one cell at a time, using the machine’s head. At any given time, the machine is in one of a finite number of states stored on it. It can do basic operations; move right one cell, move left one cell, read, print, erase and change states. By changing from one state to another, the machine can remember previously attained states.…