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
-
-
Prikaži ovu nit
-
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/npic.twitter.com/a1fNhGyR2I
Prikaži ovu nit -
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/npic.twitter.com/BfaAjbNDpk
Prikaži ovu nit -
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/npic.twitter.com/aNj2CZetTv
Prikaži ovu nit -
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/npic.twitter.com/GV8du0bR7k
Prikaži ovu nit -
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
Prikaži ovu nit -
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
Prikaži ovu nit -
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
Prikaži ovu nit -
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
Prikaži ovu nit -
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
Prikaži ovu nit -
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
Prikaži ovu nit -
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/13Prikaži ovu nit
Kraj razgovora
Novi razgovor -
Čini se da učitavanje traje već neko vrijeme.
Twitter je možda preopterećen ili ima kratkotrajnih poteškoća u radu. Pokušajte ponovno ili potražite dodatne informacije u odjeljku Status Twittera.