Submitted by: YOUR NAME HERE
with COLLABORATORS’ NAMES HERE
CSC361 Spring 2025 - Assignment 4
April 16, 2025
Exercise 1. Answer each of the following questions, and explain your reasoning.
(a) Can a Turing Machine ever write the blank symbol □ on its tape?
Solution:
(b) Can the tape alphabet Γ be the same as the input alphabet?
Solution:
(c) Can a Turing Machine’s head ever stay in the same location for two steps back to back?
Solution:
(d) Can a Turing Machine contain just a single state?
Solution:
p. 1
Submitted by: YOUR NAME HERE
with COLLABORATORS’ NAMES HERE
CSC361 Spring 2025 - Assignment 4
April 16, 2025
Exercise 2. Consider the following TM M that decides the language L = {02n|n ≥ 0}
M = "On input string w:
1. Sweep left to right across the tape, crossing off every other 0.
2. If in stage 1 the tape contained a single 0, ACCEPT.
3. If in stage 1 the tape contained more than a single 0
and the number of 0s was odd, REJECT.
4. Return the head to the left-land end of the tape.
5. Go to stage 1."
We can describe this machine formally as:
Q = {q1, q2, q3, q4, q5, qaccept, qreject}
Σ = {0}
Γ = {0, x,□}
with start state q1, accepting state qaccept and rejecting state qreject. We describe δ with the following
diagram (Sipser, p. 144):
Give the sequence of configurations that M enters when started on each of the following strings:
(a) 0
Solution:
(b) 00
Solution:
(c) 000
Solution:
(d) 000000
Solution:
p. 2
Submitted by: YOUR NAME HERE
with COLLABORATORS’ NAMES HERE
CSC361 Spring 2025 - Assignment 4
April 16, 2025
Exercise 3. Show that the following language is decidable:
{⟨A⟩ | A is a DFA and L(A) is infinite}
Hint: consider what you know about DFAs and their languages...
Solution:
p. 3
Submitted by: YOUR NAME HERE
with COLLABORATORS’ NAMES HERE
CSC361 Spring 2025 - Assignment 4
April 16, 2025
Exercise 4 OPTIONAL. A Turing machine with STAY PUT instead of LEFT is similar
to an ordinary Turing machine, but the transition function has the form:
δ : Q× Γ→ Q× Γ× {R, S}
At each point the machine can move its head right or let it stay in the same position on the
tape. Show that this Turing machine variant is not equivalent to the usual version. What
class of languages do these machines recognize?
Solution:
References
p. 4

学霸联盟