Turing Machines

Question 1

Recognizable Language

Answer 1

L is recognizable if there exists a TM M s.t. L(M) = L. Note that halting is not required for rejected inputs

Question 2

Decidable Language

Answer 2

L is decidable if L is Turing recognizable by some M that halts for all w ∈ Σ*

Question 3

Under what operations is the collection of decidable languages closed under?

Answer 3

• union
• concatenation
• star
• complementation
• intersection
• reversal

Question 4

Under what operations is the collection of Turing recognizable languages closed under?

Answer 4

• union
• concatenation
• star
• intersection
• homomorphism
• reversal

Question 5

Turing Machine Formalization

Answer 5

M = (Q, ∑, Γ, δ, q0, q_accept, q_reject)
where:
- Q = set of states
- ∑ = finite input alphabet
- Γ = finite tape alphabet (includes “” blank symbol; Γ = ∑ ∪ {“”})
- δ = transition function
- q0 = start state
- q_accept = set of accept states
- q_reject = set of reject states