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 pour laquelle les machines de Turing sont un gros problème est liée à l’étude de sujets classiques du type science informatique ou théorie du calcul. Il s’agit essentiellement d’analyser les propriétés générales d’un ordinateur, telles que les capacités et les limites théoriques d’un ordinateur, ainsi que ce que nous entendons par & "Informatique &"; quelque chose.

Un exemple de ce que l’on pourrait étudier avec Turing Machines est le Le problème de l’arrêt . Même s’il s’agit d’un exercice théorique, ce problème a des implications concrètes et concrètes. Pourquoi ne pas écrire un débogueur qui vous dira simplement si votre programme contient des boucles infinies? Le problème de l'arrêt établit qu'il est impossible de résoudre ce problème pour le cas général.

L’étude des machines de Turing se prête également à l’étude des grammaires des langues et de leurs classes, ce qui conduit au développement du langage de programmation. Le terme & Quot; expressions régulières & Quot; vient du fait qu’il s’agit d’une grammaire régulière et de l’étude de ces grammaires (partie de Theory of Computation) ) vous en dira plus sur les types de problèmes que les expressions régulières peuvent résoudre et ce qu’ils ne peuvent pas. Par exemple, une syntaxe d'expression régulière traditionnelle ne pourra pas résoudre le problème suivant: analyser un nombre N de caractères 'a' en entrée, puis analyser le même nombre N de caractère 'b'.

Si vous êtes intéressé par un texte intéressant sur ce genre de chose, consultez Introduction. à la théorie du calcul par Michael Sipser. C'est bon.

Answer 2

La machine de Turing est une machine à calcul théorique inventée par Alan Turing pour servir de modèle idéalisé de calcul mathématique. Il s’agit essentiellement d’une forme informatique simple, composée d’un ruban (un ruban de papier). ), a une tête capable de lire les symboles, d’écrire un nouveau symbole à la place, puis de se déplacer à 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 bouger.

Voici une machine de Turing de base , implémentée en JavaScript ...

Et un croquis:

Answer 3

  

Mon PC IBM est tout ce dont j'ai besoin pour faire mes calculs!

Quelque chose que d’autres n’ont pas signalé: votre PC IBM est une machine de Turing. Plus précisément, cela équivaut à cela, en ce 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 le faire.

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

La (généralement acceptée) & "Thèse de l'Eglise-Turing" & "; affirme que chaque appareil 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 telles que P et NP, la notion de & Quot; algorithme polynomial de temps & Quot ;, etc.) sont formellement formulés en termes de machine de Turing, bien que, bien sûr, ils peuvent également être adaptés à d'autres modèles. (Par exemple, il peut parfois être pratique de penser au calcul en termes de calcul lambda, ou de logique combinatoire, ou quoi que ce soit d'autre ... ils ont tous une puissance équivalente les uns aux autres, ainsi qu'à votre PC IBM.)

Alors 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 &"; est, sans avoir à décrire chaque détail de l'architecture de la CPU, ses contraintes, etc.

.

Answer 4

Il existe en fait des exemples de machines de Turing dans la nature. Plus précisément, le ribosome , qui traduit l’ARN en protéines, met en oeuvre une machine de Turing.

D'abord, quelques informations de base:

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 directionnelles: par convention les extrémités sont appelées cinq primes et trois primes (5 ', 3')
4. Une base dans une chaîne d'ARN peut attirer une base sur une autre chaîne d'ARN en & complémentaire; anti-parallèle paires " ;, où A colle à U et C colle à G.
5. Les bases sont combinées en groupes de 3 pour former & Quot; codons & Quot; (mots).
6. Il y a 64 combinaisons possibles pour les codons (4 ^ 3).
7. chaque codon peut correspondre à un & "anti-codon &"; par exemple AUG < - > UAC
8. il existe des molécules porteuses spéciales (" ARNt ") qui ont notamment anticodons et sont attachés à acides aminés spécifiques (protéines).

Le fonctionnement du ribosome est simple:

