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₀, q₁, q_f}, {0,1}, {0,1,#}, q₀, #, δ, {q_f})

   δ(q0,1) = {(q0,0,Right)},
   δ(q0,0) = {(q0,1,Right)},
   δ(q0,#) = {(q1,#,Left},
   δ(q1,1) = {(q1,0,Left)},
   δ(q1,0) = {(qf,1,Stay)}.

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

6.1. ábra - The graphical notation for the Example 58.

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 w. The problem is to create a Turing machine which decides about each input word d_TM#w whether or not the Turing machine TM goes into an infinite loop with the input word w. It has been shown that this problem cannot be decided by a Turing machine, so there is no universal algorithm to decide if a given computer program goes into an infinite loop or not. The equivalent problem is to create a Turing machine which accepts an input word d_TM#w, if the Turing machine TM stops with the input word w. As one can see, computing/calculating a function or accepting a language is not so distant from each other. We also have to point out that the halting problem cannot be solved, because we suppose that the Turing machine has an infinite tape. The problem can be solved in a computer with a finite memory, however, the algorithm is not efficient in practice. We have already shown that there are functions which cannot be algorithmically computed, consequently there are problems which cannot be solved. However, there are many problems, which can be solved, and we would like to know the complexity of the algorithms computing the solutions. For this reason, scientists have introduced the time complexity of the algorithms. The time complexity of an algorithm is not a constant number. For a longer input the Turing machine needs longer time to compute, so the time complexity of an algorithm is a function for each algorithm, and the parameter of the function is the length of the input word w. This length is commonly denoted by n, so n = ∣w∣, and the time complexity of the Turing machine TM is denoted by T(n). We can investigate the space complexity of an algorithm as well. Let us denote by S(n) the function which shows how many cells we use on the tape of the Turing machine TM for an input word of length n. Of course, the time complexity and the space complexity are not independent from each other. If the time is limited, we have a limitation on the number of steps, so we can go to a limited distance from the initial position on the tape, which means that the space is also limited. The most important time complexity classes are the followings:

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.