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?

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?

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 $2^{64}$$2^{64}$adresses 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.

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.

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

$\infty$$10000000000000000000000000000000$$10000000000000000000000000000000$

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.
• $\Pi_1^0$

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

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.

$n$$2^{2^n}$

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).

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").

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.

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?

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 $n\cdot2$bits 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.

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.