1
00:00:35,000 --> 00:00:37,005
 Ceci est la machine A.  

2
00:00:38,000 --> 00:00:42,000
 Elle effectue des calculs arithmétiques. 

3
00:00:42,005 --> 00:00:46,813
 Elle reçoit un problème écrit sur support papier, 

4
00:00:47,005 --> 00:00:50,005
 et elle imprime la réponse. 

5
00:00:51,000 --> 00:00:55,000
 Elle imprime toujours la bonne réponse. 

6
00:00:59,008 --> 00:01:01,010
 Voici une autre machine, C. 

7
00:01:02,002 --> 00:01:06,002
 C joue aux dames ("Checkers" en Anglais). 

8
00:01:07,000 --> 00:01:10,000
 Elle reçoit l'état actuel du plateau de jeu 

9
00:01:10,015 --> 00:01:14,050
 et imprime comment il faut déplacer l'une des pièces rouges. 

10
00:01:15,000 --> 00:01:20,000
 C joue aux dames si bien qu'elle ne perdra jamais une partie. 

11
00:01:22,005 --> 00:01:25,014
 A et C sont des machines que nous pouvons déjà construire aujourd'hui, 

12
00:01:26,006 --> 00:01:28,010
 et les ordinateurs sont de plus en plus intelligents. 

13
00:01:29,002 --> 00:01:33,005
 Mais vont-ils fini par être en mesure de tout faire? 

14
00:01:53,000 --> 00:01:56,002
 Par exemple la première machine peut-elle jouer aux dames ? 

15
00:01:56,004 --> 00:01:59,004
 Non, A n'a pas été conçue pour gérer ce type d'entrée, 

16
00:01:59,005 --> 00:02:02,014
 et quand elle essaie de le traiter, ça bogue : elle ne s'arrête pas, elle boucle. 

17
00:02:03,005 --> 00:02:08,010
 La même chose arrive à C lorsqu'elle est alimentée par une addition. 

18
00:02:14,008 --> 00:02:17,010
 En examinant A, nous obtenons sa notice détaillée

19
00:02:20,002 --> 00:02:25,010
 qui définit parfaitement comment fonctionne A. 

20
00:02:29,005 --> 00:02:34,012
 Nous sommes maintenant enfin prêt à introduire une machine extraordinaire appelée H. 

21
00:02:34,005 --> 00:02:37,010
 H résout le problème de l'arrêt (ou de la halte) : 

22
00:02:37,055 --> 00:02:39,950
 H peut analyser la notice d'une autre machine, 

23
00:02:40,006 --> 00:02:45,008
 et déterminer les entrées pour lesquelles elle va s'arrêter, et celles pour lesquelles elle va boucler. 

24
00:02:45,009 --> 00:02:47,918
 Elle reçoit la notice de la machine à tester, 

25
00:02:48,009 --> 00:02:50,910
 et une entrée pour tester avec. 

26
00:02:51,008 --> 00:02:55,015
 A partir de la notice donnée en entrée, H simule la machine correspondante, 

27
00:02:56,008 --> 00:03:03,908
 et détermine alors si ça boucle ou non. 
"Not stuck" = "ne boucle pas"
"Stuck" = "boucle"

28
00:03:04,003 --> 00:03:07,003
 H résout parfaitement le problème de l'arrêt. 

29
00:03:07,004 --> 00:03:10,005
 H imprime toujours la bonne réponse. 

30
00:03:15,004 --> 00:03:20,004
 Voici deux autres exemples avec la notice de la machine qui trouve les meilleurs coups aux dames. 

31
00:03:40,005 --> 00:03:44,910
 H est une belle machine, mais peut-on vraiment la construire? 

32
00:03:45,005 --> 00:03:47,980
 Nous allons maintenant prouver que son existence même 

33
00:03:48,035 --> 00:03:54,130
 est logiquement impossible. 

34
00:04:13,004 --> 00:04:16,010
 Supposons que H existe. 

35
00:04:19,000 --> 00:04:23,009
 Nous la placerons sur ici pour des raisons qui seront plus claires dans une minute. 

36
00:04:24,000 --> 00:04:27,008
 Rappelons que nous supposons H résout parfaitement le problème de l'arrêt: 

37
00:04:27,009 --> 00:04:29,012
 H imprime toujours la bonne réponse. 

38
00:04:30,003 --> 00:04:32,010
 Nous sommes sur le point de mettre cette hypothèse à l'épreuve. 

39
00:04:33,002 --> 00:04:40,002
 Voici la machine P qui est une machine à photocopier. Elle imprime simplement deux exemplaires de son entrée. 

40
00:04:42,000 --> 00:04:45,000
 Nous allons la placer avant H. 

41
00:04:46,005 --> 00:04:51,508
 Voici une autre machine simple. Nous l'appelons le Négateur. 

42
00:04:52,000 --> 00:04:57,004
 Lorsque le Négateur reçoit les mots "ne boucle pas" en entrée, le Négateur se met à boucler lui-même. 

43
00:04:57,005 --> 00:05:00,912
 Et quand il reçoit «boucle», il s'arrête 

44
00:05:01,005 --> 00:05:04,005
 et imprime un sourire. 

45
00:05:06,005 --> 00:05:09,005
 Nous le placerons après H. 

46
00:05:17,008 --> 00:05:21,010
 Regroupons le tout dans un emballage soigné que nous appelons la machine X. 

47
00:05:22,005 --> 00:05:25,010
 X possède une entrée et une sortie. 

48
00:05:26,005 --> 00:05:29,005
 Examinons X pour obtenir sa notice détaillée. 

49
00:05:31,005 --> 00:05:36,005
 Comme précédemment, cette notice définit entièrement X. 

50
00:05:37,005 --> 00:05:41,060
 Que pensez-vous qui va se passer si nous alimentons X avec sa propre notice ? 

51
00:05:42,025 --> 00:05:45,100
 X va-t-elle boucler ou s'arrêter ? Voyons. 

52
00:05:49,005 --> 00:05:52,005
 D'abord P duplique tout simplement notre entrée. 

53
00:05:53,000 --> 00:05:56,005
 Donc H reçoit deux exemplaires de la notice de X. 

54
00:05:56,008 --> 00:06:01,010
 Il faut maintenant déterminer le résultat de H. 

55
00:06:01,025 --> 00:06:07,511
 Supposons que H renvoie "ne boucle pas" pour la machine X sur l'entrée X. 

56
00:06:08,008 --> 00:06:12,010
 La négateur N nie cela, et donc se met à boucler. 

57
00:06:12,020 --> 00:06:17,004
 En résumé, alimenter X avec sa propre notice l'amène à boucler. 

58
00:06:17,005 --> 00:06:21,910
 Mais, paradoxalement, H a dit que X ne bouclerait pas. H avait donc tort. 

59
00:06:22,000 --> 00:06:25,000
 Essayons encore. 

60
00:06:28,003 --> 00:06:35,010
 Cette fois, supposons que H renvoie «boucle» pour la machine X sur l'entrée X. 

61
00:06:37,000 --> 00:06:49,005
 Sur l'entrée "boucle", le négateur s'arrête. 
 Donc, globalement, X s'arrête sur l'entrée X, ce qui contredit le fait que H a dit qu'elle bouclerait. 

62
00:06:50,000 --> 00:06:52,003
 En résumé, H a de nouveau tort. 

63
00:06:52,005 --> 00:06:54,010
 Mais H est censée avoir toujours raison. . . 

64
00:06:55,025 --> 00:06:59,100
 C'est une contradiction qui prouve que H ne peut exister.