What is the formal definition of a semi-infinite tape Turing machine? How do we define its transition function, to avoid going left when we are at the boundary?
2 Answers
$\begingroup$
$\endgroup$
I think the definition must be attached with a definition of the language that it accepts. I come up with a definition similar to that of LBA (linear bounded automata):
A semi-infinite tape Turing machine is a Turing machine $M=(Q,\Sigma,\Gamma,\delta,q_0,\square,F)$, where a special symbol $[$ is contained in $\Sigma$ and
$$ \forall q\in Q,\delta(q,[)\subseteq Q\times\{[\}\times\{R\}. $$
A string $w$ is said to be accepted by $M$ if there exist $q_f\in F$ and $x_1,x_2\in \Gamma^*$ such that
$$ q_0[w\vdash^*[x_1q_fx_2. $$
$\begingroup$
$\endgroup$
There are several ways how the definition can go. Besides having a special symbol marking the boundary of the tape as in GKxx’s answer, some possibilities are:
Define one step of the computation of the machine such that if the machine is in a configuration with the head at the beginning of the tape, and the transition function tells it to go left, it actually stays in place. (This definition is used in Sipser’s Introduction to the theory of computation.)
Leave the responsibility to the programmer: if the machine is in a configuration with the head at the beginning of the tape, and the transition function tells it to go left, the machine immediately rejects. Or alternatively, halts in a special “error” state.
