Turing Machines

Question

What is the smallest number of states can a TM have?

Comments

Turing machine can't accept epsilon. Hence all the comparisons are done by ignoring that case. and then only it will be more powerful than PDA.

---

@Manu+Thakur

@Shubhanshu

Please help. What do you think 1 state or 2 state.

---

@joshi_nitish

What about Turing Machine M = (Q,Σ,Γ,δ,$q_0$,B,F) accepting Language L=$\phi$ where

Q = {$q_0$}

Σ = {a}

Γ = {a,B}

$q_0$ = initial state

B = Blank

F = {}   no final state

δ ($q_0$ , a) = ($q_0$, $\epsilon$, R)

Answer 1

A TM needs to have at least two states - an accepting state and a rejecting state.

The accepting and rejecting states must be distinct because the machine cannot simultaneously accept and reject. Therefore, there must be at least two states.

With a single state, you can not accept anything.

A Turing Machine's transition looks like (X, Y , R/L). With single state you will specify at least one transition, now that transition will surely contain R/L, therefore Turing Machine will never stop it will either keep moving right or keep moving left or oscillate b/w left and right.

Refer: 

https://cs.stackexchange.com/questions/86538/why-does-a-turing-machine-need-at-least-two-states

http://cobweb.cs.uga.edu/~potter/theory/4_Turing_Machines1.pdf

https://en.wikipedia.org/wiki/Turing_machine

(Just stating the information as a clear answer for future readers.)