Langton's Ant and Unanswerable Questions

Langton's Ant is a cellular automaton first described by Christopher Gale Langton in 1986. It looks like this:

The "Ant" exists on an infinite grid. Each cell of the grid can be either white or black, but initially all are white. Each "generation" the Ant moves according to the following rules:

• Turn left if the current cell is white, else turn right
• Change the colour of the current cell
• Step forwards

If we allow the ant to run for some time, it initially produces some very beautiful symmetries. For example:

Generation 96 displays an "S"-like pattern:

Generation 184 looks like a pokeball about to open:

Generation 368 is like a four tentacled monster:

But then it produces chaotic patterns for many thousands of steps.

We might have guessed that this chaos would proceed forever. But then at around 10,000 steps, something magical emerges:

The Ant has begun to build a structure known as the highway. The highway is an infinitely repeating pattern. It takes the ant 104 steps for each iteration of the highway, and each iteration extends the pattern along a diagonal trajectory.

But we can change things. Instead of starting with a blank grid, we could set some cells to black at the begginning. If we then run the Ant it will generate different patterns. When people try this, they find that the highway always seems to emerge sooner or later. It is widely believed that the highway is inevitable, and yet this conjecture has never been proven nor disproven, despite many years of effort.

Such a simple system to define, and yet we are unable to answer the question "Does the highway always appear, no matter the starting state?"

# Rice's Theorem

Henry Gordon Rice proved the following theorem in 1951:

All non-trivial semantic properties of programs are undecidable.

A trivial property of a program is one which is either always true or always false for every possible program.

Semantic properties are about the behaviour of the program, rather than syntactic properties which are about the source code.

A property is undecidable if it is not possible for there to exist an algorithm which correctly identifies the property for all possible inputs.

A famous example of such a non-trivial semantic property is: "Does this program halt?". We know from the Halting Problem that there can never exist a systematic way to identify whether any program halts or not.

Once again, we find that such a simple question cannot be answered.

# Rationalism and Empiricism

Rationalism and Empiricism are two different philosophical stances on how best to pursue knowledge.

• A Rationalist believes that reason is the primary way to gain knowledge. Truth is found by reasoning from first principles.
• An Empiricist believes that experience is the primary way to gain knowledge. Truth is found from direct observation and experimentation.

Neither view is always correct. Different fields of knowledge lend themselves more to rationalism while others to empiricism. Mathematics for example is exceedingly rational, whereas Biology is exceedingly empirical.

Computer Science is founded upon Mathematics, with the aim to reason about computation and in so doing to derive concrete proofs. And yet examples like Langton's Ant and Rice's Theorem demonstrate that even very simple problems can elude solution.

There is a tension between Computer Science as an academic pursuit vs Software Engineering as a professional discipline. At heart, I am a rationalist. I crave proof and certainty. But I am employed as a professional. When trying to find truth in any matter, think critically about what is provable from reason and what is not. For the unprovables, be humble and open minded. Observe, experiment and adapt to your circumstances.

Take care,

Rupert