Mes auteurs préférés (David Deutsch, Roger Penrose et Douglas Hofstadter) se penchent tous sur la Thèse de Church-Turing de la Théorie Computationnelle et, plus important encore, sur son interprétation la plus forte: Le Principe de Turing. Dans ce post, je vais d’abord expliquer la thèse de l’Église-Turing en termes profanes.
Lorsque je travaillais sur mon diplôme en informatique, j’ai étudié les machines de Turing et la thèse Church-Turing dans mon cours d’introduction à la Théorie informatique. À l’époque, je pensais que c’était une grosse perte de temps. Je voulais juste programmer des ordinateurs et je ne me souciais pas de ce gars de Turing mort depuis longtemps (ni de ce gars de l’Église) ni de ses stupides machines théoriques.
Maintenant que je comprends les ramifications philosophiques de la Thèse de Church-Turing, j’aurais aimé faire attention en classe! Parce que la Thèse de l’Église-Turing, si elle est vraie, a de profondes ramifications philosophiques et elle pourrait aussi nous dire quelque chose sur la nature profonde — et spéciale — de la réalité.
Automates finis
Tous les textes et classes sur la Théorie du calcul commencent par quelque chose appelé « Automates finis. »L’idée de base derrière eux est assez facile. Vous imaginez une simple « machine » capable de faire des choix et de passer d’un état à l’autre. Voici un exemple très simple qui représente la « logique » d’un tourniquet à pièces.
En clair, cela dit que si vous essayez de pousser à travers un tourniquet verrouillé, vous ne pouvez pas si vous n’avez pas d’abord mis une pièce de monnaie. Si vous avez mis une pièce mais que vous n’avez pas encore poussé, des pièces supplémentaires la laissent simplement dans un état déverrouillé. Si vous avez mis une pièce de monnaie, vous pouvez passer. Il se verrouille ensuite à nouveau pour la personne suivante.
Il était probablement plus facile à comprendre à partir du diagramme que de la description.
Les automates finis sont capables d’exécuter une logique beaucoup plus compliquée que celle-ci. Mais cela devrait vous donner une idée de base du fonctionnement des automates finis.
Une chose à noter est qu’un automate fini, comme celui ci-dessus, est purement théorique car il n’existe que sous la forme d’un tas de bulles et de lignes sur un morceau de papier. Ce n’est pas comme s’il y avait une petite « machine à automates finis » à l’intérieur du tourniquet qui prend ces décisions. Ou peut-être devrais-je plutôt dire que le tourniquet lui-même est la machine à automates finis.
Si nous le voulions vraiment, nous pourrions probablement construire une machine dans la vraie vie qui serait un automate fini.Rien n’empêche quelqu’un de le construire comme une vraie machine dans la vraie vie, puis de l’installer dans le tourniquet. Ce n’est tout simplement pas le moyen le moins cher de le faire.
Ainsi, tout « programme » que vous créez en tant que dessin d’un automate fini peut être transformé en un « calcul » réel qui fonctionne vraiment. L’importance de la différence entre une machine de calcul qui peut réellement exister (comme un Automate fini) et une machine qui n’est qu’hypothétique et qui viole les lois de la physique devient importante en un instant.
Machines plus puissantes
Au fur et à mesure qu’un cours de théorie informatique progresse, les étudiants sont initiés à des « machines » de plus en plus complexes qui sont plus puissantes que les automates finis. Comme le montre la figure de droite, le suivant le plus puissant est l’automate Pushdown (PDA). Un PDA n’est vraiment qu’un DFA avec l’ajout d’une sorte de « mémoire ». Cette mémoire permet à un PDA de créer et d’exécuter des calculs (ou des programmes) qu’un DFA ne peut pas.
Le point clé est seulement qu’il existe certains types de programmes qui peuvent être écrits pour un PDA qui ne peuvent pas être écrits sur un automate fini déterministe (DFA). En d’autres termes, les PDA sont « plus puissants » que les DFA car ils peuvent exprimer des classes de « programmes » que les DFA ne peuvent pas.
Il existe donc une relation entre les DFA et les PDA en termes de « puissance de calcul. »À savoir, il est possible de prouver que tout programme écrit sur un DFA peut également être écrit sur un PDA, mais que l’inverse n’est pas vrai.
La preuve est dans la Preuve
La preuve qu’un PDA peut exécuter tout ce qu’un DFA peut faire en proposant un schéma par lequel la logique d’un DFA peut être mappée à un PDA. Comme un PDA n’est qu’un DFA avec de la mémoire, ce n’est pas difficile à faire — n’utilisez simplement pas la « fonction mémoire ».
Mais qu’en est-il de l’inverse? Peut-on prouver qu’il est impossible de prendre certains types de « programmes » écrits pour un PDA et de les traduire en DFA? C’est-à-dire, existe-t-il une preuve que les automates Pushdown ne peuvent pas être mappés à un Automate fini? Ou supposons-nous simplement qu’un Automate fini est moins puissant qu’un Automate Pushdown parce que nous ne connaissons pas actuellement de moyen de mapper un PDA à un FDA? Peut-être existe-t-il un moyen de mapper les PDA aux FDA et peut-être que personne n’a encore découvert comment le faire? N’est-ce pas au moins une possibilité?
Il s’avère qu’il est possible de prouver qu’un PDA peut exécuter certains types de programmes qu’un DFA ne peut pas. La façon dont vous le feriez est de trouver un calcul (c’est-à-dire un programme) que vous pouvez prouver qu’un DFA ne peut pas calculer, puis démontrer qu’un PDA peut le calculer.
Puissance de calcul d’une machine
Ce fait — qu’il existe des machines logiques plus puissantes (PDA) et moins puissantes (DFA) — est intéressant en soi.
Mais cela conduit à une question philosophique: existe-t-il une telle chose qu’une « machine informatique la plus puissante? »
S’il existait une telle « machine la plus puissante », comment saurions-nous qu’une machine spécifique proposée se trouve être « la plus puissante? »Ou existe-t-il simplement différents types de machines informatiques disponibles et vous devez choisir la bonne pour le travail?
Machines de Turing
Alors quelle machine est plus puissante qu’un PDA?
Comme le veut l’histoire, à peu près au même moment, deux types de « machines » très différents ont été proposés, qui étaient tous deux plus puissants que les PDA.
L’une était la machine de Turing d’Alan Turing. L’autre n’était pas tant une machine qu’un ensemble de notations astucieuses développées par Alonzo Church qui servaient le même but que le développement d’une machine. Parmi ces deux « machines », la machine de Turing est conceptuellement plus facile à enseigner, c’est donc généralement la machine qui est enseignée dans un cours de théorie computationnelle.
Les machines de Turing sont de petites machines théoriques amusantes qui ont une tête de lecture / écriture et une bande de papier (hypothétique) sur laquelle elles peuvent lire ou écrire. Sur la base de ce que lit la machine de Turing, elle place la machine de Turing dans un état d’action qui effectue une sorte de combinaison de tâches consistant à déplacer la tête de lecture / écriture vers l’avant ou vers l’arrière, à lire à partir d’une nouvelle position sur la bande ou à écrire une nouvelle position sur la bande. Une machine de Turing ressemble à ceci:
Machines de Turing et ordinateurs modernes
Une chose intéressante est qu’une Machine de Turing est, malgré les apparences de surface, en fait assez similaire à un ordinateur moderne. Dans un ordinateur moderne, l’Unité centrale de traitement (CPU) est équivalente à la tête de lecture / écriture d’une machine de Turing. Les puces de mémoire (RAM ou ROM) sont très similaires aux cellules de la longue bande de papier sur laquelle la machine à tourner peut lire ou écrire. Les ordinateurs modernes semblent donc à peu près équivalents à une machine de Turing.
Un ordinateur moderne a un avantage sur la machine de Turing. Un ordinateur moderne n’a pas à se déplacer d’une cellule de sa « mémoire » dans un ordre séquentiel comme le fait une machine de Turing.
Le fait qu’une machine de Turing ne puisse déplacer qu’une cellule à la fois semble être une limitation significative, n’est-ce pas? Nous venons de voir à quel point certaines machines sont logiquement « plus puissantes » que d’autres: un PDA peut effectuer des tâches de calcul qu’une FDA ne peut pas effectuer. Alors peut-être y a-t-il des machines plus puissantes que les machines de Turing qui peuvent effectuer des tâches que les machines de Turing ne peuvent pas? Et peut-être que les ordinateurs modernes — en raison de leur capacité à sauter autour de la mémoire plutôt que de devoir se déplacer séquentiellement de cellule en cellule – peuvent exécuter des programmes qu’une machine de Turing ne peut pas?
En fait, les ordinateurs modernes ont en fait moins de pouvoir expressif qu’une machine de Turing en raison du fait que les machines de Turing ont été conçues comme ayant une bande de papier infiniment longue (c’est-à-dire une mémoire infinie) où un ordinateur réel aura toujours une mémoire finie. Cependant, en général, cela fait très peu de différence dans les types de calculs que l’on peut effectuer, car les êtres humains ne sont généralement pas tous intéressés par des calculs infiniment longs qui donnent des résultats infiniment longs. C’est pourquoi je dis que les ordinateurs modernes et les machines de Turing sont « à peu près » équivalents. En fait, tant que vous supposez une taille de mémoire arbitraire mais finie, ils sont exactement équivalents en termes de types de programmes qu’ils peuvent exécuter.
La thèse de Turing de l’Église: Machine de Turing = Puissance Logique Maximale
Mais qu’en est-il du pauvre Alonzo Church? Sa pauvre petite « machine » oubliée car les machines de Turing sont plus faciles à enseigner. Sa machine est-elle peut-être capable d’exprimer des calculs / programmes qu’une machine de Turing ne peut pas, ou vice versa?
Ne serait-ce pas une coïncidence stellaire s’il arrivait qu’Alan Turing et Alonzo Church créent deux types de machines de calcul théoriques entièrement différents et qu’ils soient exactement identiques en termes de types de calculs qu’ils pouvaient effectuer?
Alors imaginez la surprise de tout le monde quand Alan Turing a pu produire une preuve que tout programme écrit pour une machine de Turing pouvait également être écrit pour une machine d’Église et aussi une preuve que tout programme écrit pour une machine d’Église pouvait également être écrit pour une machine de Turing.
En fait, il existe un certain nombre de types de machines de calcul théoriques proposés. Par exemple, les théoriciens ont essayé de permettre à une machine de Turing d’avoir plusieurs bandes avec lesquelles lire / écrire. Ils ont même essayé de permettre à une machine de Turing de lire et d’écrire une « feuille » à 2 dimensions. Les théoriciens ont essayé toutes sortes d’améliorations aux machines de Turing (et aux machines d’Église).
Et jusqu’à présent, il a été possible de produire une preuve pour chacun d’entre eux qu’ils sont équivalents à une simple machine de Turing.
Cela semble être une coïncidence sauvage, n’est-ce pas? Et ce serait une coïncidence sauvage à moins qu’il n’y ait une limite supérieure aux types de calcul pouvant être effectués.
S’il existe une telle limite supérieure, ce ne serait pas du tout un hasard si la Machine de Turing et la Machine Church et toutes les autres machines de calcul proposées ont toutes la même puissance de calcul, car en fait, la raison pour laquelle elles sont toutes équivalentes est que nous avons atteint la limite supérieure de la puissance de calcul.
Mais pouvons—nous prouver qu’il n’y a pas de machine de calcul là—bas – une machine que nous n’avons tout simplement pas encore découverte – qui a la capacité d’effectuer des calculs qu’une machine de Turing ne peut pas?
Comment, exactement, produirions-nous une telle preuve? Le fait est que nous ne pouvons pas prouver qu’il n’y a rien de plus puissant qu’une machine de Turing. Alors, qui sait, peut-être qu’il y en a.
Mais le fait est que nous ne pouvons pas trouver (ou inventer) de telles machines.
Ainsi, après des efforts considérables, essayant et échouant, pour trouver un moyen d’améliorer la puissance des machines de Turing, la Thèse de Church-Turing a finalement été acceptée même si elle n’a pas été prouvée. être vrai. La thèse de Church-Turing dit essentiellement quelque chose comme ceci:
Il n’est pas possible de créer une sorte de machine de calcul capable d’exécuter un programme logique qu’une vieille machine de Turing ne peut pas exécuter.
Ou en d’autres termes:
Les machines de Turing et leurs équivalents sont les types de machines de calcul les plus puissants possibles et il n’y en a pas de plus puissantes que nous ne connaissons tout simplement pas encore.
Après des années et des années de recherche sur cette Thèse, cette Thèse tient toujours. Nous verrons plus tard qu’il y a eu une modification de la Thèse avec l’introduction des ordinateurs quantiques théoriques. Mais, fondamentalement, la thèse est toujours vraie aujourd’hui. Personne n’a jamais trouvé un moyen de surpasser les machines de Turing en matière d’expressivité logique. Les machines de Turing sont toujours les championnes en titre.
Alors maintenant vous comprenez la thèse de Church-Turing. Cependant, la thèse Church-Turing n’est pas vraiment tout à fait équivalente au principe de Turing. Donc, dans un futur post, je développerai quelle est la différence et quelles sont ses ramifications philosophiques.
Note
Le principe de Turing. Ainsi nommé par Roger Penrose, qui n’y croit pas (du moins pas sous sa forme actuelle). Il a été développé dans le principe Turing-Deutsch par David Deutsch, qui y croit, du moins dans sa forme.) (Voir l’article dans Wikipedia pour plus de détails)