Post by Graham Shawcross (2012)
Wang pointed out that it is possible to find sets of Wang tiles that mimic the behaviour of any Turing Machine (Wang 1975).
A Turing machine can compute all recursive functions, that is functions whose values can be calculated in a finite number of steps. That is to do, however inefficiently, what any conceivable computer can do.
The basic idea is to use rows of tiles to simulate the tape in the machine, with successive rows corresponding to consecutive states of the machine.
Metadata
- suggesters: neauoire
- curators: neauoire