Turing Machines Explained
The video could not be loaded here. Watch on YouTube and follow the transcript below.
[EL CAPITAN Voici El Capitan, le super calculateur le plus puissant du monde.
[CAPTAIN Here is El Capitan, the most powerful supercomputer in the world.
Transcript
[EL CAPITAN Voici El Capitan, le super calculateur le plus puissant du monde.
[CAPTAIN Here is El Capitan, the most powerful supercomputer in the world.
Il est principalement utilisé pour le programme d’armement nucléaire américain,
It's mainly used for the US nuclear weapons program,
et il a la capacité d’effectuer 1 milliard de milliards d’opérations par seconde. Tout ça avec
and it can perform 1 billion billion operations per second. All that with
une consommation électrique de 35MW quand même, et pour la modique somme de 600 millions de dollars.]
a power consumption of 35MW mind you, and for the modest sum of $600 million.]
Et pourtant, en un certain sens, ce super calculateur, El Capitan,
And yet, in a certain sense, this supercomputer, El Capitan,
n’est pas fondamentalement différent de l’appareil sur lequel vous êtes
is not fundamentally different from the device you're
en train de regarder cette vidéo, que ce soit un smartphone ou un PC.
watching this video on, whether it's a smartphone or a PC.
Bien sûr il y a une différence de vitesse, mais pas de différence de capacité.
Of course there's a difference in speed, but no difference in capability.
Tous les problèmes qu’El Capitan peut résoudre, votre vieil ordinateur ou votre
All the problems El Capitan can solve, your old computer or your
smartphone pourraient les résoudre aussi, si on leur laissait suffisamment de temps.
smartphone could solve them too, if given enough time.
Et c’est même plus fort que ça, on est quasiment certains que même une
And it goes even further than that, we're almost certain that even a
civilisation extra-terrestre super avancée ne possèdera jamais d’ordinateurs qui soient
super-advanced extraterrestrial civilization will never have computers that are
très différents des nôtres, des ordinateurs qui seraient capables
very different from ours, computers that would be able
de résoudre des problèmes que les nôtres ne peuvent fondamentalement pas résoudre.
to solve problems that ours fundamentally can't solve.
Oui oui, même si les aliens ont des giga-ordinateurs à
Yes yes, even if aliens have giga-computers with
gravitons quantiques supersymétriques. Ces ordinateurs seront peut-être plus rapides,
supersymmetric quantum gravitons. Those computers might be faster,
mais il ne disposeront pas de capacités nouvelles par rapport aux nôtres.
but they won't have new capabilities compared to ours.
Evidemment vous vous dites que ce que je raconte parait un peu invraisemblable,
Obviously you're thinking that what I'm saying seems a bit far-fetched,
et il va falloir que je sois plus précis quand je parle des capacités des ordinateurs. Et pour
and I'll need to be more precise when I talk about computer capabilities. And to
comprendre ça, on va se pencher sur les travaux d’un des pionniers de l’informatique, un des
understand that, we'll look at the work of one of the pioneers of computing, one of
esprits scientifiques les plus brillants du XXe siècle : le mathématicien britannique Alan Turing.
the most brilliant scientific minds of the 20th century: the British mathematician Alan Turing.
[IMITATION Vous connaissez peut être son nom si vous avez vu le film « The Imitation Game »,
[IMITATION You may know his name if you've seen the film "The Imitation Game,"
un film biographique qui raconte comment Alan Turing a dirigé l’équipe de cryptographie qui
a biographical film that tells how Alan Turing led the cryptography team that
pendant la seconde guerre mondiale a cassé le codes secrets des nazis,
during World War II cracked the Nazis' secret codes,
donnant ainsi un avantage déterminant aux alliés.]
giving the Allies a decisive advantage.]
Mais aujourd’hui, je vais vous parler de ce que Turing a fait avant la guerre, en 1936, quand il
But today, I'm going to talk about what Turing did before the war, in 1936, when he
a inventé ce concept qu’on appelle maintenant « les machines de Turing ». Bizarrement,
invented the concept we now call "Turing machines." Oddly enough,
une machine de Turing, c’est un truc abstrait, totalement inutile en pratique. Personne n’en
a Turing machine is an abstract thing, totally useless in practice. No one has ever
a jamais construit pour une application véritable. Même pas Turing lui-même !
built one for a real application. Not even Turing himself!
Mais il s’agit d’un concept d’une importance théorique considérable, qui va nous permettre de
But it's a concept of considerable theoretical importance, which will allow us to
comprendre pourquoi, en un certain sens, presque tous les ordinateurs de l’Univers se valent.
understand why, in a certain sense, almost all computers in the Universe are equal.
[jingle]
[jingle]
Pour parler des capacités des ordinateurs,
To talk about computers' capabilities,
il faut se demander à quoi on les utilise. Au quotidien on s’en sert pour communiquer,
we need to ask what they're used for. In daily life, we use them to communicate,
travailler, se divertir, mais fondamentalement, ce que fait un ordinateur, ce sont des calculs.
work, have fun, but fundamentally, what a computer does is calculations.
[E/S Il reçoit des données numériques en entrée, qui viennent du clavier,
[I/O It receives numerical data as input, coming from the keyboard,
du disque dur, d’internet, et il effectue des calculs dessus pour produire des sorties,
the hard drive, the internet, and it performs calculations on them to produce outputs,
qui sont numériques elles aussi. Bien sûr,
which are numerical too. Of course,
souvent l’ordinateur va nous restituer ça sous forme d’images, de sons, mais fondamentalement
often the computer will return that to us as images, sounds, but fundamentally
ce qu’il fait c’est prendre des nombres en entrée, et produire des nombres en sortie.]
what it does is take numbers as input, and produce numbers as output.]
Et pour faire ça, un ordinateur ne fait pas des calculs au pif ou au feeling : il applique
And to do that, a computer doesn't calculate at random or by feel: it applies
de façon mécanique et systématique une suite d’instructions, ce qu’on appelle un algorithme.
mechanically and systematically a sequence of instructions, what's called an algorithm.
[E/S N Mathématiquement, puisque qu’un calcul prend des nombres en entrée et
[I/O Mathematically, since a calculation takes numbers as input and
donne des nombres en sortie, on peut voir un algorithme comme une fonction.
gives numbers as output, we can see an algorithm as a function.
Et pour schématiser, on peut se ramener au cas d’une fonction qui va de N dans
And to simplify, we can reduce to the case of a function that goes from N to
N : une fonction qui transforme un nombre entier n en un autre nombre entier f(n).]
N: a function that transforms an integer n into another integer f(n).]
Calculer des fonctions sur les nombres entiers, c’est ce que faisaient déjà
Calculating functions on integers is what mechanical calculating machines
les machines à calculer mécaniques, et c’est toujours concrètement ce que fait
already did, and it's still concretely what a computer does today:
un ordinateur aujourd’hui : il calcule le résultat de fonctions très compliquées.
it calculates the result of very complicated functions.
Maintenant la question qu’on peut se poser, c’est : est-ce que toutes les fonctions des nombres
Now the question we might ask is: are all functions of integers
entiers sont calculables par un ordinateur. Si je prends une fonction de N dans N au pif,
computable by a computer? If I take a function from N to N at random,
est-ce que j’ai la certitude qu’il existe un algorithme, une suite d’instructions,
am I certain that there's an algorithm, a sequence of instructions,
telles qu’un ordinateur pourra calculer sa valeur pour n’importe quel n ?
such that a computer can calculate its value for any n?
[E/S Intuitivement, on a envie de penser que oui. Si ma fonction c’est f(n) = 5 n^2 + 6n + 12,
[I/O Intuitively, we're inclined to think yes. If my function is f(n) = 5 n^2 + 6n + 12,
on voit bien qu’il n’est pas compliqué d’écrire un programme informatique qui
it's clear it's not hard to write a computer program that
la calcule, et ce pour n’importe quelle valeur de n. Et ça marche
calculates it, for any value of n. And it works
aussi si je prends une fonction de N beaucoup plus compliquée.]
too if I take a much more complicated function from N.]
Et pourtant en maths, toutes les fonctions ne sont pas toujours définies explicitement,
And yet in math, not all functions are always explicitly defined,
comme çà, par une formule avec des multiplications et des additions qui font intervenir le nombre n.
like that, by a formula with multiplications and additions involving the number n.
Tenez, considérez la fonction qui a un nombre n associe sont plus grand facteur premier p.
Take, consider the function that to a number n associates its largest prime factor p.
C’est une fonction parfaitement bien définie mathématiquement. Est-ce qu’on peut calculer
This is a perfectly well-defined function mathematically. Can we compute
cette fonction avec un ordinateur ? Eh bien oui, c’est assez simple d’écrire un
this function with a computer? Well yes, it’s quite simple to write an
algorithme qui va vous produire le bon résultat, quelle que soit l’entrée n.
algorithm that will produce the correct result, whatever the input n.
Mais en mathématiques, on peut aussi imaginer des fonctions définies de façon implicite,
But in mathematics, we can also imagine functions defined implicitly,
et dont ça n’est pas évident a priori qu’elles soient calculables.
and it’s not obvious a priori that they are computable.
[ELLIPTIC Par exemple la fonction qui a un nombre n associe : le nombre de solutions
[ELLIPTIC For example, the function that maps a number n to: the number of integer
entières de l’équation x^2 = y^3 + n. Ca a l’air un peu compliqué, mais c’est un truc bien défini
solutions of the equation x^2 = y^3 + n. It looks a bit complicated, but it’s a well-defined thing
mathématiquement. Vous prenez un nombre n, vous regardez l’équation x^2 = y^3 + n. Elle possède un
mathematically. You take a number n, you look at the equation x^2 = y^3 + n. It has a
certain nombre de solutions entières. C’est-à-dire des couples (x,y) pour lesquels ça marche.
certain number of integer solutions. That is, pairs (x,y) for which it works.
Par exemple pour n=1, vous avez la solution x=1 et y=0. Vous avez aussi x=3 et y=2. Ca en fait
For example for n=1, you have the solution x=1 and y=0. You also have x=3 and y=2. That makes
au moins deux, mais combien y en a-t-il au total ? Eh bien pour un nombre n donné cette fonction
at least two, but how many are there in total? Well for a given number n this function
est bien définie mathématiquement, mais c’est pas gagné de trouver un algorithme qui puisse
is well-defined mathematically, but it’s not a given to find an algorithm that can
la calculer pour n’importe quel n. Ca n’est pas évident que cette fonction soit calculable.]
compute it for any n. It’s not obvious that this function is computable.]
La question de savoir quelles sont les fonctions qui sont calculables, elle a notamment été posée
The question of which functions are computable was notably raised
dans les années 1930 par le mathématicien et logicien Alonzo Church. Et il a tenté
in the 1930s by the mathematician and logician Alonzo Church. And he attempted
d’y apporter une réponse au moyen d’une technique un peu abstraite qu’on appelle le lambda-calcul.
to answer it using a somewhat abstract technique called lambda calculus.
Je pourrais vous parler du lambda-calcul de Church,
I could tell you about Church’s lambda calculus,
mais j’ai peur que ça vous file rapidement mal à la tête. Heureusement pour nous,
but I’m afraid it would quickly give you a headache. Fortunately for us,
il se trouve qu’à cette époque, Alonzo Church avait un brillant étudiant du nom d’Alan Turing,
it turns out that at that time, Alonzo Church had a brilliant student named Alan Turing,
et ce dernier a proposé une autre façon beaucoup plus imagée d’approcher cette
and the latter proposed another, much more visual way to approach this
question : ce qu’on appelle aujourd’hui les machines de Turing. Alors qu’est-ce que c’est ?
Question: what we today call Turing machines. So what is it?
[jingle]
[jingle]
Ce que fait Turing, c’est qu’il imagine une machine mécanique qui réalise des calculs,
What Turing does is imagine a mechanical machine that performs calculations,
en s’inspirant de la façon dont procèdent les humains. Généralement, nous on utilise du papier,
inspired by how humans proceed. Generally, we use paper,
un crayon et éventuellement une gomme, et puis on applique des règles qu’on a apprises à l’école.
a pencil, and possibly an eraser, and then apply rules we learned in school.
[RUBAN Alors allons-y : imaginez une machine qui dispose d’un immense ruban de papier divisé
[TAPE] So let's go: imagine a machine with a huge paper tape divided
en cases, avec la possibilité d’écrire un symbole dans chaque case. Ces symboles,
into cells, with the ability to write a symbol in each cell. These symbols,
ça peut être des lettres, des chiffres, des emojis si vous voulez, mais on s’impose que
can be letters, numbers, emojis if you want, but we impose that
l’ensemble des symboles possibles soit de taille finie. Pour fixer les idées, imaginons que ce soit
the set of possible symbols is finite in size. To fix ideas, let's imagine it's
juste les chiffres de 0 à 9. Donc chaque case est soit vide, soit elle contient un chiffre.
just the digits 0 to 9. So each cell is either empty or contains a digit.
Maintenant pour travailler avec ce ruban, on va supposer que la machine dispose d’une tête de
Now to work with this tape, we'll assume the machine has a read/write
lecture et d’écriture, qui peut se déplacer sur le ruban. Quand elle est au-dessus d’une case, elle
head, which can move along the tape. When it's above a cell, it
peut lire le symbole contenu, et éventuellement l’effacer pour le remplacer par un autre symbole.
can read the symbol contained, and possibly erase it to replace it with another symbol.
Et se déplacer ensuite dans la case située soit à gauche, soit à droite.
And then move to the cell either to the left or to the right.
Si on veut définir sans ambiguïté le comportement de notre machine,
If we want to define unambiguously the behavior of our machine,
d’une façon mécanique, pour ne pas qu’il y ait à réfléchir, il faut qu’on spécifie précisément ce
in a mechanical way, so there's no need to think, we must specify precisely what
qu’elle doit faire dans chacun des cas qu’elle peut rencontrer. Donc pour chacun des symboles
it should do in each case it might encounter. So for each of the symbols
qui peuvent se situer dans la case qu’elle lit, il faut lister quel éventuel nouveau symbole on
that might be in the cell it reads, we must list which possible new symbol we
inscrit, et dans quelle direction la tête se déplace ensuite, à droite ou à gauche.
write, and in which direction the head moves next, right or left.
Voici un exemple d’une liste d’instructions de ce genre,
Here's an example of such a list of instructions,
on appelle ça une table de transition. Ici si la machine lit le symbole 4 dans une case,
we call it a transition table. Here if the machine reads the symbol 4 in a cell,
elle l’efface et inscrit 6 à la place, puis se déplace à gauche. Si elle lit le symbole 5,
she erases it and writes 6 in its place, then moves left. If she reads the symbol 5,
elle inscrit 3 et va à droite. Etc. Et notez qu’on a aussi le cas d’une case vide.
she writes 3 and goes right. Etc. And note we also have the case of an empty cell.
Bien donc vous voyez que si vous disposez de la table de transition et d’un ruban sur lequel
Well, so you see that if you have the transition table and a tape on which
sont inscrit initialement des symboles, vous avez tout ce qu’il faut pour faire
symbols are initially written, you have everything you need to make
fonctionner la machine en automatique : elle lit un symbole, elle consulte la table de transition,
the machine work automatically: it reads a symbol, it consults the transition table,
elle écrit un nouveau symbole, et elle se déplace. Et on recommence.
it writes a new symbol, and it moves. And we start again.
Aucune réflexion à produire, aucune initiative à prendre : c’est mécanique.
No thinking needed, no initiative to take: it's mechanical.
On pourrait s’amuser à construire ou plutôt à simuler des machines
We could have fun building or rather simulating machines
de ce genre et à voir ce que ça donne pour différentes tables de transition,
of this kind and seeing what happens for different transition tables,
et différentes entrées sur le ruban. Avec des symboles qui seraient des chiffres,
and different inputs on the tape. With symbols that would be digits,
on verrait le contenu du ruban se modifier au cours du temps, d’une façon qui dépend évidemment
we'd see the tape's content change over time, in a way that obviously depends
de la table de transition et de ce qu’on a inscrit au départ. Et donc on peut dire que notre machine
on the transition table and on what was written initially. So we can say our machine
réalise un calcul. Elle prend des nombres en entrée, elle produit des nombres en sortie.
performs a computation. It takes numbers as input, it produces numbers as output.
Le genre de machine que je viens de vous décrire là, ça n’est pas encore exactement ce que Turing
The kind of machine I've just described to you, that's not yet exactly what Turing
avait imaginé, ce sont des machines un peu moins intéressantes. Car Turing, lui,
had imagined; these are somewhat less interesting machines. Because Turing, himself,
a ajouté un ingrédient supplémentaire : un état interne de la machine.
added an extra ingredient: an internal state of the machine.
En gros, l’idée c’est que la machine puisse être dans un certain nombre d’états, on peut
Basically, the idea is that the machine can be in a certain number of states; we can
les désigner par des lettres par exemples. Disons pour fixer les idées qu’il y a 3 états A, B et C.
designate them by letters, for example. Let's say to fix ideas there are 3 states A, B, and C.
A chaque instant, la machine est dans un de ces 3 états. On va symboliser ça par des grosses LEDs,
At each moment, the machine is in one of these 3 states. We'll symbolize that with big LEDs,
et celle qui est allumée indique l’état dans lequel on se trouve.
and the one that's lit indicates the state we're in.
Et maintenant, on va prendre en compte l’état dans la table de transition. Chaque état A, B ou C aura
And now, we'll take the state into account in the transition table. Each state A, B, or C will have
sa propre liste d’instructions. Ici par exemple la machine se comportera vraiment différemment
its own list of instructions. Here, for example, the machine will really behave differently
suivant qu’elle est dans l’état A ou B par exemple. Et maintenant on doit aussi préciser pour
depending on whether it's in state A or B, for example. And now we also need to specify for
chaque transition non seulement le nouveau symbole à écrire, mais aussi dans quel état la machine
each transition not only the new symbol to write, but also which state the machine
doit se mettre à la fin de l’opération. Elle peut rester dans le même, ou bien changer d’état.
should be in at the end of the operation. It can stay in the same one, or change state.
Tout ça a l’air un peu compliqué mais prenons un exemple. Par exemple ici,
This all seems a bit complicated, but let's take an example. For example, here,
si la machine est dans l’état A et lit le symbole 4, alors elle inscrit le symbole 7,
if the machine is in state A and reads symbol 4, then it writes symbol 7,
passe dans l’état C et va sur la case à sa droite. Et on recommence.]
goes to state C and moves to the cell on its right. And we start again.]
Et là aussi on peut partir dans un état initial avec certains symboles sur le ruban,
And here too, we can start in an initial state with certain symbols on the tape,
et mouliner pas à pas en appliquant les instructions sans réfléchir. Et on est
and grind step by step by applying the instructions without thinking. And we are
bien en train d’effectuer un calcul mécanique, appliquer un algorithme,
indeed performing a mechanical computation, applying an algorithm,
dans le sens où la machine execute les instructions sans prendre d’initiative.
in the sense that the machine executes the instructions without taking any initiative.
Evidemment il faut une dernière chose pour prétendre que cette machine réalise un
Obviously, one last thing is needed to claim that this machine performs a
calcul : dans l’état actuel, la machine tourne indéfiniment. Et donc on ajoute une dernière
computation: in the current state, the machine runs indefinitely. So we add one last
possibilité : au lieu de se déplacer, la machine peut aussi s’arrêter. On va représenter ça avec un
possibility: instead of moving, the machine can also stop. We'll represent that with a
état stop dans notre table de transition. Quand la machine rencontre un stop, elle s’arrête.
stop state in our transition table. When the machine encounters a stop, it stops.
A ce stade, peut-être que vous vous dites que cette machine a l’air bien compliquée,
At this point, maybe you're thinking this machine seems quite complicated,
on va prendre un exemple pour fixer les idées. On va faire une machine qui ajoute 1 à un nombre.
let's take an example to clarify things. We'll make a machine that adds 1 to a number.
[ADD1 Pour ça on imagine deux états, on va les appeler A et B, et on considère la
[ADD1 For this, we imagine two states, we'll call them A and B, and we consider the following
table de transition suivante. Imaginez qu’on démarre dans l’état A avec le nombre 27999
transition table. Imagine we start in state A with the number 27999
inscrit sur le ruban, le but est de lui ajouter 1. Appliquons pas à pas les règles de la table.
written on the tape, the goal is to add 1 to it. Let's apply the table rules step by step.
En gros vous voyez que dans l’état A, on se déplace à droite systématiquement,
Basically, you see that in state A, we always move right,
en laissant le chiffre inchangé, jusqu’à tomber sur une case blanche,
leaving the digit unchanged, until we hit a blank cell,
auquel cas on passe dans l’état B et on se déplace à gauche.
in which case we switch to state B and move left.
Une fois dans l’état B, les règles de transition sont différentes. Si on a un 9,
Once in state B, the transition rules are different. If we have a 9,
on le change en 0 on se déplace à gauche. Si on a un nombre autre qu’un 9,
we change it to 0 and move left. If we have a number other than 9,
on lui ajoute 1 et on s’arrête. Et enfin si on a une case vide on inscrit 1 et on s’arrête.
we add 1 to it and stop. And finally, if we have an empty cell, we write 1 and stop.
Relisons ça et essayons de comprendre ce qu’il va se passer : au début c’est
Let's reread this and try to understand what will happen: at the start, it's
l’état A et on commence par se déplacer à droite jusqu’à trouver une case blanche,
state A, and we begin by moving right until we find a blank cell,
auquel cas on revient à gauche sur ce qui est donc le chiffre des unités, et on passe dans l’état B.
in which case we go back left to what is therefore the units digit, and we switch to state B.
Une fois dans l’état B, dans chaque case on ajoute 1 et on bouge à gauche. Et tant
Once in state B, in each cell, we add 1 and move left. And as long as
que ce sont des 9 on continue ce qui permet d’une certaine façon de propager la retenue.
they are 9s, we continue, which in a way propagates the carry.
Voilà, on a une machine un peu fastidieuse mais qui permet d’ajouter 1 au nombre
There you go, we have a somewhat tedious machine, but it allows adding 1 to the number
inscrit initialement sur le ruban. C’est un calcul très simple mais ça fonctionne.]
initially written on the tape. It's a very simple calculation, but it works.
On pourrait de la même façon créer des machines pour des opérations plus compliquées. Par exemple
We could similarly create machines for more complicated operations. For example,
on pourrait faire une machine qui additionne deux nombres présents initialement sur le ruban,
we could make a machine that adds two numbers initially on the tape,
mais là il faudrait beaucoup plus d’états et une table de transition plus compliquée.
but that would require many more states and a more complicated transition table.
Ce qu’il faut comprendre, c’est que l’intérêt des machines de Turing est purement théorique. C’est
What we need to understand is that the interest of Turing machines is purely theoretical. It's
une manière de formaliser mathématiquement ce que veut dire « effectuer mécaniquement un calcul ».
a way to mathematically formalize what it means to 'mechanically perform a calculation'.
Mais personne ne construit jamais vraiment des machines de Turing telles quelles,
But nobody ever really builds Turing machines as such,
Turing lui même n’a pas essayé d’en fabriquer.
Turing himself didn't try to build one.
Les seules que je connaisse, qui ont été physiquement réalisées, c’est uniquement
The only ones I know of that were physically made are only
pour des raisons pédagogiques ou historiques. Par exemple en 2012, à l’occasion du centenaire
for educational or historical reasons. For example, in 2012, for the centenary
de la naissance de Turing, des étudiants en informatique de l’Ecole Normale Supérieure
of Turing's birth, computer science students at the École Normale Supérieure
de Lyon en avait faite une entièrement en LEGO, fonctionnant avec des mécanismes pneumatiques.
in Lyon built one entirely out of LEGO, working with pneumatic mechanisms.
Et il se trouve qu’à l’heure où je tourne cette vidéo, le mathématicien Aurélien Alvarez et deux
And it happens that as I film this video, mathematician Aurélien Alvarez and two
de ses étudiants, David et Mathieu, sont en train de finir d’en construire une nouvelle,
of his students, David and Mathieu, are finishing building a new one,
totalement repensée, qui sera très bientôt exposée à la Maison des Mathématiques et de l’Informatique
completely redesigned, which will soon be exhibited at the Maison des Mathématiques et de l'Informatique
de Lyon. Vous pourrez aller la voir mais ils m’ont fait l’honneur d’une petite avant-première.
in Lyon. You'll be able to go see it, but they did me the honor of a small preview.
Ici vous pouvez voir le ruban, divisé en cases. Dans chaque case il y a deux briques mobiles qui
Here you can see the tape, divided into cells. In each cell there are two movable bricks that
représentent des bits d’information. S’ils sont tous les deux à zéros, la case est considérée
represent bits of information. If they're both at zero, the cell is considered
comme vide, et sinon on peut encoder un symbole parmi 3 possibles. Tout ça est
empty, and otherwise you can encode a symbol among 3 possible ones. All of this is
alimenté par un moteur pneumatique et un mécanisme d’horloge qui permet de séquencer les opérations.
powered by a pneumatic motor and a clock mechanism that sequences the operations.
La machine possède 8 états, et à chaque instant elle sait dans quel état elle est grâce à ces 3
The machine has 8 states, and at each moment it knows what state it's in thanks to these 3
leviers oranges qu’elle peut commuter. Les 3 autres lui servent à savoir quel symbole
orange levers it can switch. The other 3 let it know what symbol
inscrire et dans quel direction aller ensuite. Et puis ici on voit l’endroit où est encodé
to write and which direction to go next. And here we see where the transition
la table de transition. Ca prend pas mal de place évidemment car on a 32 cas possibles,
table is encoded. It takes up quite a bit of space obviously because there are 32 possible cases,
8 états et 4 symboles, et pour chaque de ces 32 cas on encode avec des petits leviers la
8 states and 4 symbols, and for each of these 32 cases we encode with small levers the
transition à réaliser : le nouveau symbole, le nouvel état et la direction du mouvement.
transition to carry out: the new symbol, the new state, and the direction of movement.
Ici on peut voir la machine en action sur le ruban,
Here you can see the machine in action on the tape,
les deux tiges verticales servent de capteur qui va lire l’état du ruban et
The two vertical rods act as a sensor that reads the tape's state, and
les tiges horizontales peuvent faire coulisser les briques et donc écrire un nouveau symbole.
the horizontal rods can slide the bricks and thus write a new symbol.
[jingle]
[jingle]
Je l’ai dit, l’intérêt de la machine de Turing est purement théorique. Ce que Turing affirme,
As I said, the Turing machine's interest is purely theoretical. What Turing claims,
c’est que tout ce qui est calculable peut être calculé avec une machine de Turing.
is that everything computable can be computed with a Turing machine.
Avec son concept, Turing propose en fait une définition formelle,
With his concept, Turing actually proposes a formal definition,
mathématique, pour la notion un peu floue de « truc calculable ».
mathematical, for the somewhat fuzzy notion of 'computable thing'.
Il n’est pas le seul à avoir fait ça, je l’ai dit. La même année, en 1936, Alonzo Church qui était
He's not the only one to have done that, as I said. The same year, in 1936, Alonzo Church, who was
donc le directeur de thèse de Turing, proposait le premier une définition de « calculable », à l’aide
thus Turing's thesis advisor, was the first to propose a definition of 'computable', using
de ce formalisme baptisé « lambda-calcul ». Mais ce que Turing démontre, c’est que sa définition
this formalism called 'lambda calculus'. But what Turing shows is that his definition
avec les machines est en fait mathématiquement équivalente à la définition de Church.
with machines is actually mathematically equivalent to Church's definition.
Il y a eu à la même époque quelques autres tentatives de formalisation
There were at the same time a few other attempts at formalizing
de la notion de calcul, mais à chaque fois aboutissant à quelque
the notion of computation, but each time resulting in something
chose d’équivalent à ce qu’avaient déjà proposé respectivement Church et Turing.
equivalent to what Church and Turing had respectively already proposed.
On a donc de très bonnes raisons de penser que ces deux là avaient vu juste,
So we have very good reasons to think that these two had it right,
et que leurs formalismes respectifs capturent bien la notion de ce qu’est un truc calculable.
and that their respective formalisms indeed capture the notion of what a computable thing is.
Et on appelle cela « la thèse de Church-Turing ».
And that's called 'the Church-Turing thesis'.
Le truc qu’il faut comprendre, c’est que ça n’est pas un théorème, c’est une thèse,
The thing to understand is that it's not a theorem, it's a thesis,
ça ne se démontre pas formellement. Ce que disent implicitement Church et Turing,
it can't be formally proven. What Church and Turing implicitly say,
c’est que tous les calculs qui sont réalisables avec quelque processus physique que ce soit,
is that all computations achievable with any physical process whatsoever,
sont exactement ceux qui sont faisables avec les machines de Turing.
are exactly those feasible with Turing machines.
C’est donc presque plutôt une affirmation sur le monde physique : la thèse de Church-Turing
So it's almost rather a claim about the physical world: the Church–Turing thesis
implique qu’il n’existera jamais aucune machine ou aucun processus physique qui calculerait
implies that there will never be any machine or physical process that would compute
quelque chose qu’on ne puisse fondamentalement pas calculer au moyen d’une machine de Turing.
something that one fundamentally cannot compute by means of a Turing machine.
Donc les machines de Turing, c’est, sur le papier, un concept extrêmement puissant.
So Turing machines are, on paper, an extremely powerful concept.
Avec toutefois une limitation importante. Comme vous l’avez vu avec les exemples que j’ai donné,
With, however, one important limitation. As you saw with the examples I gave,
si vous voulez réaliser deux types de calculs complètement différents,
if you want to perform two completely different types of computations,
il vous faut carrément changer de machine.
you literally have to change machines.
Peut-être qu’il faudra passer à une machine qui utilisera une table de transition différente,
Maybe you'll need to switch to a machine that uses a different transition table,
peut-être plus d’états ou bien un nombre de symboles différents. Bref,
perhaps more states or a different number of symbols. In short,
si vous voulez faire un autre calcul, vous devez a priori imaginer une autre machine.
if you want to do another computation, you must in principle imagine another machine.
C’est un peu fastidieux, et ça semble limiter la portée concrète de la thèse
That's a bit tedious, and it seems to limit the practical scope of the
de Church-Turing. La thèse nous dit que pour toute fonction calculable, il existe
Church–Turing thesis. The thesis tells us that for every computable function, there exists
une machine de Turing qui fait ce calcul, mais du coup il faut concevoir et construire cette
a Turing machine that does that computation, but then you have to design and build that
machine spécifiquement pour ce calcul. Une fonction calculable = une machine de Turing.
machine specifically for that computation. One computable function = one Turing machine.
[NINTENDO Pour prendre une analogie, c’est comme ces tous premiers jeux vidéos portables que
[NINTENDO To use an analogy, it's like those very first handheld video games that
Nintendo dans les années 80 appelait les « Game & Watch ». Vous aviez un petit appareil électronique
Nintendo in the 80s called 'Game & Watch'. You had a small electronic device
qui ne contenait qu’un seul jeu. L’appareil était le jeu, et pour changer de jeu il fallait
that contained only a single game. The device was the game, and to change games you had to
en acheter un autre, programmé spécifiquement pour. Il y en avait une soixante de différents.]
buy another one, programmed specifically for it. There were about sixty different ones.]
Bon, vous savez qu’aujourd’hui ça n’est pas comme ça qu’on joue : on a une seule machine, un PC
Well, you know that today that's not how we play: we have a single machine, a PC
ou une console, et on fait tourner tous les jeux dessus en changeant seulement le code source, que
or a console, and we run all games on it by only changing the source code,
l’on charge en mémoire. Est-ce qu’on pourrait pas faire la même chose avec les machines de Turing ?
we load into memory. Couldn't we do the same thing with Turing machines?
Eh bien Turing avait déjà envisagé la question ! Dès son article de
Well, Turing had already considered the question! From his paper
1936 définissant la notion de machine de Turing,
from 1936 defining the notion of the Turing machine,
il se demande s’il serait possible de construire une machine dite « universelle ».
he asks whether it would be possible to build a so-called "universal" machine.
[MACHINE On l’a dit, une machine réalise un calcul. En gros un calcul,
[MACHINE As we said, a machine performs a computation. Roughly, a computation,
c’est comme appliquer une certaine fonction F sur un nombre entier n.
is like applying a certain function F to an integer n.
Et vous pouvez fabriquer une machine qui va représenter la fonction F : vous
And you can build a machine that will represent the function F: you
inscrivez le nombre n en entrée sur le ruban, et vous lancez la machine.
write the number n as input on the tape, and you start the machine.
Comme la fonction F est en gros représentée par la table de transition, on l’a dit : si vous voulez
Since the function F is roughly represented by the transition table, as we said: if you want to
changer de fonction, il faut changer de machine et cabler une machine avec une table différente.
change the function, you have to change the machine and wire a machine with a different table.
Est-ce qu’on ne pourrait pas à la place faire une machine universelle programmable. Une machine
Couldn't we instead make a universal programmable machine? A single machine,
unique, pour laquelle on inscrirait sur le ruban à la fois le nombre n, et la description de la
where we would write on the tape both the number n and the description of the
table de transition qui représente F. Et si on veut changer de fonction F qu’on calcule,
transition table that represents F. And if we want to change the function F we compute,
on change sa description sur le ruban au départ, mais on garde la même machine.]
we change its description on the tape at the start, but we keep the same machine.]
Eh bien dans son article de 1936, Turing prouve que ces
Well, in his 1936 paper, Turing proves that these
machines existent. Qu’il est possible d’utiliser une machine universelle,
machines exist. That it's possible to use a universal machine,
une machine unique pour les gouverner toutes, en quelque sorte. Et en faisant ça,
one machine to rule them all, so to speak. And in doing so,
il invente de façon abstraite le concept d’ordinateur universellement programmable.
he abstractly invents the concept of the universally programmable computer.
On s’accorde à dire en général que le premier ordinateur physique de ce genre est l’ENIAC,
It's generally agreed that the first physical computer of this kind is the ENIAC,
qui a été achevé seulement en 1946,
which was only completed in 1946,
soit 10 ans après que Turing ait imaginé son concept de machine universelle.
so 10 years after Turing imagined his concept of the universal machine.
Alors à quoi ça ressemble une machine universelle ? Eh bien elles sont évidemment assez complexes,
So what does a universal machine look like? Well they are obviously quite complex,
mais on sait en construire explicitement un certain nombre.
but we know how to build a certain number of them explicitly.
Et ce que des chercheurs ont essayé de faire au cours des dernières décennies,
And what researchers have tried to do over the past decades,
c’est découvrir des machines de Turing universelles qui soient de plus en plus
is discover universal Turing machines that are more and more
petites, c’est-à-dire qui utilisent le moins possible d’états et de symboles
small, that is, that use as few states and symbols as possible
Ainsi on en connait avec 2 états et 18 symboles, ou bien 5 états et 5 symboles,
Thus we know some with 2 states and 18 symbols, or 5 states and 5 symbols,
ou bien 15 états et seulement 2 symboles. Il y a tout un tas de compromis possibles.
or 15 states and only 2 symbols. There are all sorts of possible trade-offs.
Et d’ailleurs la machine de l’ENS Lyon que vous avez vu en vidéo,
And by the way the ENS Lyon machine you saw on video,
c’est une machine universelle, qui a donc 8 états et 4 symboles.
it's a universal machine, which therefore has 8 states and 4 symbols.
Ce que vous avez sans doute compris, c’est qu’une machine de Turing universelle réalise
What you've probably understood is that a universal Turing machine performs
en gros ce que fait un ordinateur moderne : on garde le même hardware, et en mémoire,
basically what a modern computer does: we keep the same hardware, and in memory,
donc sur le ruban, on inscrit à la fois le programme qu’on veut faire tourner,
so on the tape, we write both the program we want to run,
la fonction F, et les données d’entrée sur lesquelles on veut l’appliquer, le nombre n.
the function F, and the input data we want to apply it to, the number n.
Les ordinateurs que l’on utilise tous les jours sont des machines de Turing universelles. Enfin
The computers we use every day are universal Turing machines. Well
ça dépend un peu de comment on les utilise. Vous avez que quand on utilise un ordinateur pour créer
it depends a bit on how we use them. You know that when you use a computer to create
un programme informatique, on ne va pas utiliser directement les instructions qui pilotent le
a computer program, we don't directly use the instructions that drive the
processeur. On utilise une couche intermédiaire qui s’appelle un langage de programmation.
processor. We use an intermediate layer called a programming language.
La plupart des langages de programmation permettent effectivement de faire en
Most programming languages do indeed allow
sorte que notre ordinateur se comporte comme une machine de Turing universelle,
our computer to behave like a universal Turing machine,
on dit de ces langages qu’ils sont « Turing-complets ».
These languages are said to be “Turing-complete”.
Mais tous les langages de programmation ne le sont pas forcément. Les langages génériques le
But not all programming languages necessarily are. Generic languages are:
sont : le C, le Python etc. Mais par exemple HTML n’est pas Turing-complet. LaTeX l’est par contre !
C, Python, etc. But for example, HTML isn’t Turing-complete. LaTeX, though, is!
[JEUX VIDÉO Ce qu’il y a d’amusant, c’est qu’un certain nombre de systèmes
[VIDEO GAMES What’s amusing is that a number of systems
qu’on trouve dans des jeux vidéo sont aussi Turing complets. Par exemple avec
found in video games are also Turing-complete. For example, with
la redstone dans Minecraft, vous pouvez simuler une machine de Turing universelle.
redstone in Minecraft, you can simulate a universal Turing machine.
C’est pareil dans des jeux comme Factorio ou Dwarf Fortress. Plus intriguant,
It’s the same in games like Factorio or Dwarf Fortress. More intriguingly,
des jeux comme Baba is You ou même le système de règles de Magic sont aussi Turing-complets.]
games like Baba Is You, or even Magic’s rule system, are also Turing-complete.]
Peut-être que maintenant vous comprenez pourquoi j’affirmais au début de la vidéo
Maybe now you understand why I claimed at the start of the video
que même le plus ancien des smartphones pouvait être considéré comme équivalent au
that even the oldest smartphone could be considered equivalent to the
super-ordinateur El Capitan du point de vue de ses capacités de calcul.
El Capitan supercomputer in terms of its computing capabilities.
Ce sont l’un et l’autre des machines de Turing universelles. Donc ce que l’un peut calculer,
Both are universal Turing machines. So what one can compute,
l’autre le peut aussi. La seule différence c’est le temps qu’ils
the other can too. The only difference is the time they’ll
vont y passer respectivement. Du point de vue des capacités fondamentales à calculer,
spend on it respectively. From the standpoint of fundamental computing abilities,
tous les ordinateurs du monde se valent, et presque tous les langages de programmation aussi.
all computers in the world are equal, and almost all programming languages too.
Et si la thèse de Church-Turing est effectivement correcte, c’est-à-dire que le concept de machine
And if the Church-Turing thesis is indeed correct, that is, the concept of a Turing
de Turing capture exactement l’ensemble de ce qui est physiquement calculable,
machine captures exactly everything that is physically computable,
alors c’est encore plus fort. On sait qu’on ne pourra jamais construire d’ordinateurs qui
then it’s even stronger. We know we can never build computers that
possède des capacités fondamentalement supérieures aux machines actuelles.
possess fundamentally superior capabilities to current machines.
Quelle que soit la technologie utilisée,
Whatever the technology used,
même un ordinateur quantique ou une technologie extra-terrestre inconnue.
even a quantum computer or unknown extraterrestrial technology.
Tout ce qui est physiquement calculable l’est déjà avec nos machines actuelles,
Anything physically computable is already computable with our current machines,
il suffit juste d’y passer suffisamment de temps, et d’avoir suffisamment de place en mémoire.
you just need enough time, and enough memory space.
Donc nos ordinateurs peuvent déjà calculer tout ce qui est calculable. Mais de toute façon,
So our computers can already compute everything that is computable. But anyway,
est-ce que des trucs non-calculables, ça existe vraiment ? Est-ce qu’on ne pourrait
do non-computable things really exist? Could we not
pas finalement tout calculer ? Alors avant que vous me sortiez des trucs du genre « mais non,
eventually compute everything? Before you throw things at me like 'but no,
l’amour ou l’art ou le bonheur, ça ne se calcule pas ! », il faut que je précise ma question.
love or art or happiness can't be computed!', I need to clarify my question.
On l’a dit plus haut, faire un calcul, c’est en gros utiliser
As mentioned earlier, computing is basically using
un procédé mécanique qui permet d’obtenir la valeur d’une fonction,
a mechanical process to get the value of a function,
et pour cela on peut se ramener aux fonctions des nombres entiers. Et la question qu’on se pose,
and for that we can reduce to functions of integers. The question we ask,
c’est : est-ce qu’il existe des fonctions non-calculables ? Est-ce qu’il existe des
is: do non-computable functions exist? Are there
fonctions pour lesquelles aucune machine de Turing ne peut réaliser le calcul ?
functions for which no Turing machine can perform the computation?
[DENOMBREMENT Intuitivement, on peut commencer par approcher le problème avec
[COUNTING Intuitively, we can start approaching the problem with
du dénombrement. Si on regarde les machines de Turing possibles, il y en a une infinité,
counting. If we look at possible Turing machines, there are infinitely many,
mais c’est une infinité qu’on appelle dénombrable : on peut numéroter toutes les machines de Turing
but it's an infinity called countable: we can number all Turing machines
possibles, je vous renvoie à ma vidéo sur l’infini si ça ne vous parle pas.
possible, I refer you to my video on infinity if that doesn't ring a bell.
D’un autre côté, les fonctions de N dans N, les trucs qu’on voudrait pouvoir calculer,
On the other hand, functions from N to N, the things we'd want to compute,
on sait qu’il y en a une infinité non-dénombrable. Donc il y en a infiniment plus si j’ose dire. Donc
we know there are uncountably many. So there are infinitely more, if I dare say. So
si les fonctions sont non-dénombrables mais que les machines de Turing le sont,
if functions are uncountable but Turing machines are countable,
intuitivement il doit y avoir plein de fonctions non-calculables. Mais lesquelles ?]
intuitively there must be plenty of non-computable functions. But which ones?]
Pour résoudre cette question, Turing est passé par un chemin détourné. Il s’est d’abord demandé dans
To solve this question, Turing took a roundabout path. He first asked himself
quelles circonstances on avait la certitude qu’une machine de Turing allait s’arrêter.
under what circumstances one was certain that a Turing machine would halt.
Imaginez, j’ai une machine de Turing M, et une entrée n sur
Imagine, I have a Turing machine M, and an input n on
le ruban. Est-ce que je peux savoir à l’avance si la machine va s’arrêter,
the tape. Can I know in advance whether the machine will halt,
une fois lancée ? Ca n’a rien d’évident a priori : on sait que dans la table de transition il y a
once it's running? It's not obvious a priori: we know that in the transition table there are
des instructions qui aboutissent à un arrêt de la machine, mais une machine peut aussi
instructions that lead to the machine stopping, but a machine can also
boucler à l’infini sans jamais tomber sur un état d’arrêt. Mais est-ce qu’on peut savoir
loop forever without ever hitting a halt state. But can we know
à l’avance que si ça va être le cas, rien qu’en observant la table de transition ?
in advance whether that will be the case, just by looking at the transition table?
[HALTING Reformulons un peu le problème : si j’ai une machine M et une entrée n, je peux au
[HALTING Let's rephrase the problem a bit: if I have a machine M and an input n, I can
lieu de cela utiliser une machine universelle U dont l’entrée sera un couple (M,n), où on
instead use a universal machine U whose input will be a pair (M,n), where we
inscrira sur le ruban à la fois l’entrée n et la table de transition de la machine M. Si on
will write on the tape both the input n and the transition table of machine M. If we
fait tourner U sur (M,n) on aura le même résultat que si on fait tourner M sur n, c’est équivalent.
run U on (M,n) we'll get the same result as if we run M on n, it's equivalent.
Donc est-ce que la machine U va s’arrêter sur l’entrée (M,n),
So will machine U halt on input (M,n),
est-ce qu’on peut le savoir à l’avance ? On aimerait bien avant de lancer le calcul !
can we know in advance? We'd like to know before launching the computation!
Idéalement, ce qu’on pourrait imaginer, c’est avoir une autre machine, appelons là H,
Ideally, what we could imagine is having another machine, let's call it H,
qui soit capable quand on lui donne le même ruban qui contient initialement M et n, de nous répondre
that, when given the same tape initially containing M and n, can tell us
si oui ou non, ça va s’arrêter. Attention, on ne demande pas à H de faire le calcul,
whether or not it will halt. Note, we're not asking H to do the computation,
mais juste de nous dire si quand on va faire le calcul avec U, il va s’arrêter.
but just to tell us if when we do the computation with U, it will halt.
Intuitivement on pourrait imaginer que sans faire le calcul explicitement,
Intuitively, we might imagine that without explicitly doing the computation,
la machine H puisse acquérir la certitude que le calcul va s’arrêter,
machine H could gain certainty that the computation will halt,
en analysant la table de transition et le nombre n.]
by analyzing the transition table and the number n.
Eh bien ce que démontre Turing, c’est que la machine H ne peut pas exister.
Well, what Turing demonstrates is that machine H cannot exist.
Il est impossible de construire une machine qui puisse avec certitude prédire systématiquement
It is impossible to build a machine that can with certainty systematically predict
si executer une machine M sur un entier n va s’arrêter, ou bien tourner indéfiniment.
whether running machine M on an integer n will stop, or loop indefinitely.
Et donc ce que montre Turing, c’est qu’il existe effectivement des fonctions non-calculables,
And so what Turing shows is that there actually exist non-computable functions,
il vient d’en construire une. La fonction « est-ce que la machine M appliquée à n va
he has just constructed one. The function "does machine M applied to n
s’arrêter oui ou non» est une fonction qu’on ne peut pas calculer avec une machine de Turing.
stop yes or no" is a function that cannot be computed with a Turing machine.
Je vous épargne la démonstration de Turing, mais comme souvent dans ce genre de problèmes,
I'll spare you Turing's proof, but as often with this kind of problem,
c’est avec un argument diagonal à la Cantor qu’on y arrive. Une astuce auto-référentielle,
it is achieved with a diagonal argument à la Cantor. A self-referential trick,
je vous renvoie à ma vidéo sur le théorème de Gödel.
I refer you to my video on Gödel's theorem.
Alors ok, on a une fonction non-calculable, ça peut paraitre anecdotique mais en fait c’est
So okay, we have a non-computable function, it may seem anecdotal but in fact it is
assez vertigineux : il existe des fonctions que jamais une machine de Turing ne pourra calculer,
quite dizzying: there exist functions that no Turing machine will ever be able to compute,
en tout cas pas pour toutes les entrées n. Et donc si on croit à la thèse de Church-Turing,
at least not for all inputs n. And so if we believe in the Church-Turing thesis,
ce sont des fonctions que rien ni personne ne pourra jamais complètement calculer ! C’est fou !
these are functions that nothing and no one will ever be able to fully compute! It's crazy!
Et pour répondre à une objection courante : oui, ça vaut aussi pour les ordinateurs
And to answer a common objection: yes, this also applies to quantum computers.
quantiques. Un ordinateur quantique n’a pas fondamentalement de capacités différentes
A quantum computer does not fundamentally have different capabilities
d’un ordinateur classique. Il a juste un mode de fonctionnement qui lui permet,
than a classical computer. It just has an operating mode that allows it,
sur certains problèmes et avec certains algorithmes, d’être plus rapide qu’un
on certain problems and with certain algorithms, to be faster than a
ordinateur classique. Mais il n’y a rien de nouveau qu’un ordinateur quantique puisse faire.
classical computer. But there is nothing new that a quantum computer can do.
On peut même simuler un ordinateur quantique avec un ordinateur classique, c’est juste long.
You can even simulate a quantum computer with a classical computer, it's just slow.
Et si la thèse de Church-Turing est vraie, et aujourd’hui on ne voit pas très bien ce
And if the Church-Turing thesis is true, and today we don't quite see what
qui pourrait la mettre en défaut, même avec un ordinateur à gravitons
could put it in doubt, even with a graviton computer
quantique supersymétriques construit par des extra-terrestres dans 1 milliard d’années,
supersymmetric quantum built by aliens in 1 billion years,
il existera toujours des choses incalculables, les mêmes choses qui sont déjà pour nous impossibles à
there will always be incalculable things, the same things that are already impossible for us to
calculer. Ca, et puis aussi évidemment l’amour, le bonheur, la beauté, le QI de Did...
compute. That, and also obviously love, happiness, beauty, and Did's IQ...
Merci d’avoir suivi la vidéo, abonnez-vous tout ça, pour ceux qui voudraient soutenir la chaine,
Thanks for watching the video, subscribe and all that, and for those who want to support the channel,
je rappelle que j’ai aussi un Tipeee et un Patreon, les liens sont en description.
I remind you that I also have a Tipeee and a Patreon, links are in the description.
Et moi je vous dit à très vite pour une nouvelle
And I say see you very soon for a new
vidéo. A bientôt. MINIATURE
video. See you soon. THUMBNAIL
Video and French captions: Les Machines de Turing by ScienceEtonnante. English: machine translation.




