Les ordinateurs réels n'ont qu'un nombre fini d'états. Quelle est donc la pertinence des machines de Turing par rapport aux ordinateurs réels?

42

Les ordinateurs réels ont une mémoire limitée et seulement un nombre fini d'états. Donc, ce sont essentiellement des automates finis. Pourquoi les informaticiens théoriques utilisent-ils les machines de Turing (et d’autres modèles équivalents) pour étudier les ordinateurs? Quel est l'intérêt d'étudier ces modèles beaucoup plus forts en ce qui concerne les ordinateurs réels? Pourquoi le modèle des automates finis ne suffit-il pas?

Rahul
la source
7
@Kaveh Les gens disent généralement que les ordinateurs utilisés dans la pratique sont des FSM, mais que ceux-ci sont trop grands et que des propriétés structurelles intéressantes sont perdues dans la vue FSM. Je n'ai jamais vu d'explication non artificielle. Par conséquent, la question est sur le sujet ici.
Martin Berger
15
La vraie question est de savoir pourquoi étudier les machines de Turing, lorsque nous utilisons le modèle RAM pour analyser des algorithmes.
Yuval Filmus
39
Parce que parfois est une meilleure approximation de 10000000000000000000000000000000 que 10000000000000000000000000000000 . 1000000000000000000000000000000010000000000000000000000000000000
Andrej Bauer
30
Rappelez-vous que le problème non résolu le plus célèbre de l’informatique théorique aujourd’hui est le suivant: un type d’ordinateur imaginaire physiquement impossible peut-il résoudre des problèmes aussi rapidement qu’un ordinateur imaginaire encore plus physiquement impossible ? Ne confondez pas l'informatique théorique avec l'ingénierie informatique pratique; les détails du monde physique ne sont pas particulièrement pertinents.
Eric Lippert
23
Les matériaux réels sont constitués d'atomes et sont de nature discrète. Pourquoi étudier les intégrales?
Peter Shor

Réponses:

32

Lorsque l'on aborde cette question, il y a deux approches: historique qui concerne la manière dont les concepts ont été découverts et technique qui explique pourquoi certains concepts ont été adoptés et d'autres abandonnés ou même oubliés.

Historiquement, la machine de Turing est peut-être le modèle le plus intuitif parmi plusieurs autres développés qui tentent de répondre au problème d’Entscheidungs . Cela est intimement lié aux efforts considérables déployés au cours des premières décennies du XXe siècle pour axiomatiser complètement les mathématiques. L'espoir était qu'une fois que vous auriez prouvé qu'un petit ensemble d'axiomes était correct (ce qui nécessiterait un effort considérable), vous pourriez alors utiliser une méthode systématique pour déduire une preuve de la déclaration logique qui vous intéressait. Même si quelqu'un était considéré comme un automate fini dans ce contexte, ils seraient rapidement écartés car ils ne parviennent pas à calculer même des fonctions simples.

Techniquement, l'affirmation que tous les ordinateurs sont des automates finis est fausse. Un automate fini a une mémoire constante qui ne peut pas être modifiée en fonction de la taille de l'entrée. Aucune contrainte, ni en mathématiques ni dans la réalité, n’empêche la fourniture de bandes, disques durs, RAM ou autres formes de mémoire supplémentaires, une fois que la mémoire de la machine a été utilisée. Je pense que cela a souvent été utilisé aux débuts de l'informatique, alors que même de simples calculs pouvaient remplir la mémoire, alors que maintenant, pour la plupart des problèmes et avec l'infrastructure moderne qui permet une gestion de la mémoire beaucoup plus efficace, ce n'est généralement pas un problème .


