A linear bounded automaton $($LBA$)$ is exactly like a one$-$tape Turing

machine, except that the input string xin${}^{**}$ is enclosed in left and

right endmarkers $t$ and $t$ which may not be overwritten, and the

machine is constrained never to move left of the $|--$ nor right of the $-.$

It may read and write all it wants between the endmarkers.

$($a$)$ Give a rigorous formal definition of deterministic linearly bounded

automata, including a definition of configurations and accep$-$

tance$.$ Your definition should begin as follows: "A deterministic

linearly bounded automaton $($LBA$)$ is a $9-$tuple

$M=(Q,,,|--,,,s,t,r),$

where $Q$ is a finite set of states,.."

$($b$)$ Let $M$ be a linear bounded automaton with state setQ of size $k$

and tape alphabet $$ of size $m.$ How many possible configurations

are there on input $x,|x|=n?$

$($c$)$ Argue that the halting problem for deterministic linear bounded

automata is decidable. $($Hint: You need to be able to detect after

a finite time if the machine is in an infinite loop. Presumably the

result of part $($b$)$ would be useful here.$)$

$($d$)$ Prove by diagonalization that there exists a recursive set that is

not accepted by any LBA.