Extended discussion

of Cryptic Crossword #2

Spoilers ahead! You have been warned. I'll start by providing answers for the clues, and then go on to reveal some other things that you might want to figure out on your own. So scroll wisely.

The clues

First of all, if you couldn't make heads or tails of any of the clues, you need to understand how cryptic clues work. Read up on that and try again. Solving cryptic crosswords is a highly rewarding pastime, so it will be worth the effort.

Made from wings I've lost in dreams.

Definition: Lost in dreams. Wordplay: Made from wings = pens, literally “I've”. Pensive.

(This clue used to read “Wings I've lost in dreams”, but I decided to change it to make it more fair. I didn't change the title of the cryptic.)

Colourful birds with infestations.

Definition: Colourful birds. Wordplay: With = par, infestations = rots. Parrots.

Social insect fills awkward silence with hymns of loyalty.

Definition: Hymns of loyalty. Wordplay: Social insect = ant, fills awkward silence = hems. Anthems.

We hover, worried somebody.

Definition: Somebody. Wordplay: Anagram of “we hover”. Whoever.

Reportedly fell out of the sky and governed.

Definition: Governed. Wordplay: Homophone of “fell out of the sky” = rained. Reigned.

Proud to upset somebody who never graduated.

Definition: Somebody who never graduated. Wordplay: Anagram of “proud to”. Dropout.

Partially applies spicy relishes.

Definition 1: Partially applies [a function] (Computer Science term). Definition 2: Spicy relishes. Curries.

Imply fraud with a written statement.

Definition: Imply. Wordplay: Fraud = con, written statement = note. Connote.

Hoggish earl goes after tableware from which regurgitated ale was removed.

Definition: Hoggish. Wordplay: Tableware = porcelain, remove anagram of ale (ela), earl = E. Porcine.

Gee, lovely ornament.

Definition: Ornament. Wordplay: Gee = cor, lovely = nice. Cornice.

(This clue used to read “Gee, lovely, said Eve”, where Eve is a homophone of eave.)

Vocalists made out of recycled cartons.

Definition: Vocalists. Wordplay: Anagram of “cartons”. Cantors.

Baked delicacies filled with a black liquid and small fingers.

Definition: Small fingers. Wordplay: Baked delicacies = pies, a black liquid = ink. Pinkies.

Otis abused a programming language without any signs of distress.

Definition: Without any signs of distress. Wordplay: Anagram of “otis”, a programming language = C. Stoic.

I boiled rice at a lower temperature.

Definition: At a lower temperature. Wordplay: Literally “I”, anagram of “rice”. Icier.

Perhaps Darling and I've squeezed into a luxury car.

Definition: Perhaps Darling. Wordplay: Literally “I've”, a luxury car = RR. River.

Small nut found inside a cornet.

Definition: Small nut. Wordplay: Found inside “a cornet”. Acorn.

Antiquated base next to an alien group of instrumentalists.

Definition: Group of instrumentalists. Wordplay: Antiquated base = oct, an alien = ET. Octet.

Dangle a part of Pedro openly.

Definition: Dangle. Wordplay: A part of “Pedro openly”. Droop.

Gather over a repeating sequence of instructions.

Definition: A repeating sequence of instructions. Wordplay: Gather = pool, over = backwards. Loop.

The German random number generator.

Definition: Random number generator. Wordplay: “The” in German. Die.

Looked up “copulative”.

Definition: Copulative. Wordplay: Looked = saw, up = backwards. Was.

Structure

Figure 2: The first 2500 steps of Rule 124 (only the leftmost 200 columns are shown).

Wings I've lost in dreams features an infinitely large grid that can be regarded as an array of macro blocks, eight by six squares in size:

Figure 1: A macro block

Each macro block has an output, indicated by a star in Figure 1 above. The output is either I or O, and thus represents one bit of information.

The seven-letter horizontal word along the bottom of the macro block—we'll refer to it as the pivotal word—determines the output based on its first, third and seventh letter. Of all the seven-letter words given by the clues, there are exactly eight that can fit in this slot; one for each possible combination of three binary inputs.

