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.$

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

You should add tests to check your Turing machine.

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

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 cases for even palindromes

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

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

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

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

# Test cases for odd palindromes

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

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

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

# Test cases for even non$-$palindromes

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

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

# Test cases for odd non$-$palindromes

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

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

$]$

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