$1.[3$ marks$]$ An orientable sequence of order n is a binary string S that contains each

binary string of length n as a substring at most once in either direction. Thus, if w$1$ wn is a substring of S$,$ then wn $$ w$1$ is not. For example for n $=4,00010111$ is an orientable sequence, but $110010011$ is not $($it contains $1100$ and $0011).$ Also, for n $=4$: $11001100$ is not an orientable sequence since $1100$ appears twice. Prove that the following language is decidable:

L $=\{($$,$ n$)|$ is an orientable sequence or order n$\}$

$2.[4$ marks$]$ A VC$-100$ is a Turing machine variant that has only $100$ tape squares to work with; the tape is not infinite. It is a type of linear$-$bounded automaton $($see text$).$ Consider a specific VC$-100$ with s states, i input alphabet symbols, and t symbols in the tape alphabet.

$($a$)$ How many distinct configurations are possible for this VC$-100?$

$($b$)$ Prove that AG $=\{$M$,$ w$|$ M is a VC$-100$ that accepts w$\}$ is decidable.

$3.[2$ marks$]$ Consider the undecidable Post Correspondence Problem $($PCP$).$ Find a match in the following instance of the PCP using at most $6$ dominoes:

$\{[$ abb$/$b$],[$ a$/$bb$],[$ bbbbb$/$bab$],[$ b$/$baa$],[$ ababab$/$aa$]\}.$

$4.[4$ marks$]$ Consider the following language that consists of TMs that halt on ALL inputs:

TT M $=\{$M $|$ M is a TM that halts on all inputs$\}$

Use a reduction from AT M to prove that TT M is undecidable.