Hello, I need help with this exercise please:

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.

############

Here is the code

from m$269\_$tm import run$\_$TM ##### This class is at the bottom

RIGHT $=1$

LEFT $=-1$

STAY $=0$

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

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

$]$

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

########################

THIS IS THE run$\_$TM class:

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