Turing Machines

I been reading up on Chaitin's number recently, and I thought I would record my understanding of it. This is a (real) number that has an interesting contruction and some pretty far reaching consequences in logic and philosophy of math. Informally it can be thought of as the probability that a randomly chosen string of bits that encodes a program will halt. I don't normally talk about automa theory on this blog, so let me go slowly. This will be the start of some posts that I hope will culminate in a passable discussion of Chaitin's number and its relation to incompleteness. Starting out, however, I will give a pretty handwavy and informal definition of a Turing Machine.

A Turing Machine is an abstract machine that can perform any computations whatsoever, by definition. It is the basic assumption of computer science that if something can be computed then it can be computed by a Turing Machine. A Turing Machine is given as follows- (W, R, d, S, F, i) where W is the working set of symbols, and contains the set of symbols R, as well as the special symbols _ and |. S is the set of states the machine can be in with F a subset called the halting states (if the machine gets into one of these states it has finished computing). The state i is an element of S and is called the initial state (for obvious reasons).The function d is defined as d:SxW->SxWx{->, <-} (the arrows indicate a direction to move) which, given the current state of the machine and a symbol, gives the new state and the symbol the machine should "output", or write to its tape and the direction the read head should move. The idea of the tape is a sequence of places that have a symbol from the working set written on them. The machine is, at any time, looking at one of these places. It will use the information of its current state and the symbol it is looking at to either write a symbol from its symbol set R on that location and will move left, move right, and change its internal state.

The tape can be given by a finite string of symbols from W followed by an infinite string of _ symbols (which represents a blank location). The symbol | is at the very left-most location, and the function d must write | when it sees | and must move to the right. This is one way to stop a machine from "falling off" the left end of the tape (we can also make it infinite in both directions). Notice that the tape doesn't really have to be infinite- it must only be "long enough" to finish whatever computation we are doing. We can imagine that if the machine if ever about to move to the right and there is no more tape there, we simply tack on some additional locations. This is important because for a machine that eventually halts on its input, we will only need a finite tape, and therefore the machine itself isn't really infinite, yet we can sidestep the need to say exactly how large it is. If we had to give a fixed size, there would always be a problem that needed just a little more than we gave ourselves, so we just assume we always have more tape laying around (all of this is informal of course).

If we have some initial tape and the machine is initially in its initial state i and its initial location is the head of the tape. Execution proceeds by passing the current state (the machine itself can be thought of as a finite state machine with this infinite tape to keep as memory) and the symbol in the current location to the transition function d, and writing the resulting symbol to the location, moving into the resulting state, and moving in the resulting direction. If the new state is in the set of halting states, then the machine does not continue executing. More formally, if at time t the machine is in a state s that is a member of F then the tape at time t+n for all n is the same as at time t (no changes can be made to it).

So- this is the first step in understanding Chaitin's number. If this is interesting to you, please find a more detailed and rigorous definition before excepting this one. There are many ways to do this construction and some are easier in different situations.