Q$5($a$)(17$ marks$)$

Write the transition table for the Turing machine. Organise the transitions by state or by the order they're executed $($Section $27\mathrm{.}1\mathrm{.}3).$ 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, but you won't be awarded any marks for your tests. You don't have to remove your tests before submitting this TMA.

In palindrome$\_$tests, set the debug parameter to$$True$$if you want to see the configurations your Turing machine goes through. Make sure you$$set it back to$$False$$and run the cell again before submitting$$your TMA.

# State 'start', symbol read

$(\text{'}$start$\text{'},0)$: $($None$,$ RIGHT, 'check$\_$right'$),$ # Move to the right to start checking

$(\text{'}$start$\text{'},1)$: $($None$,$ RIGHT, 'check$\_$right'$),$

# State 'check$\_$right', symbol read

$(\text{'}$check$\_$right', $0)$: $($None$,$ RIGHT, 'check$\_$right'$),$ # Continue moving right

$(\text{'}$check$\_$right', $1)$: $($None$,$ RIGHT, 'check$\_$right'$),$

$($None$,$ None$)$: $($None$,$ LEFT, 'check$\_$left'$),$ # Encountered blank, start checking from the left

# State 'check$\_$left', symbol read

$(\text{'}$check$\_$left', $0)$: $($None$,$ LEFT, 'compare'$),$ # Start comparing from the left

$(\text{'}$check$\_$left', $1)$: $($None$,$ LEFT, 'compare'$),$

# State 'compare', symbol read

$(\text{'}$compare$\text{'},0)$: $(0,$ LEFT, 'compare'$),$ # Move left

$(\text{'}$compare$\text{'},1)$: $(1,$ LEFT, 'compare'$),$

$($None$,$ None$)$: $($None$,$ RIGHT, 'halt'$)$ # Reached the beginning, halt

$\%$run $-$i m$269\_$util # both files are in the downloaded TMA zip file

$\%$run $-$i m$269\_$tm

$$

palindrome $=\{$

$\}$

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]),$

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

$]$

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