Computers

Computers

The finite automata, as defined in Chapter 5, are only language-acceptors. When we gave them output capabilities, as with Mealy and Moore machines in Chapter 8, we called them transducers. The pushdown automata of Chapter 14 similarly do not produce output and are only language-acceptors. However, we recognized their potential as transducers for doing parsing in Chapter 18, by considering what is put into, left in, or popped from the STACK as output.

Turing Machines (TMs) present a completely different situation. They always have a natural output. When the processing of any given TM terminates, whatever is left on its TAPE can be considered to be the intended, meaningful output. Sometimes, the TAPE is only a scratch pad where the machine has performed some calculations needed to determine whether the input string should be accepted. In this case, what is left on the TAPE is meaningless. For example, one TM that accepts the language EVENPALINDROME works by cancelling a letter each from the front and the back of the input string until there is nothing left. When the machine reaches HALT, the TAPE is empty.

However, we may use TMs for a different purpose. We may start by loading the TAPE with some data that we want to process. Then we run the machine until it reaches the HALT state. At that time, the contents of the TAPE will have been converted into the desired output, which we can interpret as the result of a calculation, the answer to a question, a manipulated file - whatever.

So far, we have been considering only TMs that receive input from the language defined by (a + b)*. To be a useful calculator for mathematics, we must encode sets of numbers as words in this language. We begin with the encoding of the natural numbers as strings of a's alone:

This is called unary encoding because it uses one digit (as opposed to binary, which uses two digits, or decimal with ten).

Every word in (a + b)* can then be interpreted as a sequence of numbers (strings of a's) separated internally by b's. For example, the decoding of (abaa) is 1, 2 and bbabbaa = (no a's)b(no a's)b(one a)b(no a's)b(two a's) represents 0, 0, 1, 0, 2.

Notice that we are assuming that there is a group of a's at the beginning of the string and at the end even though these may be groups of no a's. For example, abaabb = (one a)b(two a's)b(no a's)b(no a's) which represents 1, 2, 0, 0.

When we interpret strings of a's and b's in this way, a TM that starts with an input string of a's and b's on its TAPE and leaves an output string of a's and b's on its TAPE can be considered to take in a sequence of specific input numbers and, after performing certain calculations, leaves as a final result another sequence of numbers - output numbers.

Example: The ADDER TM

Consider the following TM called ADDER:

(a,a,R) (a,a,R)
START 9 (b,.,R) > c)(.,L) > 8 (a,.,R) HALT

In START, we skip over some initial clump of a's, leaving them unchanged. When we read a b, we change it to an a and move to state 1. In state 1, a second b would make us crash. We skip over a second clump of a's until we run out of input string and find a . At this point, we go to state 2, but we move the TAPE HEAD left. We have now backed up into the a's. There must be at least one a here because we changed a b into an a to get to state 1. Therefore, when we first arrive at state 2, we erase an a and move the TAPE HEAD right to HALT and terminate execution.

For an input string to be accepted (lead to HALT), it has to be of the form a *ba*. If we start with the input string a^nba^m, we end up with a^(n + m) on the TAPE.

When we decode strings as sequences of numbers as above, we identify a^nha^m with the two numbers n and m. The output of the TM is decoded as (n + m).

Under this interpretation, ADDER takes two numbers as input and leaves their sum on the TAPE as output. This is our most primitive example of a TM intentionally working as a calculator.

If we used an input string not in the form a *ba*, the machine would crash. This is analogous to our computer programs crashing if the input data are not in the correct format.

Example: Binary Addition TM

Let us build a TM that adds two numbers presented in binary notation and leaves the answer on the TAPE in binary notation. We shall construct this TM out of two parts. First, we consider the TM T1 shown below:

(0,0,R)
(1,1,R)
(1,0,L)
(START)
($,$,R)
HALT

This TM presumes that the input is of the form $(0 + 1)*$. It finds the last bit of the binary number and reverses it; that is, 0 becomes 1, 1 becomes 0. If the last bit was a 1, it backs up to the left and changes the whole clump of 1's to 0's, and the first 0 to the left of these 1's turns into a 1. All in all, this TM adds 1 to the binary number after the $. If the input was of the form $1*, the machine finds no 0 and crashes. In general, T1 increments by 1.

Now let us consider the TM T2. This machine will accept a nonzero number in binary and subtract 1 from it. The input is presumed to be of the form $(0 + 1)*$ but not $0*$. The subtraction will be done in a three-step process:

1. Reverse the 0's and 1's between the $'s. This is called taking the 1's complement.
2. Use T1 to add 1 to the number now between the $'s. Notice that if the original number was not 0, the 1's complement is not a forbidden input to T1 (i.e., not all 1's).
3. Reverse the 0's and 1's again.

The total result is that what was x will become x - 1.

The mathematical justification for this is that the 1's complement of x (if it is n bits long) is the binary representation of the number 2^n - 1. Because when x is added to it, it becomes n solid 1's = 2^n - 1.

For example, $1 0 1 0$ = binary for 10 becomes $0 1 0 1$ = binary for 5 becomes $0 1 1 0$ = binary for 6 becomes $1 0 0 1$ = binary for 9.

Defining a Computer

DEFINITION: If a TM has the property that for every word it accepts, at the time it halts, it leaves one solid string of a's and b's on its TAPE starting in cell 1, we call it a computer. The input string we call the initial input.

This definition allows us to consider TMs as computers. They can perform calculations, process data, and produce output based on specific inputs. The examples above illustrate how TMs can be designed to perform specific tasks, such as addition and subtraction of numbers encoded in various formats.

In summary, TMs are not just theoretical constructs. They can be seen as the foundation of computation, capable of simulating any algorithmic process. This makes them powerful tools for understanding the limits of computation and the nature of algorithms.

Check your understanding

• What is the difference between finite automata and Turing Machines?
• Explain unary encoding and provide an example.
• Describe the process of how the ADDER TM works.
• What are the steps involved in the binary addition using TMs?