EDIT: J’ai examiné les deux points soulevés dans les commentaires, mais j’ai choisi de ne pas les inclure pour des raisons de brièveté et de temps pour écrire la réponse. C’est pourquoi je pense que ces points ne diminuent pas l’efficacité des machines de Turing dans la simulation d’ordinateurs modernes, notamment par rapport aux automates finis:

  • Permettez-moi d’abord d’aborder la question physique de la limitation de la mémoire par l’univers. Tout d’abord, nous ne savons pas vraiment si l’univers est fini ou non. En outre, le concept d'univers observable, qui est par définition fini, est également par définition hors de propos pour un utilisateur qui peut se déplacer à n'importe quel point de l'univers observable pour utiliser la mémoire. La raison en est que l'univers observable fait référence à ce que nous pouvons observer à partir d'un point spécifique, à savoir la Terre, et il en irait autrement si l'observateur pouvait se rendre à un endroit différent de l'univers. Ainsi, toute argumentation sur l'univers observable se résume à la question de la finitude de l'univers. Mais supposons qu’au travers d’une percée, nous acquérions la connaissance que l’univers est bien fini. Bien que cela aurait un grand impact sur les questions scientifiques, Je doute que cela ait un impact sur l'utilisation des ordinateurs. En termes simples, il se peut que les ordinateurs soient en principe des automates finis et non des machines de Turing. Mais pour la grande majorité des calculs et vraisemblablement pour tous les calculs qui intéressent les humains, les machines de Turing et la théorie associée nous offrent une meilleure compréhension. Dans un exemple brut, bien que nous sachions que la physique newtonienne est fondamentalement fausse, je doute que les ingénieurs en mécanique utilisent principalement la physique quantique pour concevoir des voitures ou des machines d’usine; les cas où cela est nécessaire peuvent être traités à un niveau individuel. Mais pour la grande majorité des calculs et vraisemblablement pour tous les calculs qui intéressent les humains, les machines de Turing et la théorie associée nous offrent une meilleure compréhension. Dans un exemple brut, bien que nous sachions que la physique newtonienne est fondamentalement fausse, je doute que les ingénieurs en mécanique utilisent principalement la physique quantique pour concevoir des voitures ou des machines d’usine; les cas où cela est nécessaire peuvent être traités à un niveau individuel. Mais pour la grande majorité des calculs et vraisemblablement pour tous les calculs qui intéressent les humains, les machines de Turing et la théorie associée nous offrent une meilleure compréhension. Dans un exemple brut, bien que nous sachions que la physique newtonienne est fondamentalement fausse, je doute que les ingénieurs en mécanique utilisent principalement la physique quantique pour concevoir des voitures ou des machines d’usine; les cas où cela est nécessaire peuvent être traités à un niveau individuel.

  • Toutes les restrictions techniques telles que les bus et les adresses ne sont que des limitations techniques du matériel existant et peuvent être surmontées physiquement. La raison pour laquelle ceci n'est pas vrai pour les ordinateurs actuels est que l'adressage 64 bits nous a permis de déplacer la limite supérieure de l'espace d'adressage à une hauteur que peu d'applications, voire aucune, ne peuvent atteindre. En outre, la mise en œuvre d'un système d'adressage "extensible" pourrait potentiellement avoir un impact sur la grande majorité des calculs qui n'en auront pas besoin et qui sont donc inefficaces. Rien ne vous empêche d’organiser un système d’adressage hiérarchique, par exemple, pour deux niveaux, la première adresse peut faire référence à l’une des banques de mémoire, puis chaque banque à 2 64264264adresses différentes. La mise en réseau est un excellent moyen de le faire, chaque machine ne se souciant que de sa mémoire locale, mais ils peuvent calculer ensemble.

