Pourquoi la machine de Turing est-elle un modèle de calcul populaire?

Je suis un étudiant de premier cycle en CS. Je comprends comment Turing a créé sa machine abstraite (modéliser une personne effectuant un calcul), mais cela me semble être une abstraction maladroite et inélégante. Pourquoi considérons-nous une "bande" et une tête de machine écrivant des symboles, changeant d'état, déplaçant la bande d'avant en arrière?

Quelle est la signification sous-jacente? Un DFA est élégant - il semble capturer précisément ce qui est nécessaire pour reconnaître les langages normaux. Mais la machine de Turing, à mon avis de novice, n’est qu’un gadget abstrait maladroit.

Après réflexion, je pense que le modèle de calcul le plus idéalisé serait de dire qu'un système physique correspondant à la chaîne en entrée, après avoir été mis en mouvement, atteindrait un équilibre statique qui, une interprétation équivalente à celle utilisée pour former le système de la chaîne d'origine correspondrait à la chaîne de sortie correcte. Cela rend compte de la notion d '"automatisation", car le système changerait de manière déterministe uniquement en fonction de l'état d'origine.

Modifier :

Après avoir lu quelques réponses, j'ai compris que ce qui me dérange dans la machine de Turing, c'est qu'elle ne semble pas minimale. Le modèle de calcul canonique ne devrait-il évidemment pas transmettre l'essence de la calculabilité?

De plus, au cas où ce ne serait pas clair, je sais que les DFA ne sont pas des modèles complets de calcul.

Merci pour les réponses.

Eh bien, un DFA n’est qu’une machine de Turing qui n’a le droit que de se déplacer vers la droite et qui doit accepter ou refuser dès qu’il n’ya plus de caractères saisis. Je ne suis donc pas sûr que l’on puisse dire qu’un DFA est naturel, mais pas une machine de Turing.

Mis à part la critique de la question, rappelez-vous que Turing travaillait avant même que les ordinateurs n'existent. En tant que tel, il n'essayait pas de codifier ce que font les ordinateurs électroniques, mais plutôt le calcul en général. Mes parents ont un dictionnaire des années 1930 qui définit l'ordinateur comme "quelqu'un qui calcule" et c'est en gros de là que Turing était originaire: pour lui, à ce moment-là, le calcul était basé sur des règles de calcul, des tables de journal, des crayons et des bouts de papier. Dans cet état d'esprit, réécrire les symboles sur du ruban adhésif ne semble pas être une mauvaise abstraction.

OK, d'accord, vous dites (j'espère!), Mais nous ne sommes plus dans les années 1930, alors pourquoi utilisons-nous encore cela? Ici, je ne pense pas qu'il y ait une raison spécifique. L'avantage des machines Turing est qu'elles sont relativement simples et que nous sommes assez doués pour prouver des choses à leur sujet. Bien que formellement spécifier un programme de machine de Turing pour effectuer une tâche particulière soit très fastidieux, une fois que vous l'avez fait plusieurs fois, vous avez une intuition raisonnable sur ce qu'ils peuvent faire et vous n'avez plus besoin d'écrire les spécifications formelles. Le modèle est également facilement étendu à d’autres caractéristiques naturelles, telles que l’accès aléatoire à la bande. Ils constituent donc un modèle très utile que nous comprenons bien et nous comprenons également très bien leur rapport aux ordinateurs.

On pourrait utiliser d'autres modèles, mais il faudrait alors énormément faire la traduction entre les résultats du nouveau modèle et le vaste corpus de travaux existants sur ce que les machines de Turing peuvent faire. Personne n'a proposé de remplacement pour les machines Turing qui ont eu suffisamment d'avantages pour que cela paraisse être une bonne idée.

Vous posez plusieurs questions différentes. Permettez-moi de leur répondre brièvement un à un.

Qu'est-ce qui est si important dans le modèle de machine de Turing?

$\lambda$

