MadeEasy Subject Test: Theory of Computation - Turing Machine

Question

Consider the following statements:
S1: Turing machine can write the blank symbol on its tape.
S2: Tape alphabet Γ can never be same as input alphabet Σ.
S3: Turing machine’s head can ever be in the same location in two successive steps.
S4: Turing machine contain atleast two states.
How many of the above statements are correct?

Please give explanation too

Comments

4?..

---

Someone, explain this question, please.

---

only S1 is true...

---

I also think S1 is only true, but I don't have any solid proof for statement s3.

I think for S4 language (a+b)* is acting as counter case, where we required only one state to accept the string.

Ryt???

---

but in every transition either left or right move is taken...there is nothing like stay in same place...

---

Oh yeah, its transition function also includes Left or right direction and nothing else as the third attribute.

thanks.

---

Turing Machine with stay option exists

---

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

Answer 1

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

Answer 2

for s2,Tape alphabet Г can never be same as input alphabet ∑ . The tape
alphabet always contains the blank symbol, but the input alphabet cannot
contain this symbol.s2 is true

for S3 ,A Turing machine’s head can be in same location in two successive
steps, but it is possible only when the Turing machine’s head is on the
first tape square and it tries to move left. It will stay in place instead of
falling off the tape. However, if it is not on the leftmost square, then in
the next move the tape head cannot remain in the same location. So,
Turing machine’s head can be in same location in two successive
steps .s3 is true

Comments

Could you pls explain S3? Wouldn't it go on Blank?