UNIGE document Doctoral Thesis
previous document  unige:1332  next document
add to browser collection
Title

Calculabilité des pavages

Author
Weiss, Michael
Directors
Lafitte, Grégory
Defense Thèse de doctorat : Univ. Genève, 2008 - Sc. 4021 - 2008/09/19
Abstract Au début des années 60, Wang a introduit un modèle de pavage du plan à l'aide de tuiles orientées de taille unitaire aux bords colorés pour résoudre des problèmes de logique. Ce modèle a été montré Turing-équivalent par Berger. Nous nous intéressons à la calculabilité de ce modèle en introduisant des outils sur les pavages permettant d'obtenir des résultats plus généraux sur les jeux de tuiles. A l'aide de notions de simulation, nous obtenons une première approche de l'universalité puis nous montrons quelques uns des théorèmes fondamentaux de la calculabilité (Kleene, Rice...), dans le cadre de pavages, toujours relativement à certaines notions de simulation. Ces résultats nous permettront d'obtenir, dans un premier temps, de nouvelles preuves sur des théorèmes classiques des pavages et, dans un deuxième temps, de construire un cadre de constuction de jeux de tuiles apériodiques.
Keywords Modèles de calculPavagesCalculabilité
Stable URL http://archive-ouverte.unige.ch/unige:1332
Full text
Thesis - public document Free access
Identifiers
URN: urn:nbn:ch:unige-13320
Structures

209 hits

193 downloads

Update

Deposited on : 2009-04-07

Export document
Format :
Citation style :