4.3. Representation of Turing machines

The specification of a Turing machine means to give a description of five tuple in the general definition. For the objects and it is not a great adventure but for the transition function requires a bit more efforts. Since it is a function defined on a finite domain with values from a finite set, fortunately there are no big difficulties to manage.

The different representations are explained on two particular Turing machines.

The first Turing machine executes a parity bit encoding on words over the alphabet . This is a typical transformation task. Prefix preserving, but not length preserving mapping. The essence of the encoding is that one have to count the number of symbol 's in the input word and extend it by a new symbol such that the number of 's in the output should be even. This transformation is one of the most simple but most efficient, widely applied error detection encoding.

Examples: (Parity bit addition)

In: Out:

In: Out:

At the real life application equal word length is assumed, but here we simply don't care about this restriction.

The second Turing machine checks whether the input word satisfies the parity property or not, i.e. if there are even number of 's in it. If the answer is yes, then we accept the word, if no, then we reject it.

4.3.1. Look up table representation:

With look up table representation, the transition function can be given in several ways. In one of them the columns of the table are related to the different states, while the rows are related to the possible input symbols, read by the read-write head. The values in the table are the function values at the corresponding arguments.

If the transition function is not everywhere defined (partial function), the table contains gaps.

Example: Parity bit addition

One possible solution for the task is the following Turing machine:

where

,

, and

:

Figure 4.2. Parity bit addition to the input word

Parity bit addition to the input word

Here is the final state, is the initial state and in the same time it has the notion, that the processed part contains even number of 's. Furthermore, has the notion, that the processed part contains odd number of 's. The states and are for moving the read-write head and remembering to the parity.

The Turing machine executes the following computation on a given input:

In:

Figure 4.3. Initial configuration: Initial configuration:

Initial configuration:

Figure 4.4. 


Figure 4.5. 


Figure 4.6. 


Figure 4.7. 


Figure 4.8. 


Figure 4.9. 


Figure 4.10. 


Figure 4.11. 


Figure 4.12. 


Figure 4.13. 


Figure 4.14. 


Figure 4.15. 


Figure 4.16. 


One may recognize, that the description of a computation in the above way is rather uncomfortable, but expressive. Describing the configurations in the form of their definition is much more efficient.

Figure 4.17. The computation of the Turing machine on the input word The computation of the Turing machine on the input word

The computation of the Turing machine on the input word

Example: Parity check

One possible solution for the task is the following Turing machine:

where ,

,

and

:

Figure 4.18. Parity check

Parity check

Here is an accepting, while is a rejecting state, i.e. and . Furthermore, is the initial state and in the same time it has the notion, that the processed part contains even number of 's. The state has the notion, that the processed part contains odd number of 's and the states and are for moving the read-write head and remembering to the parity.

The Turing machine executes the following computation on a given input:

In:

Figure 4.19. Initial configuration: Initial configuration:

Initial configuration:

Figure 4.20. 


Figure 4.21. 


Figure 4.22. 


Figure 4.23. 


Figure 4.24. 


Figure 4.25. 


Figure 4.26. 


Figure 4.27. 


Figure 4.28. 


Figure 4.29. 


Figure 4.30. 


Figure 4.31. 


Figure 4.32. 


Figure 4.33. 


Figure 4.34. 


The description of the computation by the configurations in the form of their definition:

Figure 4.35. The computation of the Turing machine on the input word The computation of the Turing machine on the input word

The computation of the Turing machine on the input word

4.3.2. Graph representation:

4.3.3. Representing Turing machines by enumeration:

The transition function can be given by the enumeration of its values on its possible arguments.

The transition function of Turing machine for parity bit generation:

The transition function of Turing machine for parity check:

4.3.4. Examples

1. Turing machine for mirroring the input word: .

2. Turing machine for mirroring the input word:: .

3. Turing machine which increase the input word - regarded as a binary number:, where .

4.3.5. Problems

1. Give the description of a Turing machine, which writes the word to its tape!

2. Give the description of a Turing machine, which writes the word to its tape!

3. Give the description of a Turing machine, which inverts its input word, i.e. exchanges every to a and every to a !

4. Give the description of a Turing machine, which swaps the symbols pairwise of the input word!

e.g..

5. Give the description of a Turing machine, for deciding which symbols are more frequent in the input word! If there are more 's, then it terminates in the state , if there are more 's, then it terminates in the state and if the are equal then it terminates in the state .