Turing Machines and Finite State Machines

We already know that a Turing machine is more powerful than a finite state machine, however, this advantage is often over-played. A Turing machine is only more powerful because of its unbounded memory. Any algorithm that a Turing machine actually implements has a bounded tape if the machine stops. Obviously, if the machine stops it can only have executed a finite number of steps and so the tape has a bounded length. Thus any computation that a bounded Turing machine can complete can be performed by a finite state machine. The subtle point is that the finite state machine is different in each case. There is no single finite state machine that can do the work of any bounded Turing machine that you care to select but once you have selected such a Turing machine it can be converted into a finite state machine.

As explained in the previous chapter if a Turing machine uses a tape of length n, a symbol set of size s and x states (in the finite state machine) can be simulated by a finite state machine with a= sⁿx states. Proving this is very simple.

The tape can be considered as a string of length n and each cell can have one of the s symbols. Thus, the total number of possible strings is sⁿ. For example, if we have a tape of length 2 and a symbol set consisting of 0,1 then we have the following possible tapes [0|0] [0|1] [1|0] [1|1] and you can see that this is 2², i.e. 4. For another example, a tape of length 3 on two symbols has the following states:

[0|0|0] [0|0|1] [0|1|0] [0|1|1]

[1|0|0] [1|0|1] [1|1|0] [1|1|1]

i.e. 2³=8 states.

For each state of the tape, the Turing machine’s finite state machine controller can be in any of x states, making a total of sⁿx states. This means you can construct a finite state machine using sⁿx states arranged so that the transition from one state to another copies the changes in the Turing machine’s internal state and the state of its tape. Thus the finite state machine is exactly equivalent to the Turing machine.

What you cannot do is increase the number of states in the finite state machine to mimic any addition to the Turing machine’s tape - but as the tape is bounded we don't have to.

It is sometimes argued that modern computers have such large storage capacities that they are effectively unbounded. That is a big computer is like a Turing machine. This isn’t correct as the transition from finite state machine to Turing machine isn’t gradual – it is an all or nothing.

The halting problem for a Turing machine is logically not decidable. The halting problem for a finite state machine or a bounded Turing machine is always decidable, in theory. It may take a while in practice, but there is a distinct difference between the inaccessibility of the halting problem for a Turing machine and the practical difficulties encountered in the finite state machine case.

What it is reasonable to argue is that for any bounded machine a finite state machine can do the same job. So the language and grammar hierarchy discussed in the last section vanishes when everything has to be finite. A finite state machine can recognize a type 0, 1 or 2 language as long as the length of the string is limited.

Turing Thinking

One of the interesting things about Turing machines versus finite state machines is the way we write practical programs or, more abstractly, the way we formulate algorithms. We nearly always formulate algorithms as if we were working with a Turing machine.

For example, consider the simple problem of matching parentheses. This is not a task a finite state machine can perform because the grammar that generates the “language” is context-free:

1. <S> →  (S)

2. <S> → <S><S>

3. <S> → #

where S is the current state of the string.

You can prove that this is the grammar of balanced parentheses or you can just try a few examples and see that this is so.

For example, starting with S="" i.e. the null string, rule 1 gives:

()

Applying rule 2 gives:

()()

Applying rule 1 gives:

(()())

and finally rule 3 terminates the string.

Let’s create an algorithm that checks to make sure that a string of parentheses is balanced. The most obvious one is to use a stack in which for each symbol:

   if symbol is ) 
     if the stack is empty then stop
     else  pop the stack  
   else push ( on stack

When the last symbol has been processed, the stack is empty if the parentheses are balanced. If the stack isn't empty then the parentheses are unbalanced. If there is an attempt to pop an empty stack while still processing symbols the parentheses are unbalanced.

If you try it you should be convinced that this works. Take (()())(), then the stack operations are:

string		operation	stack
(()())()  	push (		(
()())()  	push (    	((
)())() 	        pop   		(
())()  	        push (  	((
))()  		pop 		(
)()  		pop 		empty
()  		push ( 	(
) 		pop		empty balanced

as the final stack is empty, the string is balanced.

Now try (()()))(:

string		operation	stack
(()()))(  	push (		(
()()))(   	push (    	((
)()))( 	pop   		(
()))(   	push ( 	((
)))( 		pop		(
))( 		pop 		empty
)( 		pop 		empty unbalanced

as an attempt to pop an empty stack has occurred the parentheses are unbalanced.