Est-ce qu'une machine de Turing?
qu'est Ce qu'une machine de Turing et pourquoi les gens gardent de mentionner? Mon PC IBM est tout ce dont j'ai besoin pour faire mon calcul! Pourquoi quelqu'un s'intéresse à ces machines?
10 réponses
la raison pour laquelle les machines de Turing sont une grande affaire a à voir avec l'étude de la science de L'informatique classique ou de la théorie du calcul de type substance. Il s'agit essentiellement d'analyser les propriétés générales d'un ordinateur, comme les capacités théoriques et les limites d'un ordinateur, ainsi que ce que nous entendons par "informatique" quelque chose.
un exemple de quelque chose que l'on pourrait étudier en utilisant des machines de Turing est Le Problème De L'Arrêt. Alors que ce problème est quelque chose d'un exercice académique, il a facilement tangible des implications dans le monde réel. Pourquoi ne pas écrire un débogueur qui vous dira simplement si oui ou non votre programme contient des boucles infinies? Le problème D'arrêt établit que la résolution de ce problème pour le cas général est impossible.
l'étude des machines de Turing se prête également à l'étude des grammaires de langue et de leurs classes, ce qui conduit au développement du langage de programmation. Le terme "expressions régulières" vient sur les, car ils sont un régulier de la grammaire, et l'étude de ces grammaires (partie de la théorie du calcul) vous en dira plus sur exactement quels types de problèmes les expressions régulières peuvent résoudre et ce qu'elles ne peuvent pas résoudre. Par exemple, une syntaxe d'expression régulière traditionnelle ne pourra pas résoudre le problème suivant: analyser un certain nombre N de caractères 'a' en entrée, puis analyser le même nombre n de char 'b'.
Si vous êtes intéressé par un bon texte sur ce genre de chose, découvrez Introduction à la Théorie de Calcul par Michael Sipser. Que c'est bon.
la machine de Turing est une machine de calcul théorique inventée par Alan Turing pour servir de modèle idéalisé pour le calcul mathématique, essentiellement sa forme simple d'ordinateur, son composé par un bande (un ruban de papier), a un tête qui peut lire les symboles, écrire un nouveau symbole en place, puis aller à gauche ou à droite.
on dit que la machine de Turing est dans un certain état, puis un programme est une liste de transitions, ayant un état actuel et un symbole sous la tête, ce qui devrait être écrit sur la bande, quel serait le prochain état, et où la tête devrait se déplacer.
Voici un Machine De Turing De Base, implémenté en JavaScript...
et un croquis:
mon PC IBM est tout ce dont j'ai besoin pour faire mon calcul!
quelque chose que d'autres n'ont pas fait remarquer: votre PC IBM une machine de Turing. Plus précisément, il est équivalent à cela, dans le sens que tout ce que votre PC peut faire, une machine de Turing peut faire, et tout ce qu'une machine de Turing peut faire, votre PC peut.
spécifiquement, une machine de Turing est un modèle de calcul qui capte complètement la notion de computabilité, tout en restant simple à raisonner, sans tous les détails spécifiques de l'architecture de votre PC.
la "thèse de L'Église-Turing" (généralement acceptée) affirme que chaque dispositif ou modèle de calcul n'est pas plus puissant qu'une machine de Turing. Ainsi, de nombreux problèmes théoriques (par exemple des classes comme P et NP, la notion d ' "algorithme de temps polynomial", et ainsi de suite) sont formellement énoncés en termes d'une machine de Turing, bien que, bien sûr, ils peuvent être adaptés à d'autres modèles comme bien. (Par exemple, parfois, il peut être commode de penser au calcul en termes du calcul lambda, ou la logique combinatoire, ou quoi que ce soit... ils sont tous équivalents en puissance à l'autre, et à votre ordinateur IBM aussi bien.)
donc voilà: les gens parlent de machines de Turing parce que c'est une façon précise et complète de dire ce qu'est un "ordinateur", sans avoir à décrire chaque détail de l'architecture du CPU, ses contraintes, et ainsi de suite.
il y a en fait des exemples de machines de Turing dans la nature. Plus précisément, le ribosome