We have discussed earlier that the Turing machine is not just a language definition tool. The original reason for introducing the Turing machine was to simulate mathematical algorithms which can calculate complicated functions. Later, it has been recognized that all algorithmically computable functions can be calculated by the Turing machine, as well. The statement which claims that a function is algorithmically computable if and only if it can be computed by the Turing machine is called Church's thesis. Church's thesis is not a theorem, it cannot be proven, because "algorithmically computable" is not a well defined expression in the thesis. In spite of the fact that Church's thesis is not a proven theorem, the thesis is accepted among scientists. The most important consequence of the thesis is that even the latest, and the strongest computer with a highly improved computer program can only compute the same things as a very simple Turing machine. Therefore we can use the Turing machine to show if something can be computed or not; and this is why the Turing machine plays a fundamental role in the algorithms and computational theory. Although this book focuses on formal languages, we cannot conclude this topic without illustrating the basics of the application of the Turing machine as a computing device.

When we use the Turing machine to compute/calculate a function, we use it the same way as before. At the beginning, the input word is on the tape, and when the Turing machine reaches a final configuration (u,qf,av), the result of the computation/calculation is the word uav, which is the significant part of the tape. In the Example 58. we show a Turing machine, which computes the two's complement of the input binary number.

**Example 58.** *TM* = ({*q*_{0},
*q*_{1}, *q _{f}*}, {0,1}, {0,1,

δ(q_{0},1) = {(q_{0},0,Right)}, δ(q_{0},0) = {(q_{0},1,Right)}, δ(q_{0},#) = {(q_{1},#,Left}, δ(q_{1},1) = {(q_{1},0,Left)}, δ(q_{1},0) = {(q,1,_{f}Stay)}.

*The Figure 6.1. shows the graphical notation of this Turing machine.*

**Exercise 82.** *Create a Turing machine, which changes the first five 0 to 1 in an input binary number.*

**Exercise 83.** *Create a Turing machine, which adds five to the input binary number.*

**Exercise 84.** *Create a Turing machine, which changes the order of two input binary numbers, separated by space.*

Each equivalent definition of the Turing machine which was given at the end of the previous section can work here, so we can use the deterministic Turing machine, the multitape Turing machine, and the single tape Turing machine, which is infinite only in one direction, or we can extend the Turing machine with rejecting states, our choice will not influence the calculating power.

As we have already demonstrated, there are languages which are not recursively enumerable. This means that these languages cannot be generated
by a generative grammar, and cannot be accepted by Turing machines. Also, there are functions, which cannot be computed by Turing machines.
There is a well known example: the halting problem. There is a computer program given with an input, decide whether the program stops running after a while,
or goes into an infinite loop. The same problem with Turing machine appears to be the following: given a description of a Turing machine and the input word,
decide whether the Turing machine stops running or keeps on running forever. Let us denote the description of a Turing machine with
*d _{TM}* and the input word with

constant time, when the calculating time is fixed, does not depend on the length of the input, denoted by

*O*(1),logarithmic time, when the calculating time is not more than a logarithmic function of the length of the input word, denoted by

*O*(*log n*),linear time, when the calculating time is not more than a linear function of the length of the input word, denoted by

*O*(*n*),polynomial time, when the calculating time is not more than a polynomial function of the length of the input word, denoted by

*O*(*n*),^{k}exponential time, when the calculating time is not more than an exponential function of the length of the input word, denoted by

*O*(2).^{nk}

Evidently, we can have the same complexity classes for the space used by a Turing machine, and most of our computer programs are
deterministic, so these complexity classes can be similarly defined for deterministic Turing machines, as well.
We know that the nondeterministic and the deterministic Turing machines have the same computational power, but we do not know if the problems which can
be solved with nondeterministic Turing machines in polynomial time, and the problems which can be solved with deterministic Turing machines
in polynomial time are the same or not. This is a major problem in algorithm theory, and it is called
**P** = **NP?** problem.

Our last section is about the linear bounded automaton, which is a Turing machine with linear space complexity, and has a special role in the study of context-sensitive languages.