Past exam of the computer science course of the University of Oxford / 2015 / Computational complexity / 1 / a / Solution

Exactly the regular languages. A read-only-from-left Turing acceptor has only its current control state as usable memory: it never changes a tape symbol, and its head never returns to an earlier cell. This is the behaviour of a deterministic finite automaton while it reads the input.

To make the correspondence precise, retain the control states and the transitions on the input alphabet. Replace accepting and rejecting halts by absorbing states, so that halting before the end of a word over an alphabet has the same effect on every continuation. For each remaining state $q$, follow the transitions on blank symbols and mark $q$ accepting in the deterministic finite automaton exactly when this blank-only continuation eventually accepts. This marking is a finite calculation: either a halting state is reached or a state repeats, after which the blank-only run loops. The resulting deterministic finite automaton accepts exactly the same formal language as the read-only-from-left Turing acceptor. If the latter is a decider, the blank-only run from every reachable end-of-input state halts.

Conversely, simulate any deterministic finite automaton by a read-only-from-left Turing acceptor, using its state transitions while reading the input. At the first blank symbol, halt and accept or reject according to the current deterministic finite automaton state. This machine halts on every input and decides the required regular language.