Descriptions, domains and impossible decision procedures
Bring ideas together without being told which method to use. Show the reasoning that makes your result valid.
Suggested session length: 95 minutes, as an unvalidated planning estimate. This collection contains 3 tasks; choose a manageable set and return for further sessions. Completing the whole collection may take substantially longer. This is a unit assessment, not a full course or AP examination.
Attempt these changed constructions before opening public solutions. Write both directions of each encoding or reduction claim.
State whether a description, a finite word, an infinite sequence, a program or the function it computes is the object being counted.
Written arguments need review. A finite table, a timeout or a saved response does not certify an infinite theorem or a program-correctness claim.
Loading saved assessment responses…
0 of 3 tasks have recorded responses. No overall mastery score is assigned.
For a binary word w of length m define E(w)=1^m 0 w, where 1^m means m copies of the symbol 1. Encode a finite ordered list [w₁,…,wₖ] as 1^k 0 E(w₁)…E(wₖ). Give a terminating decoder that rejects malformed input and prove the encoding is injective. Encode the empty list, the one-element list containing the empty word, and [01, empty]. Derive the total encoded length and show that the family of finite lists is countably infinite. Explain why different encodings of two programs would not imply different computed functions.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
An infinite binary sequence is ultimately periodic if it consists of a finite prefix u followed by infinitely many copies of a nonempty finite period v. Prove that the set U of these sequences is countably infinite, allowing several descriptions (u,v) of the same sequence. Given any enumeration r₀,r₁,… containing every member of U, define d(n)=1−rₙ(n). Prove exactly what this establishes and diagnose the false conclusion “U is uncountable.” Can the first eight bits alone prove that a sequence is not ultimately periodic?
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Suppose Finite(A) is an algorithm promised that A is a total decider on binary words. On every such valid input, Finite itself halts and correctly reports whether A accepts only finitely many words. Given arbitrary valid program P and fixed input x, construct Q which, on input y, simulates P on x for at most |y| transitions and accepts exactly when that simulation halts within the bound; otherwise it rejects. Include the initial state in the bounded halting check. Prove Q is total even when P does not halt. Characterize its accepted language in both cases and use Finite to derive a contradiction. Explain why this reduction respects the total-decider promise, while an unbounded “simulate P first” wrapper might not. Does any one finite timeout establish that P never halts?
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Review and revisit
Use each rubric to identify a valid argument, a missing condition or a step to revise. For independent evaluation, ask a teacher or reviewer to examine the complete reasoning. Self-review and recorded responses are not verified assessment results.
Coverage and targeted lesson returns
For a binary word w of length m define E(w)=1^m 0 w, where 1^m means m copies of the symbol 1. Encode a finite ordered list [w₁,…,wₖ] as 1^k 0 E(w₁)…E(wₖ). Give a terminating decoder that rejects malformed input and prove the encoding is injective. Encode the empty list, the one-element list containing the empty word, and [01, empty]. Derive the total encoded length and show that the family of finite lists is countably infinite. Explain why different encodings of two programs would not imply different computed functions.
An infinite binary sequence is ultimately periodic if it consists of a finite prefix u followed by infinitely many copies of a nonempty finite period v. Prove that the set U of these sequences is countably infinite, allowing several descriptions (u,v) of the same sequence. Given any enumeration r₀,r₁,… containing every member of U, define d(n)=1−rₙ(n). Prove exactly what this establishes and diagnose the false conclusion “U is uncountable.” Can the first eight bits alone prove that a sequence is not ultimately periodic?
Suppose Finite(A) is an algorithm promised that A is a total decider on binary words. On every such valid input, Finite itself halts and correctly reports whether A accepts only finitely many words. Given arbitrary valid program P and fixed input x, construct Q which, on input y, simulates P on x for at most |y| transitions and accepts exactly when that simulation halts within the bound; otherwise it rejects. Include the initial state in the bounded halting check. Prove Q is total even when P does not halt. Characterize its accepted language in both cases and use Finite to derive a contradiction. Explain why this reduction respects the total-decider promise, while an unbounded “simulate P first” wrapper might not. Does any one finite timeout establish that P never halts?
