Let be the set of all finite strings of bits and let be a subset of such that . Binary operator when applied on strings represent string concatenation.
Lemma 1. If for each determining whether is computable and there exists a total computable predicate that for each determines whether there exists such that , then there exists a computable bijection between and , where is the set of natural numbers
Proof. Suppose that there is such . We show an algorithm for constructing and using , such that . We implement function
g in Haskell:
data Bit = B0 | B1 deriving Eq g :: Integer -> [Bit] g n = g1 n  True where g1 :: Integer -> [Bit] -> Bool -> [Bit] g1 n str allowEnd | end = ifEnd | append0 && append1 = ifBoth | append0 = next B0 | append1 = next B1 where end = allowEnd && (p str) append0 = f $ str ++ [B0] append1 = f $ str ++ [B1] ifEnd :: [Bit] ifEnd | n == 0 = str | n /= 0 = g1 (n - 1) str False ifBoth :: [Bit] ifBoth = g1 (n `div` 2) (str ++ [int2bit $ n .&. 1]) True next :: Bit -> [Bit] next a = g1 n (str ++ [a]) True int2bit :: Integer -> Bit int2bit 0 = B0 int2bit 1 = B1
p determines whether a binary string belongs to , and function
f satisfies the definition given in the lemma. While
n is nonzero, in each recursive call of
g1 the integer
n either decreases, or parameter
allowEnd goes from
False, and when it goes to
False in the next iteration either
n must decrease, or the recursion base case is hit. If
n is zero, then at most finite amount of recursive calls will be performed (until
True), and it is guaranteed by
f that it terminates.
Since is a total computable function and since we can enumerate all possible strings in
P by eliminating strings from
S that are not in
P, it proves that the inverse of (which is ) is also a total computable function.
One of the interesting corollaries is that we can create a bijection between natural numbers and sudoku puzzles that have the following properties:
- The sudoku grid has dimensions , where is a perfect square
- At least one tile is empty
- There is exactly one valid solution
- If we remove any number that is already given, the solution will no longer be unique
This is usually a description of a good and hard sudoku puzzle. It is good because there is exactly one solution and it is hard because it has the minimum amount of given numbers. Each sudoku puzzle can be represented as an array of integers (and is the square root of the array's length). Since all integers are bounded, and each integer appears the same number of times for a fixed , then for any fixed , a sudoku with dimensions can be represented using a fixed amount of bits. Clearly, we can well-define to contain only sudoku puzzles that are both good and hard. Then we can construct to check whether the given string of bits can be a pefix of some such sudoku. Finally, we can use to filter only sudoku puzzles that we are interested in. We can then reconstruct the sudoku grid from the bit array.
However, it can be shown that computing , and is NP-hard, so it has at least exponential time complexity (assuming ).