Tuesday, April 7, 2009

Universal Turing Machine

Every Turing machine reads a set of symbols which you can call input or also fixed partial computable function which is accepted from the input strings over its alphabet. In this sense it behaves like a computer with a fixed program. However, it is really possible to encode the action table of any Turing machine in a string. Hence a Turing machine can be constructed that expects on its tape a string describing an action table followed by a string describing the input tape, and then it can compute the required result. I must tell you that the Turing described such universal machine in great detail when he wrote a paper in the year 1936.

In 1947, Turing said that "It can be shown that a single special machine of that type can be made to do the work of all. It could in fact be made to work as a model of any other machine. The special machine may be called the universal machine".

I must tell you that there are four kinds of grammar respectively type 0 grammars, type 1 grammar, type 2 grammars and the type 3 grammar. The Turing machine takes the type 0 grammar as the input. The others are accepted by the other machines like push down automata.

If you want to develop the universal Turing machine then you will have to develop the table at first. The table clearly mentions the initial and the final state with correspondence to each input. In this way you will be able to develop a table. You must know that the Turing machine consist of seven tuples. You will have to define the transition state function.

Turing machine is really an attempt to make the machine which will provide the artificial intelligence.
As you will develop the encoding of action tables as strings it becomes possible in principle for Turing machines to answer questions about the behavior of other Turing machines. However I must add that most of such questions are really not decidable. This really gives us one clue and that is that the function in question cannot be calculated mechanically. You can take as an example the halting problem in which you will have to decide whether any Turing machine will halt at the input of any input or on all inputs. This was generally shown to be not decidable when the paper was presented in the year 1936 original paper. You can also check for the rice theorem which shows that any non-trivial question about the behavior or output of a Turing machine is not decidable.

I really feel that the Turing machine was really a very good attempt by one of the all time great scientist and that is the Turing.