When describing a Turing machine M $=($Q$,\backslash$Sigma $,\backslash$Gamma $,$ q$0,$ q$1,$ q$2,\backslash$delta $),$ we will use the following vocabulary

$($remember that every rst$-$order language contains the equality symbol $=)$:

$$ the constant symbol $0(`$zero$\text{'})$;

$$ the unary function symbol S $(`$successor$\text{'}$ on natural numbers$)$;

$$ for every k in $\{0,...,|$Q$|\},$ a unary predicate letter Qk$($x$)(`$at step x$,$ the machine M is in state

qk$\text{'})$;

$$ a binary predicate letter C$($x$,$ y$)(`$at step x$,$ the machine M scans cell y$\text{'})$;

$$ for every k in $\{0,...,|\backslash$Gamma $|\},$ a binary predicate letter Sk$($x$,$ y$)(`$at step x$,$ cell y contains symbol sk$\text{'}).$

When describing computations of Turing machines, we will be making the following assumptions:

$$ the tape is one$-$way innite $($hence the cells can be numbered $0,1,2,$ etc.$)$;

$$ machines can move left and right $($no other types of head movement are allowed$)$;

$$ the left$-$most cell, i$.$e$.,$ cell $0,$ always contains an end$-$of$-$tape marker, which is a special tape symbol;

$$ states are always called q$0,$ q$1,$ q$2,$ etc.;

$$ the starting state is q$0,$ the accepting state is q$1,$ and the rejecting state is q$2$;

$$ the tape symbols are always called s$0,$ s$1,$ s$2,$ etc.

$$ s$0$ is the blank;

$$ s$1$ is the end$-$of$-$tape marker.

Write formulas saying the following, in the vocabulary listed above:

$1.$ A formula describing the initial conguration of M on the empty word $.$