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

68

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.

Alex
la source
2
Espérons que les prochains cours aideront à clarifier.
Yuval Filmus
19
Vous trouverez peut-être le lambda calcul comme un modèle de calcul plus naturel. C'est la base de la programmation fonctionnelle.
Bakuriu
4
En fait, je suis sur le point d'obtenir mon diplôme. Le cours de niveau le plus élevé que j'ai suivi et qui portait sur la théorie des automates s’arrêtait sur les machines de Turing, bien qu’ils mentionnent l’équivalence entre les différents modèles de calcul. J'ai même fait ma juste part de la "programmation" de TM, à juste titre la base. Le TM cependant m'a toujours buggé. Cela ne semblait pas "minimal"; cela ne m'a pas exposé l'essence du calcul.
Alex
4
" un système physique correspondant à la chaîne d'entrée " - à quoi ressemblerait cette correspondance? La machine de turing est un modèle formel assez simple mais puissant pour exactement une telle chose.
Bergi
2
Les machines de Turing changent de manière déterministe uniquement en fonction de l'état d'origine (si vous voulez parler de la configuration). Alors qu'est-ce qui ne va pas avec ça?
user23013

Réponses:

72

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.

David Richerby
la source
Les commentaires ne sont pas pour une discussion prolongée; cette conversation a été déplacée pour discuter .
Gilles, arrête de faire le mal
56

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?

λ

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

Yuval Filmus
la source
17

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.

utilisateur23013
la source
1
Essentiellement, tous les processeurs modernes sont des machines d’enregistrement avec RAM. Même les microcontrôleurs ou les architectures de jouet avec un seul registre d'accumulateur ont généralement une sorte de registre d'adresses distinct dans lequel vous pouvez charger des pointeurs, plutôt que d'être une simple machine à accumulateur. Mais le vrai matériel a des adresses de taille fixe, et Turing n'est donc pas complet. IDK si le modèle Register-Machine est très utilisé dans la CS théorique, mais c’est la façon dont le langage assembleur fonctionne dans la vie réelle et qu’il peut être utile de comprendre pour une analyse de performances, car tout est compilé en asm.
Peter Cordes
14

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é?"

TTT

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.

Lee Mosher
la source
Merci de me rappeler de la machine universelle. Je vois comment cela implique un calcul "complet".
Alex
5

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.

AnoE
la source
D'accord sur tous les points. La popularité n’est peut-être que relative aux modèles plus obscurs tels que les machines Thue, le calcul Lambda et le matériel d’Emil Post.
luser droog
Désolé, mais vous manquez un point très central que d’autres langues auraient sérieusement gâché. Une machine de Turing définit ce que vous pouvez réellement calculer. N'importe quel autre langage limiterait la question à la façon dont vous pouvez le calculer, rendant très peu probable qu'il soit en mesure de prouver ce que vous pouvez calculer ou non.
Bent
Si les machines de turing sont supposées être un objectif de réduction pour d'autres modèles, pourquoi ne devraient-elles pas être minimales?
Bergi
@Bent, j'avoue ne pas comprendre ce que vous essayez de dire en plus de ce que j'ai mentionné avec "Mais il aurait été beaucoup plus difficile de construire les bases théoriques sur une machine plus complexe." (c.-à-d. sur un langage de programmation réel tel que nous les connaissons et les utilisons).
AnoE
Par popularité, je voulais dire ce qui est utilisé dans le CS théorique. Encore une fois, c’était le seul modèle que j’ai appris (bien que je pense avoir été exposé à un peu du calcul lambda). Je me demandais juste pourquoi, peut-être pédagogiquement, c'est toujours le premier à être enseigné. Je vois à quel point son utilité le justifie.
Alex
5

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.

utilisateur88464
la source