Turing Machine: Write all the transition rules for a Turing Machine that solves the palindrome problem. A palindrome is a string that is the same if you reverse it. For example, 9235329 is an odd length palindrome and 923329 is an even length one. Your TM given a string of characters from [0,1, ..., 9} will answer with either yes or no. The input wil have a blank b at the beginning and end, i.e. b9235329b. The head will be at the first character, which is a c. (a) Writing down TM descriptions is hard. Instead, start by writing pseudo code using variables and loops. The only allowed actions are to read and write to the tape where the head is and to move the head to the left and right. I am also a big believer in loop invariants. This is a clear picture of what the tape looks like at the beginning of each iteration. Hint: The loop invariant should be that either the TM has already halted because it has already discovered that the string is not to a palindrome or for some i 2 0, the first i characters and the last i characters have been correctly matched and blanked out. What remains is to check that the renaining string is a palindrome. For example, with i = 2 the tape would contain bbb353bbb. The head will be at the first remaining character, which is stored in c. (b) Translate this code into Turing Machine Transitions s(q(lines!'jz?,-(q(nezt state), char to write, direction move head . Recall the states are named with the line number and the value of each variable (c) How many states does your TM have? Turing Machine: Write all the transition rules for a Turing Machine that solves the palindrome problem. A palindrome is a string that is the same if you reverse it. For example, 9235329 is an odd length palindrome and 923329 is an even length one. Your TM given a string of characters from [0,1, ..., 9} will answer with either yes or no. The input wil have a blank b at the beginning and end, i.e. b9235329b. The head will be at the first character, which is a c. (a) Writing down TM descriptions is hard. Instead, start by writing pseudo code using variables and loops. The only allowed actions are to read and write to the tape where the head is and to move the head to the left and right. I am also a big believer in loop invariants. This is a clear picture of what the tape looks like at the beginning of each iteration. Hint: The loop invariant should be that either the TM has already halted because it has already discovered that the string is not to a palindrome or for some i 2 0, the first i characters and the last i characters have been correctly matched and blanked out. What remains is to check that the renaining string is a palindrome. For example, with i = 2 the tape would contain bbb353bbb. The head will be at the first remaining character, which is stored in c. (b) Translate this code into Turing Machine Transitions s(q(lines!'jz?,-(q(nezt state), char to write, direction move head . Recall the states are named with the line number and the value of each variable (c) How many states does your TM have