chazisop
la source
4
La deuxième partie de cette réponse est fausse. Les ordinateurs sont des automates à états finis, même si vous avez acheté toute la RAM et tout autre matériel que vous pourriez. La quantité de RAM que vous pouvez connecter à un ordinateur est limitée par la largeur de son bus d'adresses. Il en va de même pour les disques et autres périphériques.
Emil Jeřábek soutient Monica le
12
@ EmilJeřábek pas vrai. Les interfaces série n'ont pas de bus d'adresses et la quantité de données auxquelles je peux accéder sur Internet n'est limitée par aucune propriété de mon ordinateur.
Arrêtez de blesser Monica le
5
@OrangeDog, mais l'univers mettrait toujours une limite à la quantité de données pouvant être stockée dans l'univers observable
phénomène à la cliquet
9
@ratchetfreak, comme le montre la machine de Turing, vous n'avez besoin que d'un accès local - la "fin" actuelle de la bande n'a pas besoin d'être dans l'univers observable;)
Stop Harming Monica
6
En mentionnant l’histoire, il convient de citer l’examen par Church du document de Turing selon lequel les machines de Turing ont "l’avantage de rendre l’identification efficace ... évidente immédiatement". En d'autres termes, la définition de Turing était convaincante pour ceux qui essayaient de se convaincre d'avoir capturé tout ce qui pouvait être calculé.
Jim Hefferon
44

Pour compléter les autres réponses: je pense que Turing Machine est une meilleure abstraction de ce que font les ordinateurs que les automates finis. En effet, la principale différence entre les deux modèles réside dans le fait qu'avec les automates finis, nous nous attendons à traiter des données plus grandes que l'espace d'états, et Turing Machine est un modèle pour le contraire (espace d'états >> données) en rendant l'état espace infini. Cet infini peut être perçu comme une abstraction de "très gros devant la taille des données". Lorsque vous écrivez un programme informatique, vous essayez d'économiser de l'espace pour plus d'efficacité, mais vous supposez généralement que vous ne serez pas limité par la quantité totale d'espace disponible sur l'ordinateur. C'est en partie pourquoi les machines de Turing sont une meilleure abstraction des ordinateurs que les automates finis.

Denis
la source
14
C'est à mon humble avis la bonne réponse. Les raisons sont purement pragmatiques, les machines de Turing font mieux que les automates finis pour expliquer ce que font les ordinateurs aux échelles concernées.
Emil Jeřábek soutient Monica le
3
Je suis d’accord avec cela, à l’exception de la phrase "vous supposez généralement que vous ne serez pas limité par la quantité totale d’espace disponible sur votre ordinateur". Au contraire, presque tout programme non trivial est limité par l'espace disponible et les programmeurs déploient beaucoup d'efforts pour le gérer (par exemple, le ramassage des ordures pour une réutilisation automatique de la mémoire), mais (1) nous ne pouvons rien y faire, et (2) nous nous limitons à des entrées assez petites. Il est à noter que les MT nous donnent une idée naturelle de la taille du problème et que les algorithmes ont tendance à être fermés vers le bas par rapport à cette notion naturelle de la taille du problème.
Martin Berger
2
@MartinBerger Re « presque tout programme non trivial est limité par l'espace disponible et les programmeurs vont très loin pour y faire face (par exemple , la collecte des ordures pour la réutilisation automatique de la mémoire) »: Je soutiens que les programmes écrits pour les systèmes avec la collecte des ordures considèrent ce système, y compris le gc , en tant que machine contre laquelle ils programment. Le ramasse-miettes ne fait pas partie du programme. cela fait partie d'un effort pour fournir précisément ce que Denis a dit: Une machine à programmer avec une mémoire virtuellement illimitée.
Peter - Réintégrer Monica le
2
@ PeterA.Schneider Je ne suis pas du tout d'accord. La raison d'utiliser le GC fourni par le langage d'exécution est un des aspects économiques du développement logiciel: le mécanisme de gestion de la mémoire spécifique au programme est plus performant que le GC, et la plupart des programmeurs le préféreraient s'ils le retiraient en toute sécurité et à moindre coût. Mais ils ne peuvent pas, alors utilisez plutôt le GC ambiant dont le coût est amorti sur un grand nombre de programmes. En ce sens, l’utilisation de GC s’efforce beaucoup de gérer la mémoire de finitude.
Martin Berger
2
Les machines traditionnelles ne sont pas des abstractions de ce que font les ordinateurs, elles sont des abstractions de ce que fait des ordinateurs, et les ordinateurs ont été construits par la suite. Les ordinateurs effectuent la plupart de leurs calculs en utilisant une quantité fixe de mémoire de travail interne, mais Turing Machines n’a pas été inventé pour raisonner sur le calcul avec une quantité limitée de mémoire de travail.
reinierpost
10

