SKEDSOFT

Turing Machines as Transducers: To use a Turing machine as a transducer, treat the entire nonblank portion of the initial tape as input, and treat the entire nonblank portion of the tape when the machine halts as output.

A Turing machine defines a function y = f (x) for strings x, yÎS* if

A function index is “Turing computable” if there exists a Turing machine that can perform the above task.

Example 1: Design a Turing machine that accepts the set of all even palindromes over {0,1}.

Solution: There are various steps involved in processing even length palindromes. The TM scans the first symbol of input tape (0 or 1), erases it and changes state (q1,or q2). TM scans the remaining part without changing the tape symbol until itencounters b. The read/write head moves to the left. If the rightmost symbol tallies with the leftmost symbol (which can be erased but remembered), the rightmost symbol is erased. Otherwise TM halts. The read/write head moves to the left until b is encountered. The above steps are repeated after changing the states suitably. The transition table is as shown below.