This question can be answered after studying Section $27\mathrm{.}2.$ 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$)(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.

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

from typing import Callable

def test$($function: Callable, test$\_$table: list$)->$ None:

$"""$Test the function with the test$\_$table. Report failed tests.

Preconditions: each element of test$\_$table is a list or tuple with

$-$ a string $($the test case name$)$

$-$ one or more values $($the inputs to the function$)$

$-$ the expected output value

$"""$

for test$\_$case in test$\_$table:

name $=$ test$\_$case$[0]$

inputs $=$ test$\_$case$[1$:$-1]$

expected $=$ test$\_$case$[-1]$

actual $=$ function$(*$inputs$)$

if actual $!=$ expected:

print$($name$,$ 'FAILED:$\text{'},$ actual, 'instead of$\text{'},$ expected$)$

print$(\text{'}$Tests finished.$\text{'})$

Complete the code below:

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

$]$

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