3 votes 3 votes What is the smallest number of states can a TM have? Theory of Computation theory-of-computation turing-machine + – Shivam Chauhan asked Nov 20, 2017 Shivam Chauhan 1.6k views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments Ashwin Kulkarni commented Nov 20, 2017 reply Follow Share 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. 0 votes 0 votes Shivam Chauhan commented Nov 20, 2017 reply Follow Share @Manu+Thakur @Shubhanshu Please help. What do you think 1 state or 2 state. 0 votes 0 votes Shivam Chauhan commented Nov 20, 2017 reply Follow Share @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) 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes 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.) gmrishikumar answered Jan 30, 2019 gmrishikumar comment Share Follow See all 0 reply Please log in or register to add a comment.