,
13 tweets,
4 min read
Read on Twitter
You can translate a computer program into a set of tiles: attempting to tile the plane necessarily 'runs' the program. Here's a tiling attempt using tiles from a palindrome-checking program, on inputs 10010 and 10101. Details in thread, 1/n. (I'm fond of this one, please RT)
A Turing machine (TM) is a simple model of computation. It has a tape (memory), a state, and a read/write head. A 'program' in this model is a set of rules like "when in state A and reading symbol 0, write symbol 1, go to state B, and move the head to the right" 2/n
There's a mapping from TMs to sets of square tiles with bumpy edges to indicate values on the tape and the value/location of the state, being passed upwards in the tiling between successive states of the TM. E.g., here are some tiles for transmitting tape values upwards 3/n 
Here are two tiles that change the value written on the tape and also change the state of the machine (the more complicated squiggle on the RHS) 4/n
These two tiles leave the tape unchanged. The left tile is for moving the Turing machine read/write head one step to the right. The right tile is for receiving the read/write head from one step to the right 5/n
And here's the full set of tiles from the palindrome checking program. For simplicity, I've used a Turing machine whose tape extends infinitely to the right but not the left and an alphabet of 4 symbols: 0, 1, 'blank' and 'end of tape' 6/n
We seed the tiling with an initial row giving the input of the TM. We only try to tile above the input line. Along with the TM's tape only extending to the right, this means we've translated a TM-and-input into a quarter-plane tiling problem from an initial configuration 7/n
In the gif, I've restricted the view of the attempted tiling to a narrow horizontal region, but it's trivial to extend each row infinitely to the right 8/n
This mapping means you can apply some computability results to tiling problems. E.g., due to the undecidability of the halting problem, there's no general procedure that can tell you if a given set of tiles (+ initial row) can tile the plane 9/n
Programs that terminate → tile sets that cannot tile the plane. Programs that repeat previous states → tile sets that tile the plane periodically. Programs that run forever without repeating previous states → tile sets that can tile the plane but only nonperiodically 10/n
And of course, because there are universal Turing machines, there exist universal tile sets, where you can specify a program and input with an initial row, which will be 'run' by attempting to complete the tiling 11/n
Although Turing machines are already pretty dumb, somehow tiling-as-computation seems even more dumb to me. It feels strange that you can 'do computation' by just trying to fit shapes together 12/n
On the other hand, I can't imagine a natural process that implements a TM directly, but I can imagine a natural process that does non-trivial computation by fitting shapes together (this features in a wonderful novel by @gregeganSF. I won't say which to avoid spoilers) 13/13
