Tilings and Turing Machines: Computing with Wang Tiles by Mac Carso '23, Mathematics Colloquium

Tilings and Turing Machines: Computing with Wang Tiles by Mac Carso ’23, Mathematics Colloquium, Wednesday, April 19, 1 – 1:45 pm, North Science Building 113, Wachenheim.

Abstract:  A Turing machine, proposed by Alan Turing in 1936, is a model of a computing machine that uses a predetermined set of rules to evaluate a result from a set of inputs.  In 1961, mathematician Hao Wang invented “Wang tiles” for completely unrelated purposes, however, it was later discovered that these tiles could be used to execute any program that a Turing machine could.  In this colloquium, we will introduce some basics of tiling theory and explore the intuition of how Wang tiles can perform these programs. Then, we will work through some examples of the specific types of calculations these tiles can perform.