P62 · A_LBA decidable vs E

🔊 Narration

Counting argument for A_LBA decidability, then the computation-history reduction for E_LBA undecidability.

🔊 Listen

1 · The two languages

A_LBA = {⟨M, w⟩ : M is an LBA that accepts w}

Decidable. Sipser Theorem 5.9.

E_LBA = {⟨M⟩ : M is an LBA and L(M) = ∅}

Undecidable. Sipser Theorem 5.10.

Both questions are about LBAs (linear-bounded automata — Turing machines that can only use cells holding the input). Yet one is decidable, one isn't. Why?

🔊 Listen

2 · A_LBA decidability · the configuration-count argument

Decider for A_LBA

On input ⟨M, w⟩ with |w| = n, count the maximum number of distinct configurations: |Q| · n · |Γ|ⁿ (state × head position × tape content).
Simulate M on w for at most this many steps.
If M accepts: accept. If M rejects or exceeds the bound: reject (any longer run would repeat a configuration → infinite loop).

Why this works: A loop means the same configuration repeats — so if M hasn't accepted within |Q|·n·|Γ|ⁿ steps, it never will. The bound is exponential in n, but it's FINITE, so the algorithm always halts.

🔊 Listen

3 · E_LBA undecidability · the computation-history reduction

Why the configuration bound doesn't save E_LBA

A_LBA asks about one specific w: bound the time, simulate, done. E_LBA asks about ALL possible inputs: is the language empty? You'd have to check every string — infinitely many.

Reduction A_TM ≤_m co-E_LBA

Given ⟨M, w⟩, build an LBA B_M,w whose language is the set of accepting computation histories of M on w. (A computation history is a string C₁#C₂#…#C_ℓ listing every configuration of M's run.)

Key claims:

B_M,w can verify a candidate history with three local checks (start config, every step legal, end accepting) — each uses constant tape per cell, so B_M,w is genuinely an LBA.
L(B_M,w) ≠ ∅ iff M accepts w (the witness is the accepting history).
So a decider for E_LBA would decide co-A_TM — impossible.

🔊 Listen

4 · The contrast in one sentence

Same machine model. Different scope of question.

A_LBA: "does this LBA accept THIS specific w?" — finite simulation suffices because configurations are bounded.

E_LBA: "does this LBA accept ANY w?" — checking all strings is infinite, and there's no shortcut because LBAs can encode arbitrary TM computation histories.

🔊 Listen

5 · Q&A defence notes

Q1. Why isn't A_TM also decidable by the same configuration-count argument?
A TM can use unbounded tape. The number of possible configurations is infinite: |Q| · ∞ · |Γ|^∞. So the bound is not finite, no termination guarantee.
Q2. What's the exact bound for an LBA's configurations?
|Q| · n · |Γ|ⁿ, where n = |w|. State × head position (n cells) × tape content (each of n cells holds one of |Γ| symbols).
Q3. Is the bound tight? Can an LBA actually use 2^O(n) steps?
Yes. LBA's can be programmed to enumerate every configuration before halting — equivalent to PSPACE on input of size n. So worst-case running time really is 2^O(n).
Q4. Sketch the LBA B_M,w for R1.5.
On input x (a candidate history), B_M,w does three local checks. (i) Start: is the first config q₀w? (ii) Transition: for each adjacent pair (Cᵢ, Cᵢ₊₁), do the local 2×3 windows match δ of M? (iii) End: does the last config contain q_accept? All three pass ⇒ accept x. Each check fits in |x| cells, so B_M,w is an LBA. L(B_M,w) ≠ ∅ iff M accepts w.
Q5. Why is "co-E_LBA" the natural target instead of E_LBA?
L(B_M,w) ≠ ∅ iff M accepts w — so M accepts w iff ⟨B_M,w⟩ ∈ co-E_LBA. That's literally a reduction A_TM ≤_m co-E_LBA. Since decidability is closed under complement, this gives both co-E_LBA and E_LBA undecidable.