It assesses the learning outcomes:

Understand the Turing Machine model of computation.

Explain how an algorithm or data structure works, in order to communicate with relevant stakeholders.

We want a Turing machine that checks if a string is a palindrome, i$.$e$.$ is the same as when read backwards. The input tape consists of zero or more zeros and ones, followed by blanks. The output is $1$ if the input is a palindrome, otherwise $0.$ You may modify the input symbols.

For example, if the input is $[1,0,1]$ then the

output is $[1],$ whereas input $[1,0]$ leads to output $[0].$

Q$5($a$)$

Write the transition table for the Turing machine. Organise the transitions by state or by the order they're executed. Use descriptive state names.

Suggestions: Write and test a machine that handles even$-$length inputs and then handles odd$-$length inputs. 'Remove' $($i$.$e$.$ blank out$)$ input symbols as you process them.

You should add tests to check your Turing machine.

In palindrome$\_$tests, set the debug parameter to$$True$$if you want to see the configurations your Turing machine goes through.

run $-$i m$269\_$util

$\%$run $-$i m$269\_$tm #In the picture

palindrome $=\{$

# write the transitions here in the form

# $($state$,$ symbol$)$: $($new$\_$symbol, LEFT or RIGHT or STAY, new$\_$state$),$

$\}$

palindrome$\_$tests $=[$

# case, TM$,$ input tape, debug, output tape

$(\text{'}$palindrome$\text{'},$ palindrome, $[1,0,1],$ False, $[1]),$

$(\text{'}$not palindrome', palindrome, $[1,0],$ False, $[0]),$

$]$

test$($run$\_$TM$,$ palindrome$\_$tests$)$

Q$5($b$)$

Explain how your Turing machine works, describing the main transitions and the purpose of each state. Your answer shouldn't be a direct translation of the transition table to English.

Include diagrams, if you wish, drawn by hand or with a computer.