Redirected
edited by
3,766 views
4 votes
4 votes
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
edited by

2 Answers

0 votes
0 votes
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

Related questions

1 votes
1 votes
0 answers
1
Chhotu asked Nov 25, 2017
997 views
Hi Guys, I think $S_{1}$ is not TRUE because input could be copied in other part of tape. So power of TM will not reduce. What is your opinion ?
0 votes
0 votes
1 answer
2
Venkat Sai asked Feb 3, 2018
382 views
Consider the Turing machine when the input is still left and the turing machine halts will it accept it by halting or will it process the entire input left??
2 votes
2 votes
0 answers
3