Видеотека
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Видеотека
Архив
Популярное видео

Поиск
RSS
Новые поступления






Летняя школа «Современная математика» имени Виталия Арнольда, 2018
22 июля 2018 г. 09:30–10:45, г. Дубна, Московская область, г. Дубна, дом отдыха «Ратмино»
 


Computations: from Turing machines to Tilings, lecture 1

G. Gamard, D. S. Pchelina
Видеозаписи:
MP4 2,055.2 Mb
MP4 933.1 Mb

Количество просмотров:
Эта страница:296
Видеофайлы:122

G. Gamard, Д. С. Пчелина



Аннотация: 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.

Язык доклада: английский

Website: https://www.mccme.ru/dubna/2018/courses/gamard-pchelina.html
Цикл лекций
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024