A Turing machine is specified by a finite alphabet Σ, a finite set of states
K with a special element s (the starting state), and a transition function δ : K × Σ →
(K ∪ {halt, yes, no}) × Σ × {←,→, −}. It is assumed that Σ, K, {halt,yes,no}, and {←,→, −}
are disjoint sets, and that Σ contains two special elements ., t representing the start and end
of the tape, respectively. We require that for every q ∈ K, if δ(q, .) = (p, σ, d) then σ = . and
d 6=←. In other words, the machine never tries to overwrite the leftmost symbol on its tape nor