Register

Michael Sipser Edition 3 Exercise 3 Question 5 (Page No. 188)

625 views
1 1 vote

Examine the formal definition of a Turing machine to answer the following questions, and explain your reasoning.

  1. Can a Turing machine ever write the blank symbol $\sqcup$ on its tape?
  2. Can the tape alphabet $\Gamma$ be the same as the input alphabet $\Sigma$?
  3. Can a Turing machine’s head ever be in the same location in two successive steps?
  4. Can a Turing machine contain just a single state? 

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← Previous · Michael Sipser Editi...Next → · Michael Sipser Editi...
← Previous in category · Michael Sipser Editi...Next in category → · Michael Sipser Editi...
Position:
Show:

Related questions

0 0 votes
0 0 answers
598
598 views
admin asked Oct 15, 2019
598 views
Michael Sipser Edition 3 Exercise 3 Question 10 (Page No. 188)
Say that a write-once Turing machine is a single-tape TM that can alter each tape square at most once (including the input portion of the tape). Show that this variant Tu...
1 1 vote
0 0 answers
608
608 views
admin asked Oct 15, 2019
608 views
Michael Sipser Edition 3 Exercise 3 Question 8 (Page No. 188)
Give implementation-level descriptions of Turing machines that decide the following languages over the alphabet $\{0,1\}$. $\{w \mid w \text{contains an equal number of...
0 0 votes
0 0 answers
543
543 views
admin asked Oct 15, 2019
543 views
Michael Sipser Edition 3 Exercise 3 Question 7 (Page No. 188)
Explain why the following is not a description of a legitimate Turing machine.$M_{bad} = “$ On input $\langle p \rangle,$ a polynomial over variables $x_{1},\dots,x_{k}:$...
0 0 votes
0 0 answers
406
406 views
admin asked Oct 15, 2019
406 views
Michael Sipser Edition 3 Exercise 3 Question 9 (Page No. 188)
Let a $k-PDA$ be a pushdown automaton that has $k$ stacks. Thus a $0-PDA$ is an $NFA$ and a $1-PDA$ is a conventional $PDA$. You already know that $1-PDAs$ are more power...