Computations: from Turing machines to Tilings, lecture 4

What is a computation? What is a computer? Can we express these concepts formally? The answer to the last question is yes! The abstract model for a computer is called a Turing machine; this concept was actually invented before the first computer (in the modern sense) was built. A Turing machine can do all that a programming language or a CPU can do (and vice-versa), but is much simpler to understand and to analyze. This simplicity allows to show very general results, which hold for any kind of computer or programming language. For instance: there exist formal questions which cannot be answered correctly by a computer, ever. In the first class, we will introduce Turing machines and review a few important results about them. It turns out that the concept of «computation» isn't limited to Turing machines. Indeed, it is possible to embed a Turing machine in many different mathematical objects, which turns them into computers. One famous example of this is Wang tilings. In Wang's formalism, we are given a finite set of jigsaw puzzle pieces, called tiles, and we are asked to tesselate the whole geometrical plane with them. We have the right to copy each tile as many times as we want (infinitely many times), but we cannot rotate the tiles. The question of whether a given tileset can tesselate the plane is called the Domino problem. In the second class, we will discover all about the Domino problem, why it was introduced and how researchers tried to solve it in the 1960's. In the third class, we will show how to encode different things, notably a Turing machine, inside the Domino problem. This will explain why it was so hard to solve it. Finally in the fourth class, we will study a specific set of tiles with remarkable properties, introduced in 1996 by Kari and Culik. It considerably simplifies the embedding of computations inside tiles.