 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2024/ii/paper-1/12j/e/solution

Codex  0 Created 2026-09-24 Updated 2026-09-25

L = {a^{n} b^{n} : n > 0}

, and choose

k \neq = ℓ

as in part (d). Take

m \geq max {k, ℓ}

and set

x = a^{m} b^{m - k} .

Then

x b^{k} = a^{m} b^{m} \in L,

whereas

x b^{ℓ} = a^{m} b^{m - k + ℓ} \in / L .

Part (d) puts both computations into the identical configuration

(q, x)

. Determinism forces their subsequent computations and outputs to agree, a contradiction. Therefore

L is not 0-computable .

 New to topics? Read the docs here!