Dans une conférence, un professeur a mentionné que les ordinateurs modernes n'ont pas autant de puissance de calcul qu'une machine Turing parce qu'ils n'ont pas de mémoire infinie, et comme aucun ordinateur ne peut avoir une mémoire infinie, la machine Turing est donc inaccessible et représente simplement la limite supérieure de l'informatique. Y a-t-il une mesure ou une définition de quels problèmes (ou classes de problèmes) sont hors de portée de notre puissance de calcul à cause de cela?
computability
JustAnotherSoul
la source
la source
Réponses:
Si nous considérons l'univers comme fini, alors tout ce qui a besoin de plus de mémoire que cette quantité finie dépasse notre capacité de calcul.
Cependant, ce n'est pas un bon modèle pour étudier la calculabilité, le modèle de la machine de Turing fonctionne beaucoup mieux en réalité et c'est la raison pour laquelle nous l'utilisons pour étudier le calcul sur de vrais ordinateurs. Une machine Turing n'a pas vraiment besoin d'une quantité infinie de mémoire, elle n'a besoin que d'une quantité illimitée de mémoire. Par exemple, nous pouvons fournir de la mémoire supplémentaire à un ordinateur au fil du temps (car l'ordinateur a besoin de plus en plus de mémoire), puis nous avons quelque chose de similaire à une machine de Turing. Si nous supposons que nous avons une quantité illimitée de temps et de mémoire pour terminer notre calcul, alors la machine de Turing capture assez bien ce concept de calculabilité.
Consultez l'article Wikipedia sur les machines Turing, il y a une section qui discute de la pertinence du modèle.
Si vous êtes intéressé par la calculabilité réalisable , alors la théorie de la complexité (où nous considérons différentes quantités de ressources comme le temps et l'espace pour effectuer une tâche de calcul) est plus proche de ce que nous pouvons vraiment faire dans la pratique que la théorie de la calculabilité. De nombreux experts affirment que les calculs possibles relèvent de la classe de complexité (et plus récemment dans les versions probabilistes et quantiques de , c'est-à-dire et ).P P B P P B Q P
la source
Vous pourriez considérer Linear Bounded Automaton et les langues correspondantes sont les langues contextuelles . Voir Chomsky Hierarchy pour savoir quelles langues sont hors de portée de ces automates.
btw, dans un certain sens, certains problèmes "inaccessibles" deviennent désormais à portée de main, en raison de la puissance de calcul limitée!
Par exemple, Halting Problem for Turing Machines est indécidable, mais il est décidable pour les automates linéaires délimités.
la source
La théorie du calcul est une abstraction du monde réel. À bien des égards, l'abstraction n'est pas très adaptée au monde réel. D'une part, nous ne pouvons pas fabriquer d'ordinateurs avec une mémoire illimitée; donc nous ne pouvons même pas faire des machines pour reconnaître des langages réguliers arbitraires - ou même des langages finis arbitraires!
Cependant, cela ne pose pas trop de problème; dans le monde réel, nous ne pouvons même pas construire des entrées de n'importe quelle taille arbitraire, et même si nous le pouvions, nous ne serions pas assez longtemps pour voir la réponse.
Au sens strict, non: la classe des ordinateurs physiquement réalisables est strictement moins puissante que la classe des machines de Turing. Il est également strictement moins puissant que la classe des automates finis.
la source