国产91麻豆一区二区久久久

Title:        Turing Machines and Tilings

Speaker:   Prof. Peter van Emde Boas, ILLC - FNWI - University of Amsterdam  & Bronstee.com Software & Services B.V.  Heemstede

Time and location:         May 29th (Tue) 18：40－21：00  北大理教305

Abstract:

This year the world is celebrating the 100-th anniversary of the birth of A.M. Turing. One may ask why the model of a computing device he proposed in his 1936 paper has obtained the popularity that it possesses up to the present day.

Notwithstanding the fact that there have been designed a number of ingenious and unexpectedly efficient algorithms and programs for Turing Machines it is after all a model which nobody wants to use in practice. Real life computing devices based on Turing machines exist but are considered gadgets built for fun or for participation in some strange competitions.

The real reason is twofold: on the one hand this simple model is Universal in the sense that it captures the computational power of all standard and practically used computer models with a tolerable overhead penalty. The second (and to my perspective more important reason) is that the behavior of the Turing model is very easy to encode in combinatorial structures, thus leading to undecidability and computational hardness results. The model thus is used to prove negative results showing that some tasks are impossible or intolerable hard to perform.

Tiling problems - a mathematical version of the traditional Jigg-saw puzzle you have played with being a kid - are just one example of such a combinatorial structure which can encode Turing Machine computations in a very efficient way. They have the advantage that they can be understood without any preliminary mathematical knowledge. In that way they provide a road to make the introduction into computation and complexity theory far easier compared to the standard literature.

We will also point out how this convenience of tiling is connected to an important decision in the formalization of the Turing Machine model (something Turing hardly bothered about in his 1936 paper): the proper choice of representation of Turing Machine configurations.