À l'époque, la tentative de Turing de définir la calculabilité semblait la plus satisfaisante. Il s'est finalement avéré que tous les modèles de calcul décrits ci-dessus sont équivalents - ils décrivent tous la même notion de calculabilité. Pour des raisons historiques, le modèle de Turing est apparu comme le moyen le plus canonique de définir la calculabilité. Le modèle est également très rudimentaire et facile à utiliser, comparé à de nombreux autres modèles, y compris ceux énumérés ci-dessus.

La science informatique habituelle enseigne les machines de Turing comme définition de la calculabilité, puis les utilise également pour explorer la théorie de la complexité. Mais les algorithmes sont analysés par rapport à un modèle plus réaliste connu sous le nom de machine à RAM, bien que cette question soit généralement cachée sous le tapis comme un secret pour le cognoscenti.

Les DFA ne sont-ils pas un meilleur modèle?

Telle était la motivation originelle du célèbre papier de Rabin et Scott, Finite Automata, et de leurs problèmes de décision:

Les machines de Turing sont largement considérées comme le prototype abstrait des calculateurs numériques; Cependant, les travailleurs sur le terrain ont de plus en plus l'impression que la notion de machine de Turing est trop générale pour servir de modèle précis d'ordinateurs réels. Il est bien connu que même pour des calculs simples, il est impossible de donner une limite supérieure a priori sur la quantité de bande dont une machine de Turing aura besoin pour un calcul donné. C'est précisément cette caractéristique qui rend le concept de Turing irréaliste.

L'idée d'un automate fini est apparue dans la littérature ces dernières années. Ce sont des machines n'ayant qu'un nombre fini d'états internes pouvant être utilisées pour la mémoire et le calcul. La restriction de finitude semble donner une meilleure approximation à l'idée d'une machine physique. Bien sûr, de telles machines ne peuvent pas faire autant que les machines de Turing, mais l’avantage de pouvoir calculer une fonction récursive générale arbitraire est discutable, car très peu de ces fonctions apparaissent dans les applications pratiques.

