Theory of Computing

List of Figures

3.1. Figure 1

3.2. Figure 2.

3.3. Figure 3

4.1. The model of Turing machine

4.2. Parity bit addition to the input word

4.3. Initial configuration:

4.4.

4.5.

4.6.

4.7.

4.8.

4.9.

4.10.

4.11.

4.12.

4.13.

4.14.

4.15.

4.16.

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

4.18. Parity check

4.19. Initial configuration:

4.20.

4.21.

4.22.

4.23.

4.24.

4.25.

4.26.

4.27.

4.28.

4.29.

4.30.

4.31.

4.32.

4.33.

4.34.

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

4.36. The composition of and

4.37. Conditional composition of , and

4.38. Iteration of

4.39. Multi tape Turing machine

4.40. Simulation of a two-tape Turing machine