Problem 2: TM Computing functions from strings to strings.

Create a program for TM M_ab that does the following: given a string w over alphabet {a,b}, in the first half of w, it replaces all the a's by 1's and b's by 2's. In the 2^nd half of w, it replaces all the a's by 3's and b's by 4's. If the string is odd, the middle character is replaced by 1.

This program will ACCEPT all strings of a's and b's, replace all a's and b's as described, and will always terminate with the head on the LEFTMOST tape cell.

Example: if the input string is "abbbabab", the output string is "12223434" with the head over '1'

Important: Do not use any of the same names for the states of M_ab as for the states of M₁₂₃₄

Hint: you may want to borrow some ideas from the palindrome program available with the simulator.

Note: this is an example of a machine which computes a function; in this case, it's a function from strings to strings.