Cependant, alors que les machines de Turing sont trop puissantes, les DFA sont trop faibles . De nos jours, les théoriciens préfèrent la notion de calcul polynomial , même si cette notion n’est pas sans poser de problèmes. Cela dit, les DFA et les NFA ont encore leur utilité, principalement dans les compilateurs (utilisés pour l'analyse lexicale) et les périphériques réseau (utilisés pour un filtrage extrêmement efficace).

Le modèle de machine de Turing n'est-il pas trop limité?

La thèse de Church-Turing affirme que les machines de Turing capturent la notion physique de calculabilité. Yuri Gurevich a tenté de prouver cette thèse en formulant une classe plus générale de dispositifs de calcul appelés machines à états abstraits et en prouvant qu'ils sont équivalents en puissance aux machines de Turing. Peut-être que ces machines sont analogues à votre modèle idéalisé.

La signification sous-jacente concerne l'idée d'équivalence de Turing. Le modèle exact n'a pas d'importance, tant qu'il est équivalent à Turing. Mais il est préférable d’utiliser un modèle plus simple pour pouvoir prouver plus facilement l’équivalence à d’autres modèles.

Plus précisément, il est préférable de faciliter la simulation de ce modèle dans d'autres modèles, car nous savons que la plupart des langages de programmation avancés sont équivalents à Turing (avec certaines hypothèses sur les adresses mémoire) et peuvent être utilisés pour simuler d'autres modèles.

Il existe d'autres modèles, tels que le lambda calcul et les grammaires (de réécriture de chaînes). Mais il est plus facile de définir des contraintes de temps et d'espace dans une machine de Turing. Vous pouvez également utiliser un langage de programmation tel que Brainfuck, mais cela nécessite un travail inutile, par exemple, redéfinir les symboles pour obtenir parfois une modification logiquement triviale.

Ainsi, la machine de Turing me semblait tout à fait appropriée si vous deviez apprendre un modèle unique pour tout. Mais si vous voulez apprendre plusieurs modèles de toute façon, je ne vois rien de mal à apprendre le calcul lambda pour l'idée d'équivalence de Turing, Brainfuck pour prouver d'autres modèles équivalents à Turing, et les langages de programmation pratiques (mieux avec une pile accessible et aucune variable cachée) pour des contraintes de temps / espace, et considérez la machine de Turing uniquement comme un outil permettant de prouver que ces éléments sont équivalents si personne ne se préoccupe de la trouver. Cela se produit naturellement si vous n'avez pas commencé par apprendre la théorie sous-jacente, mais seulement lorsque vous l'avez trouvée utile.

Je voudrais répondre à cette partie de la question, ajoutée dans une modification:

"Le modèle de calcul canonique ne devrait-il pas évidemment transmettre l'essence de la calculabilité?"

$T$$T$$T$

C’est l’une des qualités essentielles de la calculabilité: quelle que soit la notion générale de la calculabilité à l’esprit, il devrait y avoir une seule machine pour tout faire. C'est exactement ce que fait une machine de Turing universelle. C’est aussi ce que font les ordinateurs modernes (sous réserve de l’idéalisation physiquement irréaliste d’une mémoire infinie).

Une autre façon de le dire, qui répond directement à votre préoccupation concernant le fait que les machines de Turing ne sont pas minimales, est qu’elles sont tout aussi minimes qu’elles peuvent l'être, à condition de décrire une notion générale de calcul pour laquelle il existe une machine universelle.

Les machines de Turing ne sont pas destinées à être utilisées à la lettre; programmer en eux est quelque chose que l’on ne ferait qu’une fois comme exercice, pour comprendre comment ils fonctionnent.

Ils ne sont spécifiquement pas faits pour "faire" quoi que ce soit. Ils n'ont pas besoin d'être minimaux, ils n'ont pas besoin d'être à l'aise pour travailler avec.

Ils sont simplement un modèle de machine que vous pourriez construire, qui serait aussi expressif et puissant que n’importe quelle autre machine que vous pourriez jamais construire dans l’univers physique (pour autant que nous sachions aujourd’hui).

Ils ont été définis tels quels par Turing pour ces raisons principales:

• Pour pouvoir prouver qu'ils englobent tous les algorithmes auxquels on pourrait penser.
• Travailler sur le problème d’arrêt / problème de décision.
• Pour pouvoir réduire n'importe quelle autre machine / langue à celle-ci.

Aurait-il été possible de choisir une autre langue? Pour sûr! N'importe lequel des langages complets que nous connaissons aujourd'hui aurait pu être utilisé. Mais il aurait été beaucoup plus difficile d’établir les bases théoriques sur une machine plus complexe.

Je dirais qu'ils ne sont même pas un "modèle de calcul populaire"; personne ne calculerait jamais quoi que ce soit avec une machine de Turing. C’est un concept purement théorique, conçu par des informaticiens théoriciens, pour les Tcs.

Pourquoi est-il populaire, peut-être le plus populaire? Vous devez vous rappeler que Turing a inévitablement détruit cette "machine" plusieurs années avant les ordinateurs électroniques. Le TM fonctionne avec un papier, un stylo, un caoutchouc et enfin, un cerveau humain. Donc tout le monde est capable de faire un "calcul" avec cette machine. Tout le monde veut dire une personne qui n’a jamais appris les ordinateurs, les langages de programmation. C'est simple à utiliser. Lorsque vous y réfléchissez, vous découvrez un paradoxe: cette machine est un assemblage de presque rien mais vous pouvez tout faire fonctionner. À mon avis, le paradoxe de "presque-rien / contre / tout" est la raison pour laquelle il est populaire. Je remarquerais que la MT n'explique pas explicitement la récursivité, elle ne traite que du "saut". Cette fonctionnalité (parler explicitement de récursion) peut être une source de malaise pour les débutants, Par exemple, dans le lambda-calcul, le concept de Y-combinator est presque incompréhensible. Plus précisément, la MT est populaire parce que le paradoxe de "presque-rien / contre / tout" sans le mal de tête récursif.