I recently watched a Numberphile video about Langton's Ant (and the extra footage). They mention that the ant always ends up creating a highway at some point in all the initial board configurations that have been tried (though it's not been proven that this always happens). They also mention that Langton's Ant can be used for computation. The wikipedia article also states:
Additionally, it would be possible to simulate an arbitrary Turing machine using the ant's trajectory for computation. This means that the ant is capable of universal computation.
How could both claims be true? If the ant gets into a repeating highway, no further computation is possible and the ant-computer has essentially halted. If every initial configuration always ends up in a repeating highway, then how could one possible use Langton's Ant to simulate a Turing Machine?
Conversely, if Langton's Ant could simulate a Turing Machine, then one should be able to program the following program which continually flips a single bit back and forth between True and False forever:
a = True
while True:
a = not a
If one were able to come up with an initial board configuration to simulate the above with Langton's Ant, then surely that configuration would end up in a loop other than the highway, no?
I read the paper where Langton's Ant's universality was proven, but it was a little dense for me. All I could understand from it was that individual logic gates could be simulated and a finite set could be chained together. But it seemed like loops weren't possible and the program would essentially be over once the ant went through the gates.
What am I missing or not understanding?
The highway conjecture speaks about finite initial configurations (the set of black cells is finite). The Turing universality is achieved through infinite eventually periodic configurations (a bi-periodic configuration with some finite perturbation). So there is no contradiction.
Note that it is common to use eventually periodic configurations to embed Turing computations into small dynamical systems. it is the case for elementary cellular automaton 110