Process

Hmm, let’s see …

So it’s essentially the natural numbers with subsequences missing. We’re starting with one missing, then three, then …

This is almost the “negative” of the above. It’s shifted, though …

I think I see it. Maybe it becomes clearer if I try to formulate it out? But not now … I’m too tired and I need to leave the train soon …

A few days later …

Okay, let’s see. Let’s, write it down, shall we?

Some failed attempts ensue …

Hmm, okay. Not that simple, then. The author describes the FIGURE-FIGURE as follows:

In this clever drawing, there are two nonequivalent ways of characterizing the black regions:

1. as the negative space to the white regions.
2. as altered copies of the white regions (produced by coloring and shifting each white region).

That specific parallel is definitely there, but we still need to characterise the “white” region of the sequence first, don’t we? Or can we do both in one fell swoop?

Why is this so hard to think about? It kind of folds in on itself …

A couple of weeks later …

Okay, I think I need a different approach. Maybe we can try to get a different angle by representing the gaps as additions instead? So the first jump is $+2$, the second one is $+4$, …

Oooh, cool! That’s the exact “negative space” of the sequence! So the differences between the elements of the sequence increase by one, skipping differences which already exist as elements within the sequence. Okay, wait, I think we can base a direct characterisation upon that …

My Solution

Let $s_{i\geq1}$ be the sequence presented in the book:

Then $s$ can be characterised as follows:

As an (admittedly very inefficient) Haskell program:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

-- si: Compute the i-th element of the sequence.
si :: Int -> Int
-- Base cases.
si 1 = 1
si 2 = 3
-- Step case.
si n
  -- Case where incremented difference exists in s.
  | isInS (n-1) potNextStep = (si (n-1)) + potNextStep + 1
  -- Case where incremented difference does not exist in s.
  | otherwise               = (si (n-1)) + potNextStep
  where
    -- isInS m k: Check if k appears in s as the m-th element or before.
    isInS :: Int -> Int -> Bool
    isInS 0 _ = False
    isInS m k = k == (si m) || isInS (m-1) k
    -- Calculate the incremented difference for a new step.
    potNextStep :: Int
    potNextStep = (si (n-1)) - (si (n-2)) + 1

-- And, lastly, s as an infinite list because Haskell is cool.
s :: [Int]
s = [ si x | x <- [1..] ]

Comments

I believe the connection to the FIGURE-FIGURE can be spelled out as follows;

Exactly like the black regions of the FIGURE-FIGURE, the numbers that are not in $s$ can be characterised in two ways:

• Simply as the numbers that are not in $s$ (i.e. as its negative space).
• And also as the differences between any two neighbours of $s$ (i.e. as an operated upon copy of $s$).

Which is really cool.

Also, as we have just seen, the sequence can be generated according to typographical rules (namely the ones of the algebraic definition given above), so it must be recursively enumerable. And as its complement can also be generated in this way (namely by the extra step of extracting the differences), it must therefore also be recursive.

It is also really interesting to me to see the difference to how we defined recursive enumerability and recursivity in uni; We called a set (or rather a language in that context) recursively enumerable if there exists a Turing machine which can decide whether an element is in the set, but which may run indefinitely if an element is not within the set. And we called a set recursive if such a Turing machine exists which also always halts. So I suppose that there is some kind of “isomorphism” (in the sense in which the author uses it in the book, not the formal one) between formal systems and Turing machines. Which reminds me of a theorem we’ve touched upon just shortly this semester; the Curry-Howard Correspondence.