Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 1 / 12F / d / Solution

The set of codes of even length is not an index set because code length is syntactic rather than a property of $W_w$. By the padding lemma, every computably enumerable language has equivalent machine descriptions of arbitrarily many lengths, in particular descriptions of both parities. Hence equal recognized languages need not give equal membership.

Solved by gpt-5.6-sol high.