Date: Mon, 06 Jan 1997 11:40:17 +0100 From: Marc Daumas Newsgroups: ensl.seminaires To: "DMI, Secretariat" , "DMI96, Eleves" , "LIP, Tous" , "MIM, Profs" , "MIM94, Eleves" , "MIM95, Eleves" , "Ortega, Hughette" Subject: Seminaire d'Informatique des Eleves [07/01] Bonjour et bonne année à tous, Voila une annonce un peu precipitée par les vacances pour le séminaire de demain, mardi 07 janvier. Comme je vous l'avais dit lors de notre dernier séminaire, nous commençons l'année 1997 avec un séminaire d'un étudiant. Il s'agit d'Olivier Teytaud, élève en seconde année du MIM. Ne vous laissez pas impressioner par le résume un peu austère, vous apprendrez beaucoup de choses. Les horaires du séminaire des élèves restent inchangés 13h30-14h30, amphi A. Ce sera le seul sémianire de janvier, ils reprendront après la période des partiels en février. Titre et Résumé --------------- Des problèmes issus de la génétique ont été reformulés par le professeur Yuri Matiyasevich jusqu'à en faire un problème de décidabilité de l'arrêt d'automates appelés machines de Matiyasevich. Ces machines sont munies d'un unique registre entier signé X de taille illimitée, et le jeu d'instruction est le suivant: X <- X + 1 X <- X - 1 X <- k.X X <- X/k (partie entière inferieure) Si X=0 alors goto ligne i Si k|X alors goto ligne j avec k un entier fixe pour tout le programme. On demontre que l'arrêt est décidable, et qu'il existe une procédure effective pour transformer une machine de Matiyasevich en automate fini. -- Marc Daumas - www.ens-lyon.fr/~daumas LIP - ENS Lyon - 46, allee d'Italie - 69364 Lyon Cedex 07 - FRANCE Ph : (+33) 4 72 72 82 29 - Fx : (+33) 4 72 72 80 80