Combler le fossé entre les machines abstraites et les architectures informatiques? [fermé]

Je me sens toujours déconnecté entre les machines abstraites (telles que les machines de Turing) et les architectures informatiques (y compris les architectures de machines virtuelles, l'architecture de Von Neumann). J'aimerais donc savoir comment ils sont liés? Comment l'un influence-t-il l'autre? Les références sont également appréciées. Merci.

Les machines de Turing et les "machines" similaires sont des modèles de calcul , elles sont destinées à étudier des problèmes tels que:

• Ce qui peut être calculé
• La classe de complexité des problèmes
• Relations entre classes de complexité
• L'équivalence de différentes façons de calculer quelque chose

Pour cela, la machine elle-même doit être aussi simple que possible. La commodité du programmeur ou les problèmes d'implémentation embêtants n'ont pas d'importance, car ce sont des objets mathématiques et seuls très peu de programmes sont écrits directement pour eux.

Inversement, l'architecture de la machine virtuelle et l'architecture réelle de la machine à base de silicium sont centrées sur l' exécution d'un programme donné . La machine est rendue plus compliquée que strictement nécessaire pour les préoccupations ci-dessus, et à son tour, il faut moins (et plus évident) d'instructions pour faire des choses intéressantes. Pas trop compliqué, car ils doivent toujours être compréhensibles (et efficacement implémentables), mais plus compliqués.

Les deux approches sont donc fondamentalement opposées. En plus d'être tous deux dans le domaine de l'informatique, ils n'ont pas grand-chose à voir l'un avec l'autre.

La relation principale est que vous pouvez simuler la construction théorique dans la construction physique.

Le fait que le physique soit capable de tout ce qui est théorique donne lieu à la capacité des tests et analyses théoriques de la machine théorique à être reconnus comme pouvant être mis en œuvre dans le monde réel.

Le problème de l'arrêt est un exemple parfait de quelque chose qui a été démontré comme insoluble sur une machine de turing, et par preuve sur la machine de turing, il peut donc être connu comme insoluble sur une machine réelle qui respecte les lois de la machine de turing.

C'est la différence entre résumer en comptant et le faire en l'écrivant sur du papier, il a été prouvé que la réalité du comptage remplit les mêmes règles que de faire la sommation sur un morceau de papier. Ainsi, lorsque vous simulez le comptage physique des choses, vos résultats sont reconnus comme applicables au monde réel - ainsi vous savez combien coûteront deux barres chocolatées en simulant mentalement le comptage sans avoir besoin de compter l'argent physique pour arriver au résultat.

Les gens travaillent actuellement sur l'analyse et les tests d'un modèle théorique connu sous le nom de «machine de quantification quantique» pour voir quelles installations seront disponibles avec les machines informatiques quantiques. Il est logique que les gens travaillent avec ces modèles lorsque la version physique de leur modèle est à la fois excessivement chère, rare et que les implémentations actuelles font encore très défaut. Les modèles théoriques sont utilisés pour montrer ce que nous pourrons faire lorsque nos implémentations physiques s'amélioreront.

Ils sont liés à peu près de la même manière que la navette spatiale est liée à un ballon que vous gonflez avec votre souffle, puis relâchez et regardez s'envoler.

Le principe fondamental d'expulser quelque chose dans une direction pour propulser quelque chose dans la direction opposée est là.

C'est là que s'arrêtent les similitudes.

Je vois les machines théoriques comme un pont entre le calcul du monde réel et les mathématiques. Une machine Turing est suffisamment puissante pour simuler n'importe quelle architecture ou langage de programmation du monde réel, assez simple pour être simulée facilement et, surtout, assez simple pour faire l'objet d'un raisonnement mathématique et de preuves raisonnablement simples.

Il est important de savoir que la définition du calcul n'est pas "ce que font les ordinateurs". Le calcul est antérieur aux ordinateurs. Les ordinateurs ont reçu leur nom parce qu'ils ont été créés pour faciliter la tâche de calcul, et non parce qu'ils le définissent.

La machine de Turing ne concerne donc pas le fonctionnement des ordinateurs. Il s'agit de savoir si un problème est calculable ou non - c'est-à-dire qu'il peut être résolu par un processus logique / mathématique formel. Il ne dit rien sur la façon dont ce processus pourrait être mis en œuvre. S'il est calculable, il peut être résolu par des êtres humains avec des crayons et du papier, avec suffisamment de temps, ou avec des ordinateurs ou (c'est la chose importante) avec n'importe quel système qui peut être démontré comme Turing complet .

La machine de Turing fait donc deux choses très importantes:

1. Fournit un test pour la calculabilité de tout problème / tâche.
2. Fournit un test pour tout système pour montrer s'il peut calculer n'importe quelle tâche calculable.

Le premier point nous permet de penser aux problèmes sans être distrait par les implémentations du monde réel. C'est une bonne chose parce que le vrai matériel distrait souvent les gens avec des détails non pertinents (comme "que se passe-t-il si nous manquons de mémoire ou d'espace de stockage?", Car les machines Turing ont des ressources infinies). Une solution théorique prouvable peut être développée pour une machine de Turing, puis tout ce que quelqu'un doit faire est de la traduire en quelque chose qui fonctionnera sur une architecture donnée.

Le deuxième point nous permet de vérifier la capacité de toute implémentation sans avoir à exécuter de nombreux tests différents sur celle-ci. S'il peut simuler une machine de Turing, il peut faire tout ce que la machine de Turing peut faire. Puisque Turing Machines peut calculer n'importe quoi de calculable, il en va de même.

Ce qui signifie que la relation entre la machine de Turing et toute architecture informatique réellement pratique (même virtuelle) n'est qu'une chose: ils peuvent calculer.

L'architecture de Von Neumann était une tentative de créer un modèle de conception pour des ordinateurs numériques électroniques à usage général efficaces . Le travail de Turing a fourni la preuve de sa validité

Si vous y réfléchissez, les architectures sont des machines abstraites. Ils décrivent comment un morceau de silicium soigneusement fabriqué «devrait» se comporter. La différence entre les architectures et les machines de Turing est plus une question d'échelle qu'un changement fondamental d'approche.

L'avantage des machines de Turing est qu'il existe un ensemble de preuves utiles qui sont très faciles à faire avec une machine de Turing. Il est simple de prouver que toute machine suffisamment puissante pour simuler une machine de Turing peut résoudre tout problème qu'une machine de Turing peut (duh). Cependant, cela devient plus intéressant lorsque vous définissez une fonction calculable . Il s'avère qu'il existe de nombreuses définitions compatibles d'une fonction calculable. Si vous pouvez définir tous vos comportements comme des fonctions calculables, vous pouvez être simulé dans une machine de Turing.

Disons donc que vous avez une architecture qui prend directement en charge les programmes de style LISP, et une autre comme le x86 qui est plus procédurale. Votre ami affirme que "LISP est plus expressif, vous pouvez donc écrire des programmes sur cette machine que vous ne pourriez jamais écrire sur votre x86." C'est brutal à contrer (d'autant plus que vous ne connaissez probablement pas assez LISP). Cependant, vous pouvez abuser de plusieurs machines abstraites comme la machine de Turing:

• Votre machine LISP peut être sophistiquée, mais tout ce qu'elle peut faire est réductible au calcul lambda. Votre ami hoche la tête avec impatience. Le calcul lambda est un peu culte pour les programmeurs fonctionnels.
• Mon x86 peut être sophistiqué, mais tout ce qu'il peut faire est réductible à une machine d'enregistrement. Encore une fois, aucune question de votre ami. Les registres sont tellement conformes à la théorie informatique moderne!
• Toute machine à registre peut être modélisée comme une machine de Turing simulant cette machine à registre. Maintenant, votre ami se demande pourquoi vous revenez à l'ère du ruban perforé.
• Et votre machine à calculer lambda peut également être réduite à une machine de Turing. * Votre ami s'oppose, mais vous les dirigez vers la thèse de Church-Turing, et ils penchent la tête de honte.
• Ainsi, ma boîte x86 peut faire tout ce que votre machine basée sur LISP peut faire!

Il existe bien sûr de nombreux autres exemples. Le jeu de la vie de Conway s'est avéré être Turing complet, ce qui signifie qu'il pourrait théoriquement faire tout ce que votre ordinateur peut faire. La façon la plus simple de le faire était de construire une machine Turing dans la vie . J'en parle parce que ce serait un cas de ce que vous appelez une machine abstraite traitée comme une architecture littérale! Vous pouvez imaginer à quel point la revendication de calculabilité dans la vie serait difficile sans l'aide de modèles abstraits (je suis sûr que je ne modélise pas un x64, avec un cache furtif, juste pour prouver que la vie est calculable!)

Au final, la grande différence entre les architectures et les machines abstraites est que les architectures se préoccupent généralement des performances. Les architectures veulent savoir à quelle vitesse vous pouvez faire quelque chose. Les machines abstraites se contentent de savoir si vous le pouvez. Prenons l'exemple du constructeur universel développé pour les machines d'état von Neuman. Il suffisait de prouver que l'UC pouvait fonctionner, même si les auteurs n'avaient jamais assez de puissance de calcul pour le voir.

Le prix que les architectures paient pour démontrer à quelle vitesse elles peuvent fonctionner est qu'il est souvent terriblement difficile de prouver qu'elles peuvent tout calculer . Pour cela, les architectures font demi-tour et commencent à utiliser des machines abstraites.