Andrej Bauer a donné une raison importante dans les commentaires:

1000000000000000000000000000000010000000000000000000000000000000

Permettez-moi de compléter les autres réponses par quelques points, qui étaient probablement trop évidents pour être mentionnés:

  • Si votre objectif est d'étudier de vrais ordinateurs, les automates finis et les machines de Turing seront souvent des modèles trop simples pour répondre aux questions pertinentes. Les ordinateurs réels ont plusieurs cœurs de traitement avec une hiérarchie de cache (ou un autre schéma de gestion intelligente), un accès à une quantité raisonnable de mémoire rapide, un accès à une énorme quantité de mémoire externe lente (disques durs), et peuvent communiquer avec d'autres ordinateurs similaires vitesse approximativement comparable à la vitesse d'accès à la mémoire externe lente.
  • Si vous vous demandez maintenant pourquoi vous avez besoin de tous ces détails, il s'avère que votre véritable objectif est d'étudier les cas problématiques et avec quelle efficacité vous pouvez les résoudre. Si vous parlez d'ordinateurs réels, cela peut également signifier que vous exécutez des expériences avec des instances de problèmes réels sur différents types d'architectures (réelles).
  • Le modèle d'ordinateurs réels décrit ci-dessus est toujours idéalisé, car il ignore les différents modes de défaillance des ordinateurs réels. Etant donné que les pannes de mise hors tension peuvent être plus fréquentes que les pannes de disque dur (et que les disques durs peuvent tout de même faire l'objet de sauvegardes), certains domaines problématiques, tels que le fonctionnement de bases de données fiables, devront peut-être en tenir compte.
  • Π10
Thomas Klimpel
la source
8

Un formalisme est utile ou non, basé sur ce que les gens veulent utiliser le formalisme pour modéliser et comprendre.

La machine de Turing est un formalisme utile pour comprendre les programmes . Les programmes méritent d'être compris. la plupart des calculs sont effectués par des programmes plutôt que par des machines spéciales. Le formalisme de la machine de Turing nous permet de modéliser d'importantes préoccupations du monde réel telles que la complexité temporelle et spatiale. Il est beaucoup moins naturel d'essayer d'étudier ces notions à l'aide d'automates à états finis.

Les machines de Turing ne sont pas très utiles pour essayer d’étudier la complexité du calcul de fonctions finies (par exemple, les fonctions dont le domaine est constitué d’entrées d’une longueur maximale de 10 millions). La complexité des circuits décrit bien mieux la complexité des fonctions finies ... mais les machines de Turing ont été très utiles pour comprendre la complexité des circuits.

Les automates finis ont également été utiles pour comprendre la complexité des circuits; tous ces modèles ont leur place dans l'arsenal mathématique.

Je rejette l'argument selon lequel les automates à états finis sont un meilleur modèle de réalité simplement parce que les ordinateurs du monde réel ne comportent qu'un nombre fini d'états internes. L’étude des automates à états finis porte de manière cruciale sur les entrées provenant de l’ infini ensemble de chaînes, alors que les ordinateurs du monde réel ne traitent que des entrées de longueur maximale fixe (à moins que vous ne croyiez que nous vivons dans un univers infini, en termes de ou le temps).

Un modèle doit être jugé en fonction de son utilité pour comprendre les aspects de la réalité qui nous tiennent à cœur. Ou (alternativement) en termes d’utilité pour comprendre un univers mathématique que les gens trouvent suffisamment convaincant, même si cet univers mathématique n’a pas de manifestation physique évidente.

Les machines de Turing, les machines à états finis et les circuits (ainsi que d’autres modèles) ont tous prouvé leur utilité.

Eric Allender
la source
6

Les ordinateurs réels ne sont pas des RTA. Un ordinateur réel est un ordinateur universel, en ce sens que nous pouvons décrire un ordinateur à imiter et l'ordinateur le simulera. Pour de nombreux exemples, recherchez "machine virtuelle".

