La machine de Turing, une révolution des mathématiques et de l'informatique - Passe-science #11
Вставка
- Опубліковано 10 вер 2024
- Qu'est ce qu'un calcul? Qu'est ce qu'un programme? Sous quelles conditions et par quel miracle une machine purement conditionnelle devient elle programmable? c'est ce qu'on va tenter de comprendre dans cet épisode!
Liens pour en savoir plus:
fr.wikipedia.o...
fr.wikipedia.o...
fr.wikipedia.o...
Liens des vidéos:
Reportage sur la machine d'Anticythere (introduction):
• Video
Machine de Turing universelle en lego ENS Lyon:
• The Turing Machine Com...
Machine de Turing universelle en jeu de la vie de Conway:
• Game of Life - Univers...
Machine de Turing universelle en Minecraft:
• Universal Turing Machi...
Musique:
www.musicscree...
www.jamendo.co...
Retrouvez Passe-science sur Tipeee, Twitter et Facebook:
www.tipeee.com...
/ thomascabaret84
/ passescience.youtube
D'autres details sur la machine de Turing et un angle de presentation different et plus "simple" sont disponibles dans la premiere partie de cette video: ua-cam.com/video/OGeOQzGq4LE/v-deo.html
Merci pour cette vidéo, c'est tellement intéressant !
Super vidéo :-), elle a abordée la question de manière courte et avec le bon formalisme, cela permet de comprendre l'apport énorme d'e la machine de Turing. Merci
Wouaw !! Quelques centaines d'abonnés en quelques heures...Merci +ScienceEtonnante !! :-p
Mais tu le mérites, c'est assez complet :)
Pas à la portée de tout le monde en une seule lecture, mais tu parles de la machine universelle que je n'ai pas osé aborder en une seule vidéo avec les algorithmes ^^
Bravo ! Et bonne continuation :-)
+Basic Dev Merci oui x3 en abonnés sur qq heures!
Très bien expliqué ! pas donné à tout le monde mais je pense que c'est le but de ta chaîne. En tout cas bravo, ça m'a rappelé mes premiers essais de codage de machin de Turing en Python xD
Vidéo intéressante.
Merci, j'invite à voir le début de la vidéo sur "la machine de Turing en cartes Magic" ua-cam.com/video/OGeOQzGq4LE/v-deo.html la fin est beaucoup plus geek (et du coup c'est selon les gouts) mais la premiere partie presente egalement la machine de Turing d'une autre manière que dans cette ancienne vidéo (et je préfère la nouvelle approche).
J’ai mal à la tête, je croit que j’ai pas encore le niveau la, mais c’était assez intéressant merci
Hello, avec le recul celle ci j'aurais presenté autrement. Je resume ce qu'il faut comprendre vite fait:
1) une machine de turing c'est une machine, un automate, abstrait. (tu devrais pouvoir extraire de la video la liste des choses qu'il faut pour decrire une de ces machine et s'avoir la faire tourner.)
2) "a chaque calcul sa machine de turing". Ca c'est un truc puissant c'est que qq soit le calcul au sens large que tu envisage, que ca soit ajouter 2 nombres, calculer le symetrique d'un point par rapport a une droite, ou remplacer tous les "a" d'un texte par "bob" (c'est un calcul aussi), alors il sera possible de construire une machine de turing qui effectue ce calcul. De prime abord cette declaration n'est pas du tout evidente car ca semble pas facile a construire une machine de turing, on voit mal comment decider de son alphabet et de ses transitions pour que ca fasse ce qu'on veut, mais si on cherche un peu on se rend vite compte que tout calcul se decompose en etapes, et que les etapes on peut les faire correspondre a des "etats" de la machine de turing. On remarque aussi que si on veut mettre un repere sur la bande (sur la memoire) on peut le faire en ajoutant des symboles, par exemple si on a que 2 symboles dans notre machine disons 0 et 1 et qu'on aimerait pouvoir mettre un repere "*" sur une case sans perdre ce qui est ecrit dessus, ba il suffit de dire que les symboles 0* et 1* sont 2 nouveau symboles connus de notre machine. En resume, si on fouille un peu, on se rend compte que c'est assez facile de construire une machine de turing pour un calcul donné qq soit le calcul. (a la limite on peut l'admettre, "a chaque calcul sa machine de turing")
3) le probleme a ce stade cest que si on change de calcul ba faut changer de machine! avoir un alphabet different, une table de transition differente etc... mais ya une astuce.
4) en fait l'astuce consiste a remarquer que "faire tourner une machine de turing donnee" est un calcul comme un autre, autant que "ajouter 2 nombres donnés" est un calcul. Et comme "a chaque calcul sa machine de turing" alors il existe necessairement une machine de turing, qui sera capable si on lui decrit une autre machine de turing de notre choix, de faire la calcul qui revient à simuler son comportement. On dit qu'on a ainsi une machine de turing universelle.
5) et du coup on peut utiliser cette machine de turing universelle pour realiser n'importe quelle calcul, en la faisant simuler la machine de turing correspondant au calcul qu'on veut faire. faire ceci, c'est "programmer" notre machine de turing universelle, qui maintenant n'a plus besoin de changer en table de transition, seul ce qu'on va mettre sur la bande initiale changera.
Voila c'etait pour t'achever au cas ou tu aurais encore un morceau de tete :P
Passe-Science merci beaucoup pour ces précisions!
Franchement merci, Superbe vidéo, super résumé. Mes professeurs ont oublié de m'enseigner ce sujet. il me manque le support de cours (de ta vidéo) afin de pouvoir l'apprendre correctement.
Je me souviens qu'à l'époque où j'étudiais ça, j'avais fini par réfléchir façon machine de Turing ^^ Heureusement, je ne bosse plus dessus. Mais c'est assez intéressant comme concept.
C'est clair, complet .. Parfait !!
Bonjour,
Je n’ai pas compris comment fonctionnait la machine, j’ai fait pause mais ça manque d’explications.
Ok c’est bon j’ai compris, il n’y a plus à tenir compte d’une « tete de lecture » alors que c’est la base ?
Antonino Chimenti Hello, le detail de fonctionnement d'une machine de turing en general est à 0:40. C'est ce passage qui te pose problème ou un autre?
j'ai du mal à comprendre comment ce mécanisme permet d'effectuer un calcul... :-/
qu'est ce qu'on met en entrée et à qui va ressembler la réponse à un calcul comme 1+3 par exemple?
Hello, alors ce qu'il faut comprendre c'est > . C'est à dire que dans ton exemple, le calcul 3+1 (plus généralement ajouter 2 nombres entier donc) pour le faire tu peux construire une machine de Turing en décidant des symboles (la taille de la liste de symboles différents), de la liste des états de ta machine et de sa table de transition. Tu décides également d'une convention pour représenter tes entrées sur la bande, par exemple en binaire si tu veux (mais tu peux très bien décider d'avoir les 10 symboles de chiffre usuel, c'est juste que ca va probablement faire plus de cas différents à traiter) et tu peux séparer tes deux chiffres par un caractère spécial, pourquoi pas "+". Apres il s'agit de trouver ta table de transition. La tu va me dire "c'est super dur" de trouver cette table. Alors oui et non, car si tu es capable de décomposer ce que tu fais lors de l’opération tu verras assez vite que tu va identifier des étapes comme ajouter un chiffre à un autre, calculer une retenu, passer sur le chiffre suivant etc... et en pratique il est assez facile de faire correspondre les étapes à des états de ta machine. Si tu veux pouvoir retrouver un endroit sur la bande pour y revenir en suite, tu peux très bien décider d'un symbole spécial à ajouter à ton langage. Au bilan avec toutes ses libertés sur la liste de symboles, la liste d’états et la table de transition, on arrive en pratique très bien à faire correspondre une machine de Turing à chaque calcul. Apres vient le point dingue
Ce qui est surtout intéressant, c'est que Turing a démontré que ce modèle permet à lui seul de « tout faire », par rapport à d'autres machines abstraites plus simples comme les automates d'état finis. Voir notamment à ce sujet la Hiérarchie de Chomsky qui les adapte à l'interprétation des langages (et qui, couplée aux travaux de Kleene, nous a donné entre autres les expressions régulières). Et c'est pour cela que ce modèle sert de base aux machines « réelles » que sont nos ordinateurs.
Pour additionner 1 et 3 à présent, il y de nombreuses approches possibles. La plus simple consiste à représenter tes deux nombres chacun comme une suite de points, donc ici « . » et « ... », suivies par un espace. Chaque point et chaque espace occupant consécutivement une case sur la bande. Il te suffit alors de déplacer la bande vers la droite jusqu'à rencontrer le premier espace puis à nouveau vers la droite jusqu'à rencontrer le deuxième espace, remonter d'une case vers la gauche, remplacer le point qui s'y trouve par un espace, remonter à gauche jusqu'à retrouver l'espace intermédiaire et le remplacer par un point. Et voila : tu as bien UNE chaîne de QUATRE points consécutifs et ton addition est remplie.
Si tu veux faire ça de manière plus évoluée, en utilisant un symbole par chiffre et en comptant en base 10, alors soit tu écris tous les chiffres dans l'ordre « 0 1 2 3 4 5 6 7 8 9 » une fois sur la bande et tu te sers de leur position pour établir une relation d'ordre, soit tu établis à la base une liste d'états qui, pour chaque combinaison de deux chiffres, te donne la valeur du chiffre à poser (de 0 à 9) et celle de la retenue (0 et 1). Il te faut donc 100 états au minimum mais une fois définis, ils suffisent ensuite à répéter l'opération pour tous les chiffres. Et au passage, c'est EXACTEMENT pour cette raison que l'on nous fait apprendre les tables de multiplications au primaire.
C'est aussi une des nombreuses raisons pour lesquelles on utilise le binaire en informatique : là où il te faut 100 états en décimal, tu n'as besoin que de 4 états en binaire pour faire la même chose.
Aurais tu un exemple de machine de turing très simple? Par exemple qui additionne des nombres ou qqch du genre
Sinon très bonne vidéo et bonne continuation
Hello, merci! En dehors de l'exemple de machine de Turing qui compte en binaire dans la vidéo, je n'ai pas d'exemple simple sous la main. Mais ce qui est important c'est de comprendre comment on peut en construire une pour un calcul donné, comme tu le dis par exemple additionner deux nombres. Tu dois juste choisir comment tu comptes les écrire au départ sur la bande et comment tu comptes voir le resultat à la fin. Ensuite il s'agit de simplement decomposer ce que tu fais en etapes et faire correspondre ces etapes à des etat de la "tete de lecture", si tu as besoin de "reperer" des endroits sur la bande pour y revenir ensuite, ca peut se faire facilement en ajoutant un type de caractere parmis ceux disponibles si tu vois ce que je veux dire. C'est parfois assez long, ca peut prendre plus ou moins de caracteres et d'etats mais ca aboutira toujours à te donner la machine qui fait la tache que tu lui destines. N'hesite pas à poser des questions un peu technique si tu tentes d'en construire une et que tu ne vois pas comment modeliser une etapes.
Ok merci c'est plus clair!
merci
De rien, sur la machine de Turing j'invite à voir tout le premier chapitre de cette vidéo ou j'en parle un peu differemment: ua-cam.com/video/OGeOQzGq4LE/v-deo.html
La seconde partie de la vidéo est geek et loufoque donc ce n'est pas pour tout le monde ^^ mais les 9 premières minutes sont un bon complément sur la machine de Turing.
Salut T. Je trouve ta vidéo Parfaite !: :P (y) Merci :)
Merci Didier :)
ÂÏ nouvelle machine de TURING !!
Et du coup on peut même demander à une machine universelle de simuler... une machine universelle? C'est assez mindfuck!
Oui biensur! et oui c'est assez mindfuck! l'idee meme que certaines de ses machines aient le pouvoir de simuler toutes les autres dont elle meme est assez mindfuck, et c'est précisement le point de génie de l'idee de Turing!
Excellente vidéo ! Merci beaucoup
Comment fonctionner la machine de Turing
Bonjour, "Fonctionne" c'est-à-dire ? La machine de Turing est un modèle abstrait, ce qu'on appelle un automate, c'est-à-dire une machine abstraite qui aurait le comportement décrit dans la vidéo. Vous demandez comment réaliser physiquement une machine de Turing? eh bien comme vous voulez du moment que ca respecte ce que son comportement abstrait décrit. Ça peut se faire via un circuit imprimé mais on peut aussi s'amuser à en faire des réalisations pneumatiques en lego:ua-cam.com/video/KrNTmOSVW-U/v-deo.html
ou même mécanique en bois:ua-cam.com/video/vo8izCKHiF0/v-deo.html
J'invite a voir la première moitié de mon autre vidéo sur la machine de Turing, car le début la présente sous un autre angle (la seconde partie de la vidéo est très geek mais totalement facultative):ua-cam.com/video/OGeOQzGq4LE/v-deo.html
Les machine de turing ne son pas compliquer a comprendre et a comprendre comment elle marche aujourd'hui(si vous vouler savoir une seule opération peut pérmetre de fair tous (Nand) pour comprendre plus moi je conseil un jeux steam nommé turing complete)
Bonne vidéo mais quelques exemples expliqués aurait été les bienvenus... pas évident de tout saisir du premier coup...
Je découvre tout cela sur le tard, et merci de savoir nous faire aimer la science : 35 ans plus tôt, ce n'est pas un bac Littéraire que j'aurais passé :-D
mon cerveau a disjoncté a 5 sec
A ça va je suis pas le seul à rien comprendre a ses vidéos merci Patrick
Vidéo très intéressante ! Mais manque d'exemples concrets ... Car même après avoir regarder la vidéo je ne sais toujours pas comment l'utilisé pour un calcul. Admettons 50 divisé par 7 , comment faire le lien avec la machine de turing pour résoudre sa calcul ?
+Djtomjak73 Oui je n'ai pas mis d'exemples concrets de ce genre parce que c'est très difficile à faire tenir en peu de place! Le seul que j'ai trouvé c'est la machine qui compte en binaire a 2:10. Je te donne quelques éléments de la recette:
Pour faire une machine de Turing qui réalise une opération de ton choix, il suffit de faire comme à l’école primaire c'est a dire de décomposer ton calcul en états et étapes (comme lorsqu'on pose une addition), et de légèrement les bidouiller ou les raffiner pour avoir des états étapes et transition façon "machine de Turing". Ça te donnera une machine de Turing qui sait faire ton calcul mais qui ne sait faire que lui. Mais lorsque tu as cette machine de Turing tu peux la coder dans une machine de Turing universelle qui va en simuler le comportement, c'est l’étape de programmation. Pour faire l’intégralité de ceci ça te prendra certainement des pages entières :) même pour une addition.
La seconde raison pour laquelle je n'ai pas donné ce genre d'exemple c'est que la machine de Turing est un modèle minimal abstrait et mathématique pour étudier le calcul en général, un ordinateur moderne ne suit pas cette organisation minimale, par exemple il n'a pas une bande de mémoire dans laquelle il doit se déplacer de manière continue, il peut accéder à une adresse mémoire particulière, ce qui rend la programmation bien plus simple.
Merci pour cette réponse rapide ! D'accord je comprend mieux, a chaque calcul sa machine de turing, je vais essayer de trouver des exemples sur internet juste par curiosité ;)
+David Théodoros Merci. Il n'est pas impossible que certain mécanisme biochimique sur des molécules chainées soient des machines de Turing très simple. Pour le jeu de la vie on parle d'automate cellulaire, une famille en quelque sorte plus générale. La famille machine de Turing était la famille la plus simple qui contient certains éléments (ie certaines machines de Turing, celles dites universelles) capables de simuler tout autre calcul ou automate.
+Djtomjak73 Avant de faire 50/7, fait une machine pour 1+1, ce sera déjà un début ;)
+David Théodoros C'est normal, le travail de Turing est loin d’être évident (d'ailleurs beaucoup de gens ne comprenaient pas la portée de ses travaux à son époque). En gros tu peux retenir que:
1) A chaque calcul sa machine de Turing (c'est à dire que si tu penses à un "calcul" tu pourrais construire une machine de Turing pour le faire et ce n'est pas si dur.)
2) Les machines de Turing ont des différences en terme de pouvoir, certaines peuvent faire des calculs que les autres ne peuvent pas faire.
3) Certaines machines de Turing ont le pouvoir de simuler n'importe quel autres machines de Turing (et donc comme à chaque calcul sa machine, elles ont le pouvoir absolu de faire n'importe quel calcul).
C'est ce point 3 qui fait du modèle d'automate, qu'est la machine de Turing, un modèle exceptionnelle, car il pose les bases formelles pour définir la notion de calcul, et de la notion d'algorithme c'est à dire comment s'y prendre avec une machine de Turing universelle pour faire un calcul donné.
Bon je vais jeter mon ordinateur par la fenêtre et à partir de maintenant j'irais sur internet avec une machine de Turing. Quelqu'un sait où on peut acheter une tête de lecture et des TRÈS long ruban ? Blague à part super vidéo pouce bleu :)
Tu peux la faire en lego :) voir lien dans les commentaires :P
Dans ma fac de maths lors de la fête de la science j'ai eu l'occasion de voir une "petit" machine de Turing en Lego à qui on donnait un ruban avec plusieurs levier et elle l'inversait symétriquement. C'était beau O.O
OK je viens de passer 30min a essayer de comprendre Les 2 premieres min mais ca vaux le coup, tu aurais quand meme pu expliquer Les etapes juste pour aider a comprendre mais peut etre voulais tu nous faire comprendre par nous meme :p au final tu expliques que c'est binaire car ca cetait introuvable tu es un tres bon pedagogue dur mais efficace :)
Hello, c’était quels points précisément que tu ne comprenais pas initialement et que tu as compris par toi même? (je suis curieux c'est pour améliorer ma méthode de pédagogie)
@@PasseScience a 1:47 "vous vous déplacez à droite" mais tu ne dis pas "car le symbole est à droite de la case de couleur" et ensuite tu présente l'exemple et tu dis vous pouvez mettre en pause pour comprendre comment ça marche (2min) mais il aurait été plus simple que tu nous fasse directement les exemples genre on commence par symbole et case noir donc ont lis sur la table la suite puis on applique on va sur le côté etc en nous montrant ça permet de comprendre comment tu fais
Ha oui en effet. C’était sans doute lié au temps nécessaire pour faire l'animation (je procède de manière tellement inefficace pour faire des animations) mais oui ça aurait été plus beau en voyant l'animation! :) C'est un peu tard mais tu peux t'amuser avec différent simulateur en ligne, notamment celui ci: turingmachine.io/ (Tu as des exemples et comment définir ta machine de Turing en texte, puis la simuler) Un autre ici: math.hws.edu/eck/js/turing-machine/TM.html
@@PasseScience merci :)
Tout d'abord, je m'excuse de relancer une discussion sur une vidéo datant de trois ans, qui ne tente rien n'a rien.
Je suis lycéen et me créer un compte exceptionnellement pour commenter vos vidéos.
Celle-ci est particulièrement intéressante, mais je n'ai pas compté sur mon fort niveau d'ignorance pour la comprendre entièrement. Finalement, j'ai bien compris tout le contenu de la vidéo, à l'exception d'un détail sur l'explication du fonctionnement d'une machine de Turing universelle à 6:05, pourquoi le système n'inscrit pas en mémoire l'état courant de l'emplacement ?
Hello, il faut toujours tenter, et 3 ans ce n'est rien, le savoir périme parfois oui mais pas si vite et heureusement :) Pour ta question: peux tu être plus precis sur ce que tu veux dire par "en mémoire" (car toute la bande est la mémoire et je l'ai découpé en 4 zones, tu parles d'une zone en particulier?) et que désignes tu par "l’état courant de l'emplacement" ? tu parles de la position de la tête de lecture de la machine simulée par notre machine universelle?
Je vais tenter d'expliquer ce que j'ai compris, puis ce que je n'ai pas compris, peut-être ainsi pourriez-vous m'aiguiller.
L'ensemble de la bande est composé de trois partie : une pour stocker la table de transition, une réservée au segment de travail (ce que j'appelle très vulgairement mémoire), et tout le reste pour y faire figurer dans chaque case (emplacement) une valeur et éventuellement un état.
La machine contient d'abord des valeurs initiales. Elle cherche à les retrouver au sein de la table de transition, une fois fait, elle exécute les instructions analogues. les nouvelles valeurs sont également ainsi accompagnées d'un état. La phase de lecture lis les nouvelles valeurs puis les inscrits dans le segment de travail. Je n'ai pas compris pourquoi cette phase de lecture n'inscrit pas également l'état des valeurs dans le segment de travail, puisque celle-ci sont prise en compte dans la table de transition.
Je repose quelques éléments de contexte (que tu as sans doute déjà compris mais ça permettra d’être plus clair). Une machine de Turing c'est une bande de case, sur laquelle se déplace une tête de lecture qui lit, écrit, mémorise une info qu'on nomme l’état, et se déplace en fonction des règles qu'on lui donne au travers d'une table de transition. Une table de transition c'est très simple ça dit: quoi écrire, ou se déplacer, dans quel état passer, en fonction de l’état courant et de ce qu'on lit. Jusque la pas trop de problème j'imagine. Ce qu'on fait dans ce passage de la vidéo, (autour de 5:00) c'est construire une machine de Turing Universelle, c'est a dire une machine de Turing dont le fonctionnement effectue une tache précise: simuler une autre machine du Turing quelconque qu'on lui décrit initialement. C'est à dire que notre machine de Turing Universelle a "physiquement" une bande, une tete de lecture et une table de transition. Et la machine de Turing dont elle est en train de simuler le fonctionnement à elle aussi ces ingrédients mais, comme on est en train de la simuler, ils sont représenté de manière abstraite sur la bande de notre machine de Turing Universelle. C'est à dire que si tu suis bien, l’étape dont je parle à 5:42 par exemple, ou notre machine de Turing Universelle recopie des informations de la partie jaune à la partie verte, est en fait constitue d'un grand nombre d'aller retour de la tete de lecture de cette machine de Turing universelle et de potentiellement beaucoup de lecture/écriture et changement d’état pour y arriver selon sa table de transition à elle (qui n'a rien a voir avec la table de transition de la machine de turing qu'elle est en train de simuler, representee en jaune sur sa bande). Tout ce que je viens de dire doit être clair ou sinon c'est qu'il y avait avant ta question, un autre truc à comprendre. En ce qui concerne ta question: lorsque notre machine de Turing Universelle va lire la transition qu'elle doit simuler (de la machine de Turing qu'elle est en train de simuler) elle recopie tout ce qu'elle doit savoir: ce que cette transition simulée lui dicte d’écrire, ce qu'elle lui dicte également pour l’écriture et le changement d’état de notre machine simulée. Est ce que ça a éclaircit la chose? sinon ou se trouve précisément ton problème avec ces termes?
Je m'apprêtais à envoyer cette réponse :
__________________________________
« elle recopie tout ce qu'elle doit savoir: ce que cette transition simulée lui dicte d’écrire, ce qu'elle lui dicte également pour l’écriture et le changement d’état de notre machine simulée », tout cela afin que la machine de Turing universelle puisse recommencer un cycle. Après cette étape, le segment de travail retient ce que la machine simulée vient de lire, exactement comme à l'initialisation. Il me semble ainsi avoir bien compris l'intérêt de cette dernière étape.
Or, à 6:05, dans le schéma qui image ce discours, la machine transmet bien la valeur de la case en lecture, mais pas son état ... pourtant d'après le passage citée ci-dessus, il transmet effectivement l'état de la case. S'agit-il d'un oubli lors de l'édition des images de la vidéos, ou alors la machine ne retient jamais l'état des cases en lecture ?
__________________________________
Lorsque soudain j'ai compris : l'état de la machine (1, 2 ou 3) est "absolue", chaque case ne contient pas à la fois une valeur (A, B ou C) et un état. Les cases contiennent des valeurs, et la machine est dans un état, qui est évidemment inchangé lorsque la tête de lecture transmet ce qu'elle lit au segment de travail. Peut-être ai-je ironiquement encore mal interprété ce qu'il faut comprendre, mais je ne pense pas puisque j'arrive à suivre tout les détails en revisionnant cette vidéo sans problèmes.
Merci pour l'attention que vous portez sur les commentaires de vos vidéos.
Voila tout à fait, l’état est associé à la machine tout entière, ie une machine de Turing a bien un seul état à un instant donné et cet état varie au cours du temps parmi un ensemble d’état possibles qui fait partie de la définition de la machine. Dans le passage autour de 5:00 la machine de Turing Universelle a bien un etat propre à tout instant (qu'on ne represente pas sur le schema et qui change potentiellement plein de fois à chaque macro-etapes decrites) et la machine de Turing qui est en train d'etre simulée par notre machine universelle, a elle aussi un état unique, qui est toujours stocké dans le segment de travail de la machine universelle.
Voici la machine de Turing que j'ai conçu : ua-cam.com/video/-je1LUJcT_E/v-deo.html
Pour le plaisir des yeux, voici un modèle en bois entièrement mécanique: ua-cam.com/video/vo8izCKHiF0/v-deo.html
@@PasseScience J'avais déjà vu et oui, c'est magnifique ! J'espère que vous aimerez ma version 😉
J'adore le travail que tu fais. Mais en fonction des commentaires, je suis moi aussi assez mièvre et décontenancé. J'ai beau revoir la vidéo, je ne comprends pas très bien ce que cette machine fait ou devrait faire, ni comment.
Je suis aussi informaticien et automaticien. J'essai de me raccrocher au fonctionnement d'un très simple processeur. Etat initial, unité de lecture du code action (micro code) ou des données. Registre de calcul et registre de stockage temporaire de l'information.
La table des transitions correspond-t-elle à une série de tableaux de Karnaugh ?
Nous sommes sur une machine donc la logique binaire doit s'y appliquer. Je comprend bien que cet automate est séquentiel (et sériel) et que les différentes positions de la tête de lecture sur le ruban représente une forme de mémoire stockant différents états du calcul. Je ne comprend pas sa capacité de généralisation. J'en suis navré. Ici, pour l'application, il me manque une pièce maîtresse du discernement, de la logique. Notre humanité est faite de cerveaux différents, différemment câblés. Je crains malheureusement ne pas faire partie de celle des Turing. Mais ce n'est rien. C'est a moi de m'adapter.
Hello, avant de parler de ce que tu n'as pas compris je vais faire le point sur ce que je pense que tu as compris:) 1) "Machine de Turing" c'est juste une famille d'automates tous bâtis selon le même modèle: avec une table de transition un ruban de symbole etc...2) Si je te donne une machine de Turing particulière c'est à dire son alphabet de symboles, son ruban initial, ses états possibles, et sa table de transition, tu sais la faire fonctionner. (en appliquant bêtement la mécanique dans la vidéo). Ne tente pas de te rapprocher du fonctionnement d'un processeur ou autre, car la machine de Turing est un modèle minimal et pas forcement le plus intuitif. Alors en quoi cette famille d'automates, ie les machines de Turing, a t elle un pouvoir généralisant de la notion de calcul? La réponse: à chaque calcul sa machine de Turing. Pour comprendre cela imagine que ton exercice soit de construire une machine de Turing qui ajouterait deux nombres. tu vas d'abord décider de ou les écrire sur le ruban, de comment les placer, éventuellement les séparer par un caractère spécial, tu peux si tu le souhaites même les écrire en base 10, ça ne pose pas de probleme c'est un alphabet comme un autre. Ensuite ce qu'il faut remarquer c'est que tout calcul se décompose facilement en étapes. par exemple ici pour ajouter on sait qu'on devra regarder les unités de chaque nombre, écrire quelque part un résultat, écrire éventuellement qq part une retenu etc.. Une fois que toute ses étapes seront bien identifiées elles vont en fait correspondre aux états de ta machine de Turing. L’état de la machine ça représente la mémoire de l’étape que la machine est en train d'accomplir. Ensuite en pratique tu va te rendre compte que tu auras envie de mémoriser des emplacement, tu aimerais pouvoir marquer des endroits de la bande en disant "c'est la que j'en étais". Ce qu'il faut voir c'est que marquer des endroits de la bande c'est en fait ajouter des symboles: transformer un "0" en un "0*" c'est ajouter un nouveau symbole. Donc tout ceci étant dit, en théorie, tu devrais sentir que quelque soit la tache à faire, si tu n'es pas limité sur le nombre d'etats et pas non plus limité sur le nombre de symboles, tu peux, pour un calcul donné, construire une machine de Turing qui le réalise.
Par exemple un exercice plus faisable que l'addition: faire une machine de Turing qui étant donné un motif du genre #0110101111# le retourne symétriquement c'est a dire produit #1111010110# avec le droit à autant de symboles supplémentaires que tu veux et autant d’état que tu veux c'est très faisable, c'est à tenter.
Ensuite la ou les choses deviennent plus dures, et la ou se trouve le génie de Turing, c'est qu'il a remarqué que certaines machines de Turing particulières ont le pouvoir de simuler n'importe quelle autre machine de Turing. C'est a dire que la ou avant tu devais pour chaque calcul changer la table de transition et l'alphabet de symbole tu peux avec un bon alphabet et table de transition (ceux d'une machine de Turing universelle) simuler le fonctionnement de n'importe quel autre machine de Turing (et donc de celle correspondant au calcul que tu veux faire). Mais l’étape qui consiste a remplir la bande de la machine de Turing universelle est technique, car il faut exprimer la machine de Turing qu'on désire simuler sous une forme qu'elle comprend, c'est ce qu'on appelle "programmer" une machine de Turing universelle. (voir vidéo pour l'allure d'une machine de Turing universelle)
Voila voila :)
Merci beaucoup pour ce supplément d'info, très gentil. C'est plus clair . Je crois que pour bien comprendre ces automates, il faut passer à la pratique. Donc, si je veux simuler une de ces machines il me faut :
Un tableau uni dimensionnel (un ruban inscriptible) qui comprend, un alphabet (des constantes), des règles de transition (code action, opération ou changement d'état) qui en font un état initialisé de l'automate. Définition de symboles spéciaux, les séparateurs, repères sur le ruban.
Mise en marche : un ordre de déplacement de la tête de lecture vers un symbole précis : lecture. Le compteur d'itération (pointeur d'instruction ou d'état) sera un changement de symbole (une surcharge) de la valeur lue.
En gros, je recherche un opérande (premier symbole de l'alphabet donné) puis un opérateur notifié lui aussi pour la séquence (et l'opérande suivant) et je stocke le résultat de l'opération qql part sur la bande : Itération sur l'opérande suivant jusqu'à séparateur de fin de donnée. A partir de là je peux reprendre le résultat comme données (opérande) et lui faire subir un autre opérateur pour un autre résultat et ainsi de suite. Je suis face à un ordinateur. ;-)
Oui, si je suis bien ici tu décris plus qu'une machine de Turing, tu décris une machine de Turing universelle et également comment celle si a le pouvoir en pratique d’être programmable. C'est ce ce que je décris au moment complexe de la vidéo a partir de 4:50. En pratique concevoir une MTU demande beaucoup de symbole et d’états, (ça reste facilement constructible lorsqu'on a le plan mais il faut y passer des heures). Ce dont il faut vraiment se convaincre c'est que:
-Si on nous demande de retourner un motif, on saura facilement trouver un moyen de l’écrire sur une bande et de construire une MT qui le retourne. (mais une MT qui ne fait que ca)
-Si on nous demande d'additionner deux nombres, on saura facilement trouver un moyen de les écrire sur une bande et de construire une MT qui les ajoute. (mais une MT qui ne fait que cela).
Et de la même manière:
-Si on nous demande de simuler une MT donnée, alors on saura aussi trouver un moyen de la décrire sur une bande et de construire une MT qui en simule l’exécution. Cette MT ne sait faire que cela (en simuler une autre) mais du coup elle sait tout faire car on pourrait lui demander de simuler notre MT qui ajoute 2 nombre, ou notre MT qui retourne un motif. elle devient MTU, et face à cette MTU tu es donc face à un ordinateur, changer uniquement son input la bande te permet de simuler n'importe quel calcul.
j'ai rien compris
+chiminig chiminang Si tu as une question précise je peux tenter d'y répondre.
Normalement jusqu’à 2:20 ça doit être abordable après il faut se concentrer mais je peux aider :)
Je connais également les machines de Turing et j'avoue que tes explications sont très confus.
Pour être plus précis, les diagrammes de transitions sont pas clairs.
Même en faisant pause c'était difficile à déchiffrer.
bon j'aime quand même ce que tu fais
Continue comme çà
Malheureusement c'est le genre de domaine ou je pense que quelque soit
la manière de le présenter un effort de l'auditoire est nécessaire. (sauf en restant a un niveau superficiel de vulgarisation) J'attend clairement que le spectateur fasse pause dans celle ci. Mais je serais curieux de savoir quel diagramme precisement tu ne trouve pas clair? (a quel moment de la vidéo)
+Passe-Science je parle de la representation graphique que tu donnes en 1:31.
C'est bete mais j'ai eu du mal a comprendre comment etait défini les transitions.
Notamment le deplacement a gauche et a droite ainsi que le nombre d'états.
A mon sens, mais peut etre que je me trompe, une machine a 2 états avec les 4 transitions que tu décris aurait été plus claire.
Oui on est moins habitué à cette représentation graphique, c'est celle de wolfram:
mathworld.wolfram.com/TuringMachine.html
C’était aussi pour être pédagogique et montrer une autre manière de le noter que ce que je fais avec un tableau à 1:13. Je le détaille avec une phrase un peu après à 1:40, après on aime ou on aime pas cette notation :) personnellement j'ai toujours aimé cette représentation graphique parce qu'elle représente le motif que fait ta machine lorsqu'on la dessine dans le temps ligne par ligne. Par exemple tu peux voir a 1:54 le rapport qu'il y a entre les ligne 1-2 et le motif de transition utilisé. Ça peut paraître paradoxal mais c'est typiquement le genre de notation que des enfants comprendront plus rapidement que la notation formelle tableau (la ou nous, adultes, on aime bien les représentations formelles) Oui des enfants peuvent jouer à exécuter des machines de turing :P haha
0:42 ; 2:20
J'invite aussi à voir le debut de cette video plus récente: ua-cam.com/video/OGeOQzGq4LE/v-deo.html
La premiere partie fait un recap sur la machine de Turing d'une maniere complementaire à l'ancienne video ici.
Hou la la la... C'est à n'y rien comprendre...
Et je suis informaticien et je connaissais la machine de Turing... ^^
La, il faut que tu sois lucide : c'est incompréhensible pour la majorité des gens à partir du moment où tu aborde la version universelle...
La vidéo commençait mal : "Un objet conditionnel"... Je comprends, mais c'est très mal formulé, et aucune explication....
Tu veux trop démontrer, prouver (un travers, une déformation professionnelle de mathématicien je pense), mais ce qui intéresse les gens c'est d'apprendre quelque chose qui soit accessible, de comprendre, et d'être étonné.
Pense y ! ;)
+Régis Voiclair je pense que tu n'as pas compris le but de ces videos. Il ne s'agit pas de faire de la simple vulgarisation; de nombreuses chaines, notament en anglais, font déjà ça très bien. Le but est ici d'aller dans les details, de ne pas seulement dire "c'est comme ça et c'est génial" mais plutot d'expliquer ce qu'il y a de génial dans le sujet présenté. Oui cela implique de rentrer vraiment dedans, d'approfondir d'avantage, et oui cela necessite plus d'efforts et eventuellement de connaissances initiales.
Tu commentes depuis un moment les vidéos de Passe-Science de la même manière : "Cela ne convient pas 'aux gens' " mais tu te trompes sur le public visé. Certes certains points pourraient parfois être plus clair, mais si tu changeais un peu de point de vue, tu les apprécierais bien d'avantage.
Si tu es vraiment informaticien, je doute que même la seconde partie te pose problème. Pour une démarche plus vulgarisatrice, je te recommande la chaine d'e-penser, que tu connais probablement déjà :)
+Xavier Villoing : la seconde partie ne me pose pas de problème, c'est seulement son caractère didactique et pédagogique que je remet en cause... ^^
Passe-Science n'a pas pour vocation, comme tu semble le dire, de devenir une chaîne de spécialistes, ou de matheux, certaines vidéos antérieures bien plus simples le prouvant.
Maintenant, le créateur de cette chaîne est libre de choisir sa politique éditoriale... Mais je trouve que c'est dommage qu'une personne aussi savante que lui fasse des vidéos aussi difficiles pour le grand public. ;)
+Régis Voiclair Doit-on critiquer un prof de prepa parce que ce qu'il explique ne peut pas être compris par des collégiens ? Ce n'est pas parce que ces vidéos ne sont pas destinées au grand public qu'elles s'adressent aux experts (et inversement). Entre les deux extrêmes se trouve un grand nombre de gens, dont nous faisons partie semble-t-il, qui disposent de la curiosité et des connaissances nécessaires pour approfondir des sujets qui, bien qu'ils leurs soient familier, recèlent encore des secrets. Ce besoin est parfaitement rempli par cette vidéo, qui au passage est loin de faire partie des vidéos les plus complexes de la chaîne.
Je suis désolé, mais la vitesse d'élocution et le ton monotone font que j'ai du mal à saisir ce qui est dit dans la vidéo. Et au final je suis perdue. Et peu importe si cette vidéo s'adresse à un public confirmé ou pas, j'avais envie de comprendre! Même les schémas et les diagrams sont compliqués et non instinctif, je vais mettre un like et m'abonner pour encourager dans tout les cas. Il vaut mieux vulgariser puis rentrer dans ta technicité petit à petit en prenant son temps, c'est important pour le public. Les ignorants que vous saurez eclairer aujourd'hui vous dirons merci demain et vous apprendrons peut quelque chose un jour à leur tour ;)
j'ai rien compris tu sais pas expliquer frr
Dans les 8 premieres minutes de cette autre video: ua-cam.com/video/OGeOQzGq4LE/v-deo.html je le présente d'une autre manière (la suite de la video devenant très geek). Ca reste complexe mais je préfère l'approche de la video plus récente.
_J'ai rien compris_
Hello, vous pouvez tenter la première moitié de cette autre vidéo, j'en reparle différemment. ua-cam.com/video/OGeOQzGq4LE/v-deo.html
Entre 0:30 et 8:20 (après c'est autre chose mais ces 8 minutes retraitent de la Machine de Turing)