1. la transcription commence à un & début; codon " ;, qui définit la " lecture cadre "
2. la transcription se déroule toujours dans le sens 5 '- > 3'
3. le codon sous le cadre de lecture est apparié avec un ARNt spécifique contenant un acide aminé spécifique
4. le codon de départ code toujours le acide aminé méthionine.
5. le nouvel acide aminé est lié à la protéine en croissance
6. la trame avance alors de 3 bases au codon suivant et la protéine est étendue en permanence
7. en rencontrant un " stop " codon, la traduction est terminée, aucun acide aminé n’est attaché et le ribosome se dissocie de l’ARNm.

Comme vous pouvez le constater, il s’agit d’une machine de Turing très simple qui effectue l’opération la plus complexe: la nature elle-même!

Answer 5

Une machine de Turing est une machine théorique qui permet de raisonner sur les limites des ordinateurs. En termes simples, c’est un ordinateur imaginaire avec une mémoire infinie.

Les machines Turing nous intéressent, car elles nous aident à découvrir ce qui est impossible à accomplir avec de vrais ordinateurs (comme votre PC IBM). S'il est impossible pour une machine de Turing d'effectuer un calcul particulier (comme décider du Problème stoppant ), il est donc logique que votre PC IBM ne puisse pas effectuer le même calcul.

Answer 6

Pourquoi les concepteurs d’avions se soucient-ils des Wright Brothers ou de la science derrière & "Lift &"; qui permet aux aéronefs à voilure fixe de voler?

Alan Turing est considéré comme le père de l’informatique moderne. La machine de Turing est le précurseur de tous les ordinateurs modernes.

La théorie de la calculabilité était ma classe la plus difficile au collège, mais je suis heureux de l'avoir suivie. Cela m'a fait penser à des choses que je n'aurais jamais ou à des choses que je n'aurais jamais faites, et ce sont de bonnes choses.

Answer 7

Une machine de Turing est une machine abstraite capable de calculer.

Sur Wikipedia:

  

Les machines de Turing sont des dispositifs de base abstraits de manipulation de symboles qui, malgré leur simplicité, peuvent être adaptés pour simuler la logique de tout algorithme informatique. Ils ont été décrits en 1936 par Alan Turing. Les machines de Turing ne sont pas conçues comme une technologie informatique pratique, mais comme une expérience de réflexion sur les limites du calcul mécanique. Ainsi, ils n'ont pas été réellement construits. L'étude de leurs propriétés abstraites fournit de nombreuses informations sur l'informatique et la théorie de la complexité.

     

Une machine de Turing capable de simuler n’importe quelle autre machine de Turing est appelée machine de Turing universelle (UTM ou simplement une machine universelle). Une définition plus mathématique avec un & "Universel &" Similaire; La nature a été introduite par Alonzo Church, dont les travaux sur le calcul lambda étaient étroitement liés à ceux de Turing dans une théorie formelle de l'informatique connue sous le nom de thèse de Church-Turing. La thèse indique que les machines de Turing capturent bien la notion informelle de méthode efficace en logique et en mathématiques et fournissent une définition précise d'un algorithme ou d'une "procédure mécanique".

Answer 8

La machine Turing est une machine abstraite capable d’opérer sur une séquence de données et de modifier son propre état ainsi que les données en cours de fonctionnement, conformément à une logique.

C’est un concept qui forme la base des algorithmes, des programmes stockés et du calcul en général. Il fournit de bonnes idées et des abstractions si vous utilisez des algorithmes, des états, des données, etc.

Matière à réflexion, pour la plupart.

Answer 9

En plus de l'entrée Wikipedia, vous pouvez choisir le livre The Annotated. Turing de Charles Petzold. Sous-titré & "Une visite guidée du document historique d'Alan Turing sur la calculabilité et la machine de Turing &"; Il comprend le document complet, scindé en morceaux avec de nombreux discours sur le sujet, y compris une perspective historique.

Answer 10

La machine de Turing est équivalente à un algorithme. Il s'arrête lorsqu'il accepte une chaîne, rejette ou entre une boucle infinie lorsqu'il n'accepte pas la chaîne.

La bande agit comme une mémoire, les règles de transition agissent comme des conditions "if then else"