The inputs of a macro block correspond to the outputs of the three blocks above it, i.e. the neighbours to the north-west, north and north-east. This information is routed by means of intermediary word slots, each capable of holding one of a pair of words. In this way, information flows downwards through the grid. The I or O at an output selects one of two possible five-letter words going down. Each of these words fully determines the two horizontal seven-letter words that intersect it, and these carry the information further towards the pivotal words of the appropriate neighbouring macro blocks. In one place, marked with a dot in Figure 1, two words cross without influencing each other. This was achieved by ensuring that all words that may appear in these slots have the same letter (an O) at the point of intersection.

The following table summarises the relation that is enforced between the inputs and outputs of each macro block. The order of the columns in the table corresponds to the order of the letters within the pivotal words, i.e. the output is given in the third column from the left.

Cellular automaton interpretation

This array of macro blocks behaves like a cellular automaton. Each row of cells corresponds to the state of the automaton at a given moment, and is comprised of an infinite number of binary digits. Each row of macro blocks fully determines what words can go into the row below it, just like the state of a cellular automaton fully determines the next state. The update rule for the automaton is determined by the set of pivotal words provided by the clues. The clues of this cryptic have been chosen in such a way that the state of the cellular automaton is updated according to Rule 124 (which is the number obtained, in binary, from the output column of Table 1 in bottom-up order). This is a mirror version of the more well-known Rule 110.

The initial state (or configuration) of the automaton is determined by the Os at the top of the grid. The left edge of the grid has been crafted to make the north-west neighbour of every leftmost cell be an I-block. As it happens, these conditions trigger a long and beautifully complex sequence of state interactions in the Rule 124 automaton, shown in Figure 2, in which the pattern comprised of the provided ANSWER letters appears exactly once along the left edge of the grid (indicated by a small arrow).

Obtaining the final answer

It should be mentioned at this point that the ANSWER condition appears after 2149 state transitions. In order to obtain the final answer in the traditional way, one would have to pencil in over fifteen million words. At one word per second, working eight-hour days, that'd still take roughly a year and a half. Please be advised that you can solve the problem considerably faster by implementing a computer program that simulates the cellular automaton—even if that involves learning how to program a computer in the first place. Or, if you still trust me, you could just zoom in on Figure 2.

You may have tried to work backwards from the ANSWER letters in order to figure out what letters can possibly appear in the grey squares. Due to the complex behaviour of Rule 124, it is generally not possible to go back in time and determine an earlier state vector; one has to run the automaton forwards.

Based on our knowledge of how the macro blocks work, we can nevertheless reduce the number of possible combinations of letters, but this will not be enough. The grey squares can in fact accomodate two different six-letter words, each of which is the name of a pioneer in Computer Science. A famous thesis relavant to the present discussion has been named after these two pioneers. But in order to determine which of the two names is the final answer, you're going to have to run the automaton.

Universality

It has been proved that Rule 110 (and thus Rule 124 by symmetry) is Turing complete. This means that the cellular automaton is capable of carrying out computations—in fact, that it can evaluate any computable function.

All you need to do is encode the desired computation and its input in the initial state vector, which can be an arbitrarily large binary number padded with an infinite number of zeros to the right. Then you run the automaton forwards until the ANSWER condition (or some similar condition of your choice) is true, at which point you read out the solution. The details of how you would represent the computation using a bit vector are provided in the aforementioned proof.

With the given ANSWER condition, the function can only produce one bit of output. However, it is always possible to represent an integer-valued function F(x) as a boolean-valued function F'(x, b) that computes F(x) and then extracts bit b of the result.

Now, suppose you had been asked to solve this cryptic crossword without being restricted to a particular initial state, i.e. without having any O letters already filled-in. This version of the cryptic would have many possible solutions, and would, by virtue of being structurally equivalent to the Rule 124 cellular automaton, be a universal Turing machine. So in principle, when you scratch out the Os, Wings I've lost in dreams generalises into a fully functional computer, capable of running any software by emulation. You could run a crossword solver on it, for instance, or a program that simulates cellular automata.

None of this is practical. Even the most trivial of programs would require initial state vectors spanning millions of bits. But it is possible. And so, what you have seen turns out to be the world's first cryptic crossword that is capable of solving itself.