Turing machine that accepts language in n+1

Question

Let $\Sigma$ be a finite alphabet and $L \subseteq \Sigma^n$. I want to show that there exists a Turing machine, which accepts $L$ and has a calculating time of n+1.

Answer 1

You can make a Turing machine for this which operates as follows. It has $n+2$ states, where $n$ is the same as the n in $\Sigma^n$. It starts in state $q_1$ on the first character of the word and goes right on the tape and goes to state $q_2$ if the first character is not blank. It keeps doing this until it is on state $q_n$. Again it goes right if the character is not blank, and now it goes to state $q_{n+1}$, and goes right on the tape. State $q_{n+1}$ goes to state $q_{n+2}$ if the tape IS blank on this character, and $q_{n+2}$ is an accepting state. We made n+1 moves to get from $q_1$ to $q_{n+2}$.

Note that the machine gets stuck (with an undefined transition function) if the word is too long or too short. In this case it may not take time $n+1$. If you want it to take time $n+1$ whether accepting or rejecting, then you can view the states described above as on a line from $q_1 \implies q_2 \implies ... \implies q_{n+2}$. Simply put another line of states underneath, where $r_1 \implies r_2 \implies ... \implies r_{n+2}$ and $r_{n+2}$ is not an accepting state. Then change the transition function so that if the machine would get stuck on the transition from $q_k \implies q_{k+1}$, instead have it go to $r_{k+1}$ and just follow the r sequence till the end regardless of what is on the tape. Then the machine will take time $n+1$ on all inputs, accepting or rejecting.

Answer 2

Here is a TM for $\Sigma = \{ a,b \}$ and $n=3$ ($0$ is blank):