Turing Machines Explained

C229 minScienceEtonnante

[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

  1. [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.

  2. Il est principalement utilisé pour le programme d’armement nucléaire américain,

    It's mainly used for the US nuclear weapons program,

  3. 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

  4. 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.]

  5. Et pourtant, en un certain sens, ce super calculateur, El Capitan,

    And yet, in a certain sense, this supercomputer, El Capitan,

  6. n’est pas fondamentalement différent de l’appareil sur lequel vous êtes

    is not fundamentally different from the device you're

  7. 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.

  8. 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.

  9. 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

  10. smartphone pourraient les résoudre aussi, si on leur laissait suffisamment de temps.

    smartphone could solve them too, if given enough time.

  11. 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

  12. civilisation extra-terrestre super avancée ne possèdera jamais d’ordinateurs qui soient

    super-advanced extraterrestrial civilization will never have computers that are

  13. très différents des nôtres, des ordinateurs qui seraient capables

    very different from ours, computers that would be able

  14. 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.

  15. Oui oui, même si les aliens ont des giga-ordinateurs à

    Yes yes, even if aliens have giga-computers with

  16. gravitons quantiques supersymétriques. Ces ordinateurs seront peut-être plus rapides,

    supersymmetric quantum gravitons. Those computers might be faster,

  17. mais il ne disposeront pas de capacités nouvelles par rapport aux nôtres.

    but they won't have new capabilities compared to ours.

  18. 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,

  19. 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

  20. 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

  21. 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.

  22. [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,"

  23. 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

  24. pendant la seconde guerre mondiale a cassé le codes secrets des nazis,

    during World War II cracked the Nazis' secret codes,

  25. donnant ainsi un avantage déterminant aux alliés.]

    giving the Allies a decisive advantage.]

  26. 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

  27. a inventé ce concept qu’on appelle maintenant « les machines de Turing ». Bizarrement,

    invented the concept we now call "Turing machines." Oddly enough,

  28. 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

  29. 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!

  30. 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

  31. 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.

  32. [jingle]

    [jingle]

  33. Pour parler des capacités des ordinateurs,

    To talk about computers' capabilities,

  34. 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,

  35. 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.

  36. [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,

  37. 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,

  38. qui sont numériques elles aussi. Bien sûr,

    which are numerical too. Of course,

  39. 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

  40. 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.]

  41. 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

  42. 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.

  43. [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

  44. 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.

  45. 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

  46. 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).]

  47. Calculer des fonctions sur les nombres entiers, c’est ce que faisaient déjà

    Calculating functions on integers is what mechanical calculating machines

  48. 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:

  49. un ordinateur aujourd’hui : il calcule le résultat de fonctions très compliquées.

    it calculates the result of very complicated functions.

  50. 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

  51. 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,

  52. 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,

  53. telles qu’un ordinateur pourra calculer sa valeur pour n’importe quel n ?

    such that a computer can calculate its value for any n?

  54. [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,

  55. 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

  56. la calcule, et ce pour n’importe quelle valeur de n. Et ça marche

    calculates it, for any value of n. And it works

  57. aussi si je prends une fonction de N beaucoup plus compliquée.]

    too if I take a much more complicated function from N.]

  58. 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,

  59. 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.

  60. 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.

  61. 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

  62. 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

  63. 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.

  64. 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,

  65. et dont ça n’est pas évident a priori qu’elles soient calculables.

    and it’s not obvious a priori that they are computable.

  66. [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

  67. 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

  68. 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

  69. 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.

  70. 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

  71. 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

  72. 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

  73. 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.]

  74. 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

  75. 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

  76. 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.

  77. Je pourrais vous parler du lambda-calcul de Church,

    I could tell you about Church’s lambda calculus,

  78. 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,

  79. 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,

  80. 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

  81. 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?

  82. [jingle]

    [jingle]

  83. 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,

  84. 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,

  85. 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.

  86. [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

  87. 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,

  88. ç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

  89. 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

  90. 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.

  91. 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

  92. 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

  93. 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.

  94. 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.

  95. Si on veut définir sans ambiguïté le comportement de notre machine,

    If we want to define unambiguously the behavior of our machine,

  96. 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

  97. 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

  98. 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

  99. 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.

  100. Voici un exemple d’une liste d’instructions de ce genre,

    Here's an example of such a list of instructions,

  101. 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,

  102. 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,

  103. 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.

  104. 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

  105. 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

  106. 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,

  107. 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.

  108. Aucune réflexion à produire, aucune initiative à prendre : c’est mécanique.

    No thinking needed, no initiative to take: it's mechanical.

  109. On pourrait s’amuser à construire ou plutôt à simuler des machines

    We could have fun building or rather simulating machines

  110. 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,

  111. 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,

  112. 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

  113. 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

  114. 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.

  115. 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

  116. 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,

  117. a ajouté un ingrédient supplémentaire : un état interne de la machine.

    added an extra ingredient: an internal state of the machine.

  118. 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

  119. 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.

  120. 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,

  121. 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.

  122. 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

  123. 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

  124. 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

  125. 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

  126. 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.

  127. 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,

  128. 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,

  129. 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.]

  130. 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,

  131. 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

  132. bien en train d’effectuer un calcul mécanique, appliquer un algorithme,

    indeed performing a mechanical computation, applying an algorithm,

  133. 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.

  134. 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

  135. 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

  136. 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

  137. é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.

  138. 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,

  139. 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.

  140. [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

  141. 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

  142. 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.

  143. 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,

  144. en laissant le chiffre inchangé, jusqu’à tomber sur une case blanche,

    leaving the digit unchanged, until we hit a blank cell,

  145. 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.

  146. 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,

  147. 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,

  148. 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.

  149. 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

  150. 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,

  151. 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.

  152. 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

  153. 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.

  154. 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

  155. 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.

  156. 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,

  157. 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,

  158. 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.

  159. 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

  160. 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'.

  161. Mais personne ne construit jamais vraiment des machines de Turing telles quelles,

    But nobody ever really builds Turing machines as such,

  162. Turing lui même n’a pas essayé d’en fabriquer.

    Turing himself didn't try to build one.

  163. 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

  164. 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

  165. 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

  166. 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.

  167. 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

  168. 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,

  169. 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

  170. 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.

  171. 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

  172. 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

  173. 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

  174. 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.

  175. 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

  176. 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

  177. 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

  178. 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,

  179. 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

  180. 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.

  181. Ici on peut voir la machine en action sur le ruban,

    Here you can see the machine in action on the tape,

  182. 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

  183. 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.

  184. [jingle]

    [jingle]

  185. 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,

  186. 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.

  187. Avec son concept, Turing propose en fait une définition formelle,

    With his concept, Turing actually proposes a formal definition,

  188. mathématique, pour la notion un peu floue de « truc calculable ».

    mathematical, for the somewhat fuzzy notion of 'computable thing'.

  189. 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

  190. 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

  191. 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

  192. avec les machines est en fait mathématiquement équivalente à la définition de Church.

    with machines is actually mathematically equivalent to Church's definition.

  193. 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

  194. de la notion de calcul, mais à chaque fois aboutissant à quelque

    the notion of computation, but each time resulting in something

  195. chose d’équivalent à ce qu’avaient déjà proposé respectivement Church et Turing.

    equivalent to what Church and Turing had respectively already proposed.

  196. 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,

  197. 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.

  198. Et on appelle cela « la thèse de Church-Turing ».

    And that's called 'the Church-Turing thesis'.

  199. 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,

  200. ç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,

  201. 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,

  202. sont exactement ceux qui sont faisables avec les machines de Turing.

    are exactly those feasible with Turing machines.

  203. 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

  204. 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

  205. 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.

  206. 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.

  207. 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,

  208. si vous voulez réaliser deux types de calculs complètement différents,

    if you want to perform two completely different types of computations,

  209. il vous faut carrément changer de machine.

    you literally have to change machines.

  210. 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,

  211. 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,

  212. 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.

  213. 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

  214. 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

  215. 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

  216. machine spécifiquement pour ce calcul. Une fonction calculable = une machine de Turing.

    machine specifically for that computation. One computable function = one Turing machine.

  217. [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

  218. 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

  219. 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

  220. 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.]

  221. 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

  222. 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,

  223. 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?

  224. Eh bien Turing avait déjà envisagé la question ! Dès son article de

    Well, Turing had already considered the question! From his paper

  225. 1936 définissant la notion de machine de Turing,

    from 1936 defining the notion of the Turing machine,

  226. 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.

  227. [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,

  228. c’est comme appliquer une certaine fonction F sur un nombre entier n.

    is like applying a certain function F to an integer n.

  229. 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

  230. 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.

  231. 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

  232. 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.

  233. 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,

  234. 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

  235. 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,

  236. 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.]

  237. Eh bien dans son article de 1936, Turing prouve que ces

    Well, in his 1936 paper, Turing proves that these

  238. machines existent. Qu’il est possible d’utiliser une machine universelle,

    machines exist. That it's possible to use a universal machine,

  239. 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,

  240. il invente de façon abstraite le concept d’ordinateur universellement programmable.

    he abstractly invents the concept of the universally programmable computer.

  241. 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,

  242. qui a été achevé seulement en 1946,

    which was only completed in 1946,

  243. 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.

  244. 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,

  245. mais on sait en construire explicitement un certain nombre.

    but we know how to build a certain number of them explicitly.

  246. 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,

  247. 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

  248. 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

  249. 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,

  250. 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.

  251. 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,

  252. 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.

  253. 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

  254. 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,

  255. 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,

  256. 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.

  257. 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

  258. ç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

  259. 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

  260. processeur. On utilise une couche intermédiaire qui s’appelle un langage de programmation.

    processor. We use an intermediate layer called a programming language.

  261. La plupart des langages de programmation permettent effectivement de faire en

    Most programming languages do indeed allow

  262. sorte que notre ordinateur se comporte comme une machine de Turing universelle,

    our computer to behave like a universal Turing machine,

  263. on dit de ces langages qu’ils sont « Turing-complets ».

    These languages are said to be “Turing-complete”.

  264. 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:

  265. 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!

  266. [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

  267. 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

  268. la redstone dans Minecraft, vous pouvez simuler une machine de Turing universelle.

    redstone in Minecraft, you can simulate a universal Turing machine.

  269. 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,

  270. 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.]

  271. 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

  272. 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

  273. super-ordinateur El Capitan du point de vue de ses capacités de calcul.

    El Capitan supercomputer in terms of its computing capabilities.

  274. 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,

  275. 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

  276. vont y passer respectivement. Du point de vue des capacités fondamentales à calculer,

    spend on it respectively. From the standpoint of fundamental computing abilities,

  277. 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.

  278. 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

  279. de Turing capture exactement l’ensemble de ce qui est physiquement calculable,

    machine captures exactly everything that is physically computable,

  280. 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

  281. possède des capacités fondamentalement supérieures aux machines actuelles.

    possess fundamentally superior capabilities to current machines.

  282. Quelle que soit la technologie utilisée,

    Whatever the technology used,

  283. même un ordinateur quantique ou une technologie extra-terrestre inconnue.

    even a quantum computer or unknown extraterrestrial technology.

  284. Tout ce qui est physiquement calculable l’est déjà avec nos machines actuelles,

    Anything physically computable is already computable with our current machines,

  285. 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.

  286. 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,

  287. 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

  288. 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,

  289. 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.

  290. On l’a dit plus haut, faire un calcul, c’est en gros utiliser

    As mentioned earlier, computing is basically using

  291. un procédé mécanique qui permet d’obtenir la valeur d’une fonction,

    a mechanical process to get the value of a function,

  292. 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,

  293. 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

  294. fonctions pour lesquelles aucune machine de Turing ne peut réaliser le calcul ?

    functions for which no Turing machine can perform the computation?

  295. [DENOMBREMENT Intuitivement, on peut commencer par approcher le problème avec

    [COUNTING Intuitively, we can start approaching the problem with

  296. 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,

  297. 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

  298. 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.

  299. 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,

  300. 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

  301. si les fonctions sont non-dénombrables mais que les machines de Turing le sont,

    if functions are uncountable but Turing machines are countable,

  302. intuitivement il doit y avoir plein de fonctions non-calculables. Mais lesquelles ?]

    intuitively there must be plenty of non-computable functions. But which ones?]

  303. 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

  304. 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.

  305. 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

  306. 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,

  307. 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

  308. 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

  309. 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

  310. à 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?

  311. [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

  312. 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

  313. 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

  314. 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.

  315. 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),

  316. 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!

  317. 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,

  318. 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

  319. 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,

  320. 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.

  321. Intuitivement on pourrait imaginer que sans faire le calcul explicitement,

    Intuitively, we might imagine that without explicitly doing the computation,

  322. 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,

  323. en analysant la table de transition et le nombre n.]

    by analyzing the transition table and the number n.

  324. 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.

  325. 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

  326. 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.

  327. 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,

  328. 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

  329. 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.

  330. 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,

  331. 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,

  332. 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.

  333. 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

  334. 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,

  335. 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,

  336. 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!

  337. 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.

  338. quantiques. Un ordinateur quantique n’a pas fondamentalement de capacités différentes

    A quantum computer does not fundamentally have different capabilities

  339. 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,

  340. 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

  341. 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.

  342. 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.

  343. 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

  344. qui pourrait la mettre en défaut, même avec un ordinateur à gravitons

    could put it in doubt, even with a graviton computer

  345. quantique supersymétriques construit par des extra-terrestres dans 1 milliard d’années,

    supersymmetric quantum built by aliens in 1 billion years,

  346. 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

  347. 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...

  348. 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,

  349. 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.

  350. Et moi je vous dit à très vite pour une nouvelle

    And I say see you very soon for a new

  351. vidéo. A bientôt. MINIATURE

    video. See you soon. THUMBNAIL

Video and French captions: Les Machines de Turing by ScienceEtonnante. English: machine translation.

Words at C2

More C2 videos

Help me keep building French Atlas

If this site has helped you study, your support helps me keep improving it.