Les machines de Turing sont similaires aux automates finis/machines à états finis mais ont l'avantage d'une mémoire illimitée … Elles sont capables de simuler des ordinateurs courants; un problème qu'un ordinateur ordinaire peut résoudre (avec suffisamment de mémoire) pourra également être résolu à l'aide d'une machine de Turing, et vice versa.
Quelle est la différence entre RAM et TM ?
Une machine de Turing ne peut pas Une machine RAM peut faire de l'arithmétique en O(1) (sous certaines restrictions). Une machine de Turing ne le peut pas. Les machines de Turing simulent polynomialement les machines RAM, c'est-à-dire que pour une certaine constante c, toute machine RAM fonctionnant dans le temps O(nk) peut être simulée par une machine de Turing fonctionnant dans le temps O(nck).
La bande d'une machine de Turing est-elle illimitée ?
Une machine de Turing (TM) est une machine à états composée de deux mémoires: une bande illimitée et une table de contrôle à états finis. La bande contient des données sous forme de symboles. La machine a un très petit ensemble d'opérations appropriées, 6 en tout (lire, écrire, se déplacer vers la gauche, se déplacer vers la droite, changer d'état, s'arrêter) sur la bande.
Pourquoi la machine de Turing est-elle puissante ?
Quelle est la puissance des machines de Turing ? Les machines de Turing peuvent accepter n'importe quel langage régulier ou sans contexte. Les machines de Turing peuvent effectuer des calculs arithmétiques de base … La thèse de Turing stipule que tout calcul pouvant être effectué par des "moyens mécaniques" peut être effectué par une machine de Turing (en ignorant les problèmes d'efficacité).
Les machines de Turing peuvent-elles boucler indéfiniment ?
turing(turingDescrip) ne peut ni s'arrêter ni boucler indéfiniment; ça n'a aucun sens de toute façon.
