We want a Turing machine that capitalises a string: the first letter of every word is changed to uppercase.

There can only be six different symbols on the tape: a$,$ A $,0,"($double quote$),$ space and None $($blank symbol$).$ The input tape consists of a double quote, followed by zero or more spaces, a$,$ A and $0,$ followed by a double quote. The rest of the tape is blank. Write the transition table for the Turing machine. Use descriptive state names.

The list constructor used in the test below was introduced in Section $4\mathrm{.}6\mathrm{.}2$: list$(\text{'}"$A$"\text{'})$ evaluates to $[\text{'}"\text{'},\text{'}$A$\text{'},\text{'}"\text{'}]$

When the Turing machine stops, every a at the start of the string or preceded by a space has been replaced with A$.$ The rest of the string must remain unchanged. For example, if the tape is initially

$[\text{'}"\text{'},\text{'}$a$\text{'},\text{'}$A$\text{'},\text{'}\text{'},\text{'}0\text{'},\text{'}$a$\text{'},\text{'}\text{'},\text{'}$a$\text{'},\text{'}$a$\text{'},\text{'}"\text{'}]$

then the final tape is

$[\text{'}"\text{'},\text{'}$A$\text{'},\text{'}$A$\text{'},\text{'}\text{'},\text{'}0\text{'},\text{'}$a$\text{'},\text{'}\text{'},\text{'}$A$\text{'},\text{'}$a$\text{'},\text{'}"\text{'}]$

The head begins and must end$\%$run $-$i m$269\_$util

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

capitalise $=\{$

# Write the transitions here in the form

# $($state$,$ symbol$)$: $($new$\_$symbol, LEFT or RIGHT or STAY, new$\_$state$),$

$(\text{'}$start$\text{'},\text{'}"\text{'})$: $(\text{'}"\text{'},$ RIGHT, $\text{'}\text{'})$

$\}$

capitalise$\_$tests $=[$

# case, TM$,$ input tape, debug, output tape

$(\text{'}$example$\text{'},$ capitalise, list$(\text{'}"$aA $0$a aa$"\text{'}),$ True, list$(\text{'}"$AA $0$a Aa$"\text{'})),$

$]$

test$($run$\_$TM$,$ capitalise$\_$tests$)$ on the first $($left$-$most$)$ double quote. Here is some incomplete code: $\%$run $-$i m$269\_$util

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

capitalise $=\{$

# Write the transitions here in the form

# $($state$,$ symbol$)$: $($new$\_$symbol, LEFT or RIGHT or STAY, new$\_$state$),$

$(\text{'}$start$\text{'},\text{'}"\text{'})$: $(\text{'}"\text{'},$ RIGHT, $\text{'}\text{'})$

$\}$

capitalise$\_$tests $=[$

# case, TM$,$ input tape, debug, output tape

$(\text{'}$example$\text{'},$ capitalise, list$(\text{'}"$aA $0$a aa$"\text{'}),$ True, list$(\text{'}"$AA $0$a Aa$"\text{'})),$

$]$

test$($run$\_$TM$,$ capitalise$\_$tests$).$