"La machine la plus importante jamais construite", Alan Turing et la Machine de Turing

Le calcul est un concept familier que la plupart d'entre nous comprennent intuitivement. Prenons comme exemple la fonction f (x) = x + 3. Lorsque x vaut 3, f (3) = 3 + 3. La réponse est 6, très simple. Évidemment, cette fonction est calculable. Mais certaines fonctions ne sont pas si simples, et déterminer si elles peuvent être calculées n’est pas trivial, ce qui signifie qu’elles ne mèneront peut-être jamais à une réponse définitive.

En 1928, les mathématiciens allemands David Hilbert et Wilhelm Ackermann ont proposé un problème appelé Entscheidungsproblem (c'est-à-dire le « problème de détermination »). Au fil du temps, la question qu’ils se posaient conduirait à une définition formelle de la calculabilité, une définition qui permettrait aux mathématiciens de répondre à une multitude de nouvelles questions et de jeter les bases de l’informatique théorique.

Cette définition a été proposée par un étudiant diplômé de 23 ans nommé Alan Turing, qui a écrit un article fondateur en 1936 qui non seulement introduisait le concept d'informatique, mais aussi formellement exprimé et prouvé un problème fondamental en mathématiques, créant une base de connaissances pour l’invention des ordinateurs électroniques. La grande vision de Turing était de fournir des réponses concrètes aux problèmes informatiques sous la forme d'une machine abstraite, qui fut plus tard baptisée machine de Turing par son directeur de thèse, Alonzo Church.

Une machine de Turing est abstraite car elle n'existe pas (et ne peut pas) exister physiquement en tant qu'appareil tangible. Il s’agit plutôt d’un modèle conceptuel de calcul : si cette machine peut calculer une fonction, alors la fonction est calculable.

# 🎜 🎜#Quand Alan Turing a inventé la machine de Turing en 1936, il a également créé l'informatique moderne.

Alan Turing et sa machine de Turing

Ça fonctionne comme ça : Une machine de Turing peut lire et changer symboles sur une bande infiniment longue comme dicté par un tableau de règles. La bande est composée de « cellules » et chaque cellule ne peut stocker qu’un seul symbole. Les machines de Turing utilisent des têtes de bande pour lire et réécrire le contenu des cellules. Chaque règle du tableau de règles détermine ce que la machine de Turing doit faire en fonction de son état actuel et du symbole qu'elle lit. Une machine de Turing peut entrer dans un état final (un « état d'acceptation » ou un « état de rejet ») en fonction de l'endroit où elle s'est arrêtée, en décidant d'accepter ou de rejeter l'entrée. Ou bien une machine de Turing reste coincée dans une boucle infinie et ne cesse de lire la bande.

La meilleure façon de comprendre une machine de Turing est de penser à un exemple simple comme celui-ci. Imaginons qu'une machine de Turing soit conçue pour nous dire si une entrée donnée est le nombre zéro. Nous entrerons le numéro 0001 avec un espace (#), ce qui signifie que "#0001#" est la partie pertinente de notre bande.

La machine de Turing démarre à partir d'un état initial, appelons-le q0, où elle lit la cellule la plus à gauche de la bande et trouve une zone vide. En règle générale, dans l'état q0, si le signe est #, laissez-le tel quel, puis déplacez une cellule vers la droite et changez l'état de la machine en q1. Après cette étape, la machine est dans l'état q1 et sa tête va lire le deuxième symbole 0.

Maintenant, nous recherchons les règles qui s'appliquent à ces conditions. Nous trouvons une règle qui dit : "Conservez l'état q1 et déplacez la tête d'une cellule vers la droite." Cela nous laisse dans la même position (dans l'état q1, la lecture est toujours 0), nous continuons donc à nous déplacer vers la droite jusqu'à ce que la tête soit affichée. enfin, un autre numéro 1 est lu.

Lorsque nous avons consulté à nouveau la table de règles, nous avons trouvé une nouvelle règle : "Si 1 est rencontré, transition vers q2, qui est l'état de rejet." arrêté Exécutez-le et répondez « Non » à la question initiale « 0001 est-il zéro ?

En revanche, si l'entrée est "#0000#", la machine de Turing rencontrera # après tous ces zéros. Lorsque nous consultons la table de règles, nous trouvons une règle qui dit que cela signifie que la machine entre dans l'état q3, un état « d'acceptation ». La machine répond désormais « oui » à la question « « 0000 » est-il nul ?

Alan Turing a aidé à définir le calcul, les algorithmes et les machines de Turing.

Répondre aux questions de jugement avec des machines abstraites

Turing a utilisé sa machine abstraite pour construire un modèle informatique pour répondre au problème Entscheidungs ​​​​​​, qui demande formellement : étant donné un ensemble d'axiomes mathématiques, s'il existe un processus mécanique ( C'est-à-dire un ensemble d'instructions, nous l'appellerions aujourd'hui un algorithme) qui peut toujours déterminer si une affirmation donnée est vraie ?

Supposons que nous voulions trouver un algorithme pour nous dire si la position des pièces dans un certain jeu d'échecs est réalisable. Dans ce cadre, les axiomes sont les règles qui régissent les mouvements raisonnables aux échecs. Pouvons-nous y parvenir en suivant une séquence finie de processus étape par étape ? Bien que l'analyse de certaines positions d'échecs puisse prendre plus de temps que notre vie, un algorithme peut générer toutes les positions possibles et les comparer une par une à l'entrée, de tels algorithmes existent dans le jeu d'échecs. Par conséquent, nous disons que les échecs sont « décidables ».

Cependant, en 1936, les mathématiciens américains Church et Turing ont utilisé différentes méthodes pour prouver qu '«il n'existe pas de méthode générale capable de résoudre tous les exemples du problème Entscheidungs ​​​​Par exemple, certains jeux tels que Game of de John Conway». La vie est indécidable : aucun algorithme ne peut déterminer si un certain modèle émergera du modèle initial.

Turing a montré qu'une fonction est calculable s'il existe un algorithme capable d'effectuer la tâche requise. Parallèlement, il a également montré que l’algorithme est un processus pouvant être défini par une machine de Turing. Par conséquent, une fonction calculable est une fonction qui peut être calculée par une machine de Turing. Cela semble être une manière détournée de définir la calculabilité, mais c'est la meilleure que nous ayons.

Michael Sipser, informaticien théoricien au MIT, a déclaré : « Ce n'est pas que vous puissiez choisir de le définir d'une autre manière. Je pense que les gens s'accordent généralement sur le fait que la thèse de Church-Turing propose que les algorithmes soient le concept informel de n'importe quel modèle de calcul raisonnable peut faire. D'autres mathématiciens ont proposé différents modèles de calcul qui, bien que superficiellement différents, sont en réalité les mêmes : ils peuvent faire ce qu'une machine de Turing peut faire et vice versa.

Quelques années seulement après que le philosophe, logicien et mathématicien Kurt Gödel ait montré que les mathématiques sont incomplètes, Church et Turing ont également montré que certains problèmes mathématiques avec cette feuille de travail sont indécidables. Aussi complexe que soit l’algorithme, il ne peut pas nous dire si la réponse est oui ou non. Les deux événements furent des coups dévastateurs pour Hilbert, qui avait espéré que les mathématiques fourniraient des réponses simples et idéalisées. Mais ce n'est pas mal : s'il existait une solution générale au problème de l'Entscheidungs, cela signifierait que tous les problèmes mathématiques pourraient être réduits à de simples calculs mécaniques.

Machines de Turing universelles et probabilistes

En plus de répondre à ces questions fondamentales, les machines de Turing ont également directement influencé le développement des ordinateurs modernes à travers une variante appelée Machine de Turing universelle. Il s'agit d'une machine de Turing spéciale qui peut simuler n'importe quelle entrée de n'importe quelle autre machine de Turing. Il pourrait lire les descriptions (ainsi que les règles et les bandes d'entrée) d'autres machines de Turing et simuler leur comportement sur ses propres bandes d'entrée, produisant ainsi la même sortie que la machine simulée, tout comme les ordinateurs d'aujourd'hui peuvent lire n'importe quel programme et l'exécuter de la même manière.

En 1945, le mathématicien, informaticien et physicien hongro-américain John von Neumann a proposé une architecture informatique : l'architecture von Neumann, qui a transformé le concept d'une machine de Turing universelle en machines réelles devenues possibles.

Lorsque Sanjeev Arora, informaticien théoricien à l'Université de Princeton, enseigne ce concept, il met l'accent sur une vision philosophique plus large. Il a dit : "Il existe deux concepts d'universel. L'un est qu'il peut faire fonctionner n'importe quelle autre machine de Turing, mais l'autre concept plus important est qu'il peut exécuter n'importe quel calcul que vous proposez dans l'univers. " tout processus physique peut être modélisé ou simulé à l'aide d'algorithmes, et les algorithmes peuvent être simulés par des machines de Turing.

Une autre variante remarquable et de plus en plus utile est la machine probabiliste de Turing. Contrairement aux machines de Turing conventionnelles, qui ont des réponses bien définies à chaque entrée, les machines de Turing probabilistes peuvent générer plusieurs réponses basées sur des probabilités. Cela signifie qu’il peut produire des résultats différents pour la même entrée à différents moments. Il est également surprenant que pour certains problèmes, cette stratégie probabiliste soit plus efficace qu'une approche purement déterministe. Le concept de machines probabilistes de Turing s'est avéré très utile dans des domaines tels que l'optimisation et l'apprentissage automatique.

Ces machines abstraites sont peut-être la meilleure preuve que poser des questions fondamentales peut être l'une des choses les plus utiles qu'un scientifique puisse faire.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!