Try
A file containing 0 is different from a file containing 00, and both differ from an empty file. Before describing programs or mathematical objects, we need codes that preserve such distinctions. A binary word is a finite ordered string of zeros and ones. Write ε for the empty word, whose length is zero. The symbol ε is our notation for emptiness, not an additional bit stored in the file.
List every binary word without skipping one: first ε, then 0, 1, then 00, 01, 10, 11, then 000, and so on. Within a fixed length, use dictionary order with zero before one. This is length-lexicographic order. Ordinary lexicographic order alone places infinitely many words beginning with zero before 1, so it does not give this natural-number enumeration.
| Length ℓ | Words at that length | Ranks, starting at zero |
|---|
| 0 | ε | 0 |
| 1 | 0, 1 | 1–2 |
| 2 | 00, 01, 10, 11 | 3–6 |
| 3 | 000 through 111 | 7–14 |
| 4 | 0000 through 1111 | 15–30 |
Write the word at rank 9 and the rank of 010. These are the same question in opposite directions. There are seven shorter words; 010 has ordinary binary value two. Its rank is therefore nine. The leading zero remains part of the word even though it does not change its ordinary numerical value.
Predict
Predict whether raw concatenation encodes a pair of words uniquely. A receiver sees 1011. This might mean the pair (1, 011) or (10, 11). Knowing the total length does not identify the dividing point. A successful pair code must supply that missing boundary information.
Try this repair: for a pair (u, v), first write as many ones as there are symbols in u, then a zero delimiter, then u, then v. In notation, E(u, v)=1^ℓ0uv, where ℓ is the length of u and 1^ℓ means a run of ℓ ones. This is string concatenation, not numerical multiplication or exponentiation of a number. For u=10 and v=011, the pieces are 11, 0, 10, 011, giving 11010011.
Predict what changes when u is empty, when v is empty, and when both are empty. The delimiter is still required. In particular, the code for (ε, ε) is 0, not ε. Do not remove the delimiter as an alleged redundant leading zero.
Experiment
Act as the decoder for 11010011. Stop at its first zero. Two initial ones announce that the next two bits after the delimiter belong to u. Those bits are 10; everything left, 011, belongs to v.
| Step | Information read | Remaining input |
|---|
| Read length prefix | 11 means length 2 | 010011 |
| Consume delimiter | 0 ends the prefix | 10011 |
| Read exactly two bits | u=10 | 011 |
| Read the remainder | v=011 | empty |
Now change just the prefix to three ones, giving 111010011. Decode it without using the previous answer. The answer is u=100, v=11. A changed prefix changes the boundary; a decoder must follow the code, not guess the author’s intention.
Also attempt 11101. It announces three bits for u but supplies only one after the delimiter, so it is invalid. A string with no zero is invalid too. Conversely, any string with a first zero and at least as many following bits as there are initial ones decodes successfully. The remainder may be empty. These are exact tests of code validity, requiring only a finite scan.
For a second action, decode rank 20. Find its block before converting any bits: 15 through 30 is the length-four block. Subtract 15 to get five, and write five with exactly four bits: 0101. Writing 101 would discard the recovered length and give a different rank.
Understand
For a length-ℓ word, the number of shorter words is 1+2+⋯+2^(ℓ−1)=2^ℓ−1, with the empty sum zero when ℓ=0. At that length, binary values run in order from zero to 2^ℓ−1. Thus
rank(w)=2^ℓ−1+value(w).
Every nonnegative integer belongs to exactly one block from 2^ℓ−1 through 2^(ℓ+1)−2. These blocks are adjacent, disjoint and unbounded. Subtract the block’s first rank and write the result with exactly ℓ bits. This constructs an inverse for every rank, not merely the examples in the table. It proves a bijection between finite binary words and nonnegative integers.
The pair decoder also proves a general statement. The first zero uniquely determines ℓ. The next ℓ positions uniquely determine u, and the remaining positions uniquely determine v. Encoding this recovered pair reproduces the original valid string; decoding an encoded pair recovers both components. Hence two different pairs cannot share a code. There is no assumption that the pair’s components are nonempty or lack leading zeros.
Any fixed finite alphabet can be encoded in binary using equally long blocks: choose enough bits to assign each symbol a distinct block. Some blocks may remain unused. A word becomes a sequence of blocks, and a known block width recovers its symbols uniquely. Therefore all finite words over that alphabet, and any subset consisting of valid program descriptions, are at most countable.
This last conclusion concerns syntax, the written description. Different descriptions may have the same meaning. If each description specifies a function, there can be no more represented functions than descriptions: assign each represented function its least-ranked description. Distinct functions have distinct chosen descriptions. This is a mathematical existence argument; it does not provide an algorithm for deciding whether two programs compute the same function. Nor does it establish that every conceivable function is represented.
An always-halting syntax checker lets us scan descriptions in rank order and output the valid ones. Each fixed valid description is eventually reached. Running each accepted program to completion before continuing is a different procedure: one nonterminating program can stop that procedure from reaching later descriptions. Finite source text does not imply a finite run. This distinction does not by itself prove a general undecidability theorem; it identifies precisely what the proposed listing procedures do and do not guarantee.
Apply
Encode a finite subset of the nonnegative integers by membership bits in increasing index order: the first bit says whether zero belongs, the second whether one belongs, and so on. For the set containing 0, 2 and 3, the word is 1011. Stop at the largest included integer; thus a nonempty canonical code ends in one. Use ε for the empty set.
Why impose that stopping rule? Without it, appending zeros changes no membership decision: 1, 10 and 100 would all describe the singleton containing zero. With the rule, decode the one positions and then encode again. The last one is the largest included index, so both operations recover exactly the original object. This proves a bijection between finite subsets and canonical words, and therefore shows countability.
There is also a direct integer code: add 2^i for every included index i. Our worked set gives 1+4+8=13. Notice that the displayed membership word 1011 lists low indices first; reading that string as an ordinary high-place-first binary numeral would give eleven instead. Define the convention before using a numerical decoder. Integer thirteen has ordinary binary notation 1101, whose one positions recover the worked set. Zero codes the empty set.
Repair this claim: “We checked the first thirty ranks, so all descriptions have unique codes.” The checks can detect mistakes, but the conclusion requires the disjoint-block inverse argument. Similarly, a few correctly decoded pairs do not prove injectivity; the first-delimiter and fixed-length reasoning does.
As a nearby exercise, rank 001, then encode the pair (0, 10). Check your answers only after writing the intermediate steps: rank 001 is 7+1=8; the pair code is 10 followed by 0 followed by 10, namely 10010. Decoding that five-bit word returns one bit for its first component and two for its second.
Continue
Complete the written tasks below with two-way recovery arguments. State whether you are counting descriptions, listing syntactically valid descriptions, or deciding something about their behavior. These are different claims with different evidence requirements.
Return to cardinality and bijections for the distinction between an injection and a bijection. The present lesson supplies concrete codes that later impossibility arguments can use. It does not yet show that any particular semantic decision problem is undecidable. A countable collection can still contain descriptions whose behavior is difficult to determine, and a successful finite decoding rule does not solve that behavioral problem.