Il est possible de construire une machine de turing universelle - une MT qui reçoit une description d'une autre MT puis émule le fonctionnement de cette MT sur une entrée fournie.

n22n

Comme point de départ dans la littérature, je peux recommander « Sur l’existence d’automates universels finis ou à repoussement », qui étudie la non-existence d’automates universels. Vous pouvez également consulter ses références (et ainsi de suite).

Eric Towers
la source
3
C'est une approche utile pour saisir intuitivement différents niveaux de «puissance de calcul». Cependant, OP semble penser que les ordinateurs réels sont des FSM car le nombre d'états est limité, par exemple en raison de la mémoire RAM finie. Selon votre argument, cela signifie que les ordinateurs réels ressemblent davantage à des FSM qu'à des machines de Turing, car je ne peux pas doubler librement le nombre d'états d'une machine simulée. Je n'ai pas de bande infinie comme stockage.
amon
1
Les machines Turing n'ont pas besoin non plus d'une bande infinie. Les ordinateurs peuvent utiliser une quantité arbitrairement grande de stockage externe dans leurs calculs (et cela devient particulièrement facile avec les fournisseurs de cloud que nous avons aujourd'hui), de sorte qu'ils ressemblent fondamentalement à des machines de Turing plutôt qu'à des FSM.
reinierpost
1
Si nous supposons qu'un ordinateur a une quantité de mémoire fixe, il manquera de mémoire lors de la simulation d'un ordinateur avec plus de mémoire. Par conséquent, avec cette hypothèse, ce n'est pas vraiment universel.
Kaveh
3

Ce qui rend la machine de Turing spéciale, c’est que, tout en étant très, très simple, elle peut exécuter tous les algorithmes auxquels nous pouvons penser. Aucune machine connue n'est plus puissante (en ce sens qu'elle peut exécuter des algorithmes dont la machine de Turing n'est pas capable).

Mécaniquement simples, il est facile de montrer si, ou à quel degré, d'autres machines sont équivalentes à une machine de Turing. Cela permet relativement facilement de montrer si un ordinateur (ou un langage informatique) donné est véritablement universel (c / f "Turing-complete").

AnoE
la source
La question porte sur la relation entre le modèle de machine de Turing et les ordinateurs réels. Si nous supposons qu'un ordinateur a une quantité de mémoire fixe, ce n'est pas vraiment universel.
Kaveh
1

Pourquoi le modèle des automates finis ne suffit-il pas?

Alors que d'autres réponses ont déjà mentionné de nombreux aspects pertinents, je pense que le principal avantage des machines de Turing par rapport aux automates finis est la séparation des données et des programmes . Cela vous permet d'analyser un programme assez fini et de faire des déclarations sur la manière dont ce programme gérera différentes entrées, sans limiter la taille de l'entrée.

Bien qu’il soit théoriquement possible de décrire à la fois un ordinateur réel et quelque chose comme une machine de Turing avec une bande finie en tant que machine à états, cela n’est pas vraiment réalisable: le nombre d’états est exponentiel dans la quantité de mémoire dont dispose votre machine et le nombre fini Le formalisme d'automate d'état vous oblige à lister explicitement les transitions entre ces états. Donc, pour un automate général à états finis de cette taille, il est tout à fait impossible de faire des déductions basées sur une énumération complète de toutes les transitions d’états.

Bien sûr, dans un ordinateur réel, les transitions entre états ne peuvent pas se produire de manière arbitraire. Il n'y a pas de commande pour échanger un tiers des bits en mémoire en une seule étape du calcul. Vous pouvez donc essayer de proposer une spécification plus compacte pour les transitions d’état. Quelque chose comme la spécification du jeu d'instructions de votre architecture. Bien entendu, les architectures informatiques réelles sont complexes pour des raisons de performances. Vous pouvez donc simplifier davantage ce jeu d'instructions très simples, qui effectuent de très petites étapes en utilisant des entrées et des sorties très limitées. En fin de compte, votre architecture ressemblera peut-être à un interpréteur de machine de Turing: en utilisant quelques bits de code de programme et un bit d’entrée, générez un peu de sortie et déplacez-vous dans votre code de programme.

Une solution consisterait à utiliser les états d'un automate à états finis uniquement pour représenter les données en cours de traitement par le programme, tout en codant le programme lui-même dans les transitions d'état. Cela poserait le même problème de énumération de tous les états, et une représentation compacte pourrait à nouveau être proche de celle d’une machine de Turing.

Quel est l'intérêt d'étudier ces modèles beaucoup plus forts en ce qui concerne les ordinateurs réels?

Dans l'ensemble, je dirais qu'une machine de Turing à bande finie serait probablement un meilleur modèle pour les ordinateurs actuels. Mais pour de nombreuses questions scientifiques, la distinction entre une bande finie mais de grande taille et une bande infinie n’est pas pertinente. Il suffit donc de revendiquer une bande infinie pour rendre les choses plus faciles. Pour les autres questions, la quantité de bande utilisée est au cœur de la question, mais le modèle vous permet facilement de parler de la quantité d'utilisation de la bande sans avoir à spécifier précisément ce qui se passe si le calcul est à court de bande.

MvG
la source
1

La plupart des problèmes nécessitent des machines de Turing de taille finie

Bien que supposer que la bande non bornée soit une simplification utile, la plupart des problèmes / algorithmes nécessitent en réalité une quantité finie de bande, et les limites de la mémoire requise (éventuellement en fonction de la taille de l'entrée) peuvent être analysées et souvent prouvées.

Cela se généralise aussi souvent à d'autres types d'ordinateurs (pour lesquels l'analyse ou la preuve liée peut être beaucoup plus salissante que sur une machine de Turing), et permet d'estimer la quantité de mémoire de stockage temporaire requise pour un problème particulier - peut-on le faire avec un montant fixe de l'espace? Proportionnel à l'entrée? A-t-il besoin de quantités d'espace exponentielles à mesure que les intrants augmentent?

Peter est
la source
1

Une caractéristique importante des machines qui ne sont pas partagées par des automates finis est qu’elles peuvent mettre à niveau la quantité de mémoire nécessaire pour résoudre le problème avec sa taille .

Disons (nombres inventés) que vérifier si un graphique a un chemin hamiltonien, étant donné un graphique avec n les sommets, vous avez besoin n2bits de mémoire. Vous pouvez décrire complètement cette relation en utilisant une machine de turing. Vous pouvez également décrire cette relation en utilisant un nombre infini d’automates finis: les implémentations de cette machine de turing avec un nombre de bandes limité. Vous avez probablement besoin de rendre compte de certains détails, mais vous pouvez vous convaincre avec un simple argument: c'est ce que nous faisons habituellement avec les ordinateurs! Nous implémentons une solution qui utilise plus d'espace pour les problèmes plus importants et l'ordinateur exécute notre solution avec son nombre d'états borné.

Le problème: de nombreux problèmes ont des solutions naturelles qui utilisent plus de mémoire, plus le problème est gros. Il est donc naturel de décrire ces solutions avec des représentations pouvant utiliser une mémoire infinie - non pas parce qu’une instance utilisera des quantités infinies, mais parce qu’une instance utilise chaque quantité. Vous pouvez le faire avec des machines de turing, mais aussi avec des séquences d'automates finis.

Josinalvo
la source
Sur une note connexe, si une machine de Turing à N états est démarrée avec une bande ayant un nombre fini de caractères C non blancs avant et après la position initiale, il y aura un nombre T (N, C) tel que toute machine qui se terminera jamais pourrait être émulé par une machine une machine dont la bande était limitée à T (N, C) caractères.
Supercat
-2

Les ordinateurs réels ont une mémoire limitée et seulement un nombre fini d'états. Donc, ce sont essentiellement des automates finis.

Les machines de Turing sont des dérivés d'automates finis. Les machines de Turing sont pratiquement une architecture de Nuemann.

Jesse Enjaian
la source