Turing Machine

Question

S1: Can a Turing machine ever write a blank symbol on its tape.
S2: Any Turing machine must have at least two states

which of above statements are true???

Comments

both are true.

S1: Can a Turing machine ever write a blank symbol on its tape. yes this is also possible
S2: Any Turing machine must have at least two states : i.e. accepts state or reject state.

---

reference: http://cseweb.ucsd.edu/~mihir/cse105/ss3.pdf

---

@Anu007 Please could you tell if I am understanding it in a right way ? I am thinking as Turing machine should have minimum two states, because if there is only one state, then if transition is not defined for some symbol in that state, then the strings containing that symbol will halt on that one state only and hence, it will be again be halted in final state, making it accepted.

Also, does it apply the same way for PDA also, where we have dead configuration ?

Answer 1

Both are true.

S1: Yes it is also possible
S2: Any Turing machine must have at least two states i.e. accept state or reject state.

 

Ref: https://cseweb.ucsd.edu/~mihir/cse105/ss3.pdf

Comments

How many states for L = a* over {a}? Is it not possible that initial state is final state and TM accepts everything.

---

@priyesh9875

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