Qu'est-ce qu'une machine de Turing?

Question

Qu'est-ce qu'une machine de Turing et pourquoi les gens ne cessent de le mentionner? Mon PC IBM est tout ce dont j'ai besoin pour faire mes calculs! Pourquoi est-ce que quelqu'un se soucie de ces machines?

Answer 1

La raison que les Machines de Turing sont un gros problème a à voir avec l'étude des classiques de l'Informatique ou de la Théorie de Calcul des trucs de type. Il s'agit essentiellement d'analyser les propriétés générales d'un ordinateur, tels que théorique capacités et les limites d'un ordinateur, ainsi que ce que nous entendons lorsque nous parlons de "calcul" de quelque chose.

Un exemple de quelque chose que l'on peut étudier à l'aide des Machines de Turing est Le Problème de l'Arrêt. Alors que ce problème est en quelque sorte un exercice académique, il a facilement tangible dans le monde réel implications. Pourquoi ne pas écrire un débogueur qui va tout simplement vous dire si oui ou non votre programme contient une boucle infinie? Le Problème de l'Arrêt établit que la résolution de ce problème dans le cas général est impossible.

L'étude des Machines de Turing se prête également à l'étude de la langue des grammaires et des catégories de ceux-ci, qui mène dans le langage de programmation du développement. Le terme "expressions régulières" vient à propos, car ils sont un ordinaire de la grammaire, et l'étude de ces grammaires (partie de la Théorie de Calcul) pour en savoir plus sur exactement quels types de problèmes sont les expressions régulières peuvent résoudre et qu'ils ne peuvent pas. Par exemple, un traditionnelle la syntaxe d'expression régulière ne sera pas en mesure de résoudre le problème suivant: analyser un certain nombre N de 'a' caractères en entrée, et ensuite d'analyser le même nombre N de char "b".

Si vous êtes intéressés par un bon texte sur ce genre de chose, découvrez Introduction à la Théorie de Calcul par Michael Sipser. Que c'est bon.

Answer 2

La machine de Turing est un calcul théorique de la machine inventée par Alan Turing pour servir de modèle idéalisé de calcul mathématique, fondamentalement, de son une forme simple de l'ordinateur, son composé par une bande, d'un ruban de papier, a une tête qui peut lire les symboles, écrire un nouveau symbole en place, puis aller à gauche ou à droite.

La machine de Turing est dit être dans un certain état, et ensuite un programme est une liste de transitions, d'avoir un état actuel et un symbole de la tête, ce qui devrait être écrit sur la bande, ce qui serait le prochain état, et où le chef doit se déplacer.

Voici une de Base de la Machine de Turing, implémenté en JavaScript...

Et un croquis:

Answer 3

Mon PC d'IBM est tout ce que je dois faire mon calcul!

Quelque chose que les autres n'ont pas souligné: Votre IBM PC est une machine de Turing. Plus précisément, c'est l'équivalent, dans le sens que tout ce que votre PC peut faire, une machine de Turing peut faire, et de tout ce qu'une machine de Turing peut faire de votre PC peut.

Plus précisément, une machine de Turing est un modèle de calcul qui a complètement capture la notion de compilation, tout en restant simple à comprendre, sans tous les détails de votre PC à l'architecture.

L' (généralement reconnus) "thèse de Church-Turing", affirme que chaque appareil ou d'un modèle de calcul n'est pas puissant qu'une machine de Turing. Donc, de nombreux problèmes théoriques (par exemple des classes P et NP, la notion de "polynôme en temps de l'algorithme", et ainsi de suite) sont formellement indiqué dans les termes d'une machine de Turing, même si bien sûr ils peuvent être adaptés à d'autres modèles ainsi. (Par exemple, parfois, il peut être commode de penser de calcul en termes du lambda calcul, ou de la logique combinatoire, ou quoi que... ils sont tous équivalent en puissance à chaque autre, et à votre PC d'IBM en tant que bien.)

Donc là vous allez: les gens parlent des machines de Turing, car il est précis et complet spécifié façon de dire ce qu'est un "ordinateur" est, sans avoir à décrire chaque détail de l'architecture du CPU, de ses contraintes, et ainsi de suite.

Answer 4

Il y a en fait des exemples de Machines de Turing dans la nature. Plus précisément, le ribosome, qui se traduit par de l'ARN en protéines, met en œuvre une Machine de Turing.

D'abord, un peu de contexte:

1. L'ARN est composé d'une chaîne de nucléotides ("bases"), qui définissent les lettres de l'alphabet génétique.
2. Il y a 4 bases dans l'ARN alphabet - A, C, G, U.
3. Les Bases sont directionnelle: par de la convention les extrémités sont appelés cinq premier et les trois premier (5', 3')
4. Une base dans un ARN chaîne peut attirer une base sur un autre ARN chaîne "anti-parallèles complémentaires paires", où Un des bâtons de U et C bâtons de G.
5. Les bases sont combinés dans les groupes de 3 pour former "codons" (mots).
6. Il y a 64 combinaisons possibles pour les codons (4^3).
7. chaque codon peut correspondre à un "anti-codon". par exemple AUG <-> contrôle de compte d'utilisateur
8. il y a des molécules vectrices ("arnt"), qui ont notamment des anticodons et sont attachés à certains acides aminés (protéines).

Le fonctionnement du ribosome est simple:

1. la transcription initie à un "start codon", qui définit la "lecture cadre"
2. la transcription toujours le produit dans la 5'->3' direction
3. le codon en vertu du cadre de lecture est jumelé à un arnt spécifique contenant un acide aminé spécifique
4. le codon de départ toujours le code de la acide aminé Méthionine.
5. le nouvel acide aminé est attaché à la croissance de la protéine
6. le cadre, puis des avances 3 bases pour la prochaine codon, et la protéine est continuellement étendu
7. lors de la rencontre d'un "stop" codon, la traduction est terminée, aucun acide aminé est attaché et le ribosome se dissocie de l'arnm.

Comme vous pouvez le voir, c'est très simple Machine de Turing qui effectue la plus complexe des opérations de la nature elle-même!

Answer 5

Une Turing machine est théorique de la machine qui peut être utilisé à raison à propos des limites des ordinateurs. Tout simplement, c'est un ordinateur imaginaire avec l'infini de la mémoire.

Nous nous soucions de Turing-machines parce qu'ils nous aider à découvrir ce qui est impossible à réaliser avec de vrais ordinateurs (comme votre IBM PC). S'il est impossible pour une machine de Turing pour effectuer un calcul particulier (comme décider le Problème de l'Arrêt), alors il va de soi qu'il est impossible pour votre IBM PC pour effectuer le même calcul.