2. Variations of Turing Machines, Semidecidable Languages & Enumeration

What is the difference between a nondeterministic TM and a deterministic TM?

1. δ has the form δ : (Q − {ha}) × Γ → 2^(Q x Γ x {L, R, S}

2. The reject state hr is replaced by h∅, where δ(h∅, a) = ∅ for all a ∈ Γ.

When is an input string accepted by an NTM?

If there exists a transition sequence from q₀∆w to an accepting configuration

What happens if the TM at the leftmost tape cell tries to move left?

It crashes:

qav ⊢ h∅av if δ(q, a) = (r , b, L) for some r ∈ Q and b ∈ Γ

What is the language that this NTM accepts?

L(N) = Σ*{abc, cab}Σ* if Σ = {a, b, c}

What is the proof for proving L(N) = L(D)
Where N - NTM and D - DTM

Construct a TM D which simulates N by trying all possible branches of N’s nondeterministic computation in breadth-first fashion. If D finds the accept state on one of these branches, it accepts, otherwise, the simulation rejects.

What is the transition function for a Multitape TM?

δ: (Q - {h_a,h_r}) x Γⁿ → Q x Γⁿ x {L, R, S}ⁿ where n >= 2 and n is the number of tapes

What is a configuration in an NTM?

An n-tuple (u₁qv₁, u₂qv₂, . . . , u_nqv_n), where q ∈ Q and u_i , v_i ∈ Γ*

What is the intial configuration for an input w in an NTM?

q₀∆w , q₀∆, . . . , q₀∆

When is a language L semidecidable?

If there exists a turing machine that accepts L (is generated by some unrestricted grammar)