RIGHT $=1$

LEFT $=-1$

STAY $=0$

MAX$\_$STEPS $=100$

def run$\_$TM$($tm:dict, tape:list, debug:bool$)->$ list:

$"""$Run Turing machine $`$tm$`$ on $`$tape$`$ and return the resulting output.

The machine runs from state 'start' until it halts or has done MAX$\_$STEPS.

The output is the tape's content from the head onwards.

If debug is True, print each configuration.

Preconditions:

$-$ tm maps $($state$,$ symbol$)$ pairs to $($symbol$,$ movement, state$)$ triples

$-$ states are represented by strings

$-$ symbols are of any hashable type

$-$ movement is one of RIGHT, LEFT, STAY

$-$ tape is a list of symbols

$-$ the blank symbol is represented as None

$"""$

head $=0$

if tape $==[]$:

tape $=[$None$]$

symbol $=$ tape$[$head$]$

state $=$ 'start'

step $=0$

if debug:

print$($step$,$ state, tape$[$:head$],$ symbol, tape$[$head$+1$:$])$

while step $<$ MAX$\_$STEPS and $($state$,$ symbol$)$ in tm:

actions $=$ tm$[($state$,$ symbol$)]$

tape$[$head$]=$ actions$[0]$ # write symbol $($may be the same$)$

head $=$ head $+$ actions$[1]$ # move left, right or stay

state $=$ actions$[2]$ # next state $($may be the same$)$

step $=$ step $+1$

if head $<0$:

print$(\text{'}$Moved left past the start of the tape'$)$

head $=0$

step $=$ MAX$\_$STEPS # force loop to finish

elif head $==$ len$($tape$)$:

tape.append$($None$)$ # extend tape when needed

symbol $=$ tape$[$head$]$

if debug:

print$($step$,$ state, tape$[$:head$],$ symbol, tape$[$head$+1$:$])$

output $=$ tape$[$head:$]$

while output $!=[]$ and output$[-1]==$ None:

output.pop$()$

return output

$\%$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', palindrome, $[1,0,0,1],$ False, $[1]),$

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

$]$

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

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.