Theory of Computing

Tamás Herendi

2014.


Table of Contents

1. Preface
2. Formal languages
3. Order of growth rate
4. Turing machines
4.1. The definition of the Turing machine
4.2. Acceptor Turing machines
4.3. Representation of Turing machines
4.3.1. Look up table representation:
4.3.2. Graph representation:
4.3.3. Representing Turing machines by enumeration:
4.3.4. Examples
4.3.5. Problems
4.4. Church-Turing thesis
4.5. Composition of Turing machines
4.6. Multi tape Turing machines, simulation
5. Computability theory
5.1. Universal Turing machines and universal language
5.2. Diagonal language
5.3. Recursive languages
5.4. Halting problem
6. Nondeterministic Turing machines
6.1. Definition of nondeterministic Turing machines
6.2. Simulation of nondeterministic Turing machines
7. Complexity concepts
7.1. Time, space and program complexity
7.2. Complexity classes
7.3. Space-time theorems
8. The class NP
8.1. The witness theory
8.2. NP-completeness
Bibliography

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: 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 The computation of the Turing machine on the input word
4.18. Parity check
4.19. Initial configuration: 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 The computation of the Turing machine on the input word
4.36. The composition of The composition of and and The composition of and
4.37. Conditional composition of Conditional composition of , and, Conditional composition of , and and Conditional composition of , and
4.38. Iteration of Iteration of
4.39. Multi tape Turing machine
4.40. Simulation of a two-tape Turing machine

List of Examples

3.1. Example 1.
3.2. Example 2.
3.3. Example 3