TM as Transducers | Theory of Computation - Computer Science Engineering (CSE) PDF Download

• Part III. TM as Transducers

TM as Transducers
In all the above TMs, TM either accepts or rejects a string. That is, TM acts as a language acceptor.
- A TM can function as a transducer. That is, a string is given as input to TM, it produces some output. We can view a Turing machine as a transducer.

Input to the computation is a set of symbols on the tape.
At the end of computation, whatever remains on the tape is the output.

- A TM can be viewed as a transducer for the implementation of function f defined as,            
- A function, f is said to be computable or Turing computable, if there exists a TM M =     (Q,∑, Γ, δ, q₀, #, q_f ) such that , where w is in the domain of f. We can see that all common mathematical functions are turing computable.

This means, basic operations such as addition, subtraction, multiplication, division can be performed on it. This means that a TM is an abstract model of our modern computer system.

Example 1:
Design a Turing machine that computes the following function, f(m, n) = m + n. A positive integer on a Turing tape can be represented by an equal number of 0s.
For example,
integer 5 is represented as 00000, and
integer 8 is represented as 00000000.
In the tape two integers are separated using the symbol, $.

Let us assume that m=3 and n=5.
Then the input tape of the Turing machine will be,

After addition, tape will contain the results of addition as shown below:

TM for addition works as follows:
- Head reads the 0s of the first number, m and reaches the separator symbol, $. Symbol, $ is replaced with 0 and head moves towards right.
- It continues to move towards right till the second number, n is passed over and # is reached.
- At #, it turns left and replaces rightmost 0 with #.
- Now the tape contains the sum of m and n, and TM halts.
- Conversion of the separator symbol, $ to 0, helps TM to make the single number on the tape. The conversion of symbol, 0 to # removes the additional 0 that was generated from the conversion of $ to 0.

Transition table for the TM is shown below:

Above table is describes as follows:
1. Initially, TM is in state q₀. Head reads the first symbol, 0 and moves towards right without changing the state.
2. Head continues to move towards right till the separator symbol, $ is reached. It replaces $ with 0, changes state to q₁, and continues to move towards right.
3. Head continues to move towards right and passes over the second number to reach #.
4. On reaching the #, head changes state to q₂ and turns left.
5. In state q₂, it replaces symbol 0 with #, and changes state to qf .
6. In the final state, TM halts to indicate the completion of the process.

Addition of 3 and 5 is shown below:



Example 2:
Design a Turing machine that can multiply two numbers.
f(m, n) = m x n.

Let m=2, n=4
Tape contains two integers, both containing a termination symbol $, at the end as shown below:

After the multiplication operation, tape contains the result as shown below:

TM for multiplication works as follows:
- Leftmost 0 is replaced with symbol x and head moves towards right.
- Head moves towards right till the remaining 0s are passed over and the separator symbol $ is reached. It crosses $ and reaches the leftmost 0 of the number n. It replaces this 0 with y and moves towards right.
- Head moves towards right and reaches and crosses the second separator symbol, $.
- After crossing $, it replaces # with 0.
- Now head turns towards left and replaces second leftmost 0 of n to y.
- Head then turns right and keeps moving towards right till a # is reached. It replaces # with 0 and turns towards left.
- This process is repeated till all the 0’s in the number n are converted to y and their copy is made after the second $. This completes one cycle of copying.

- After one cycle of copying, head turns left and converts all y’s to 0. It moves towards left and converts the second leftmost 0 of m to x and makes a copy of n after the second $.
- The cycle of copying n after the second $ is repeated m times and the number of such cycles is tracked with the help of the number of x symbols in the number m. With m cycles of copying n after the second $, tape contains mxn numbers of 0s, which is the product.

Transition table for the TM is shown below:


Example 3:
Design a TM that copies strings of 1’s.

For this problem, let the given string is 11 as shown below:

Note that we store a # before the string in the tape.
The output from TM should be as follows:

Following is the transition table for this TM:

Here the TM replaces every 1 by symbol x. Then TM replaces rightmost x by 1. It goes to the right end of the string and writes a 1 there. Thus TM has added a 1 for the rightmost 1 in the input string. This process is repeated.
TM reaches q₁ after replacing all 1’s by x’s and reading the # symbol at the end of the input string. After replacing x by 1, TM reaches q₂. TM reaches _q3 at the end of the process and halts.
If the string is 11, we get 1111 at the end of computation.
If the string is 111, we get 111111 at the end of computation.

Consider the processing of the string 111:

 

TM as a Computer
Thus a TM can perform the basic operations such as addition, multiplication, subtraction and division. That means it can act as a computer. TM is a simple mathematical model of a computer. TM can do everything a computer can do. If TM cannot solve certain problems, then these problems are beyond the theoretical limits of computation.

Exercises:
1. Design a Turing machine that computes m - n where m and n are positive integers and m>n.
2. Design a TM to divide m by 3 and to compute the quotient and the remainder.