Crea sito

Cerqueto InForma

Storia, cultura e vita di un paese

Modele de calcul machine de turing

Le biographe de Turing, Andrew Hodges (1983:107) a noté et discuté de cette confusion. Les définitions dans la littérature diffèrent parfois légèrement, pour rendre les arguments ou les épreuves plus faciles ou plus clairs, mais cela est toujours fait de telle sorte que la machine résultante a la même puissance de calcul. Par exemple, la modification de l`ensemble {L, R} {displaystyle {L, R }} à {L, R, N} {displaystyle {L, R, N }}, où N (“none” ou “no-Operation”) permettrait à la machine de rester sur la même cellule de bande au lieu de bouger à gauche ou à droite, n`augmente pas la computationa l puissance. Dans son essai de 1948, “intelligent Machinery”, Turing écrivit que sa machine consistait en: ainsi, les machines Turing prouvent des limitations fondamentales sur la puissance du calcul mécanique. Bien qu`ils puissent exprimer des calculs arbitraires, leur conception minimaliste les rend impropres au calcul dans la pratique: les ordinateurs du monde réel sont basés sur des conceptions différentes qui, contrairement aux machines de Turing, utilisent la mémoire d`accès aléatoire. Aurait-il été possible de choisir une autre langue? Sans aucun doute! L`une des langues complètes de Turing que nous connaissons aujourd`hui aurait pu être utilisée. Mais il aurait été beaucoup plus difficile de construire le terrain théorique sur une machine plus complexe. À l`autre extrême, certains modèles très simples se tournent vers l`équivalent de Turing, c.-à-d. avoir la même puissance de calcul que le modèle de machine de Turing. Plus tôt dans son article Turing a porté ceci encore plus loin: il donne un exemple où il a placé un symbole de la “configuration m” actuelle — l`étiquette de l`instruction — sous le carré scanné, ainsi que tous les symboles sur la bande (The Undecidable, p.

121); Il appelle «la configuration complète» (The Undecidable, p. 118). Pour imprimer la “configuration complète” sur une ligne, il place l`étiquette d`État/m-configuration à gauche du symbole scanné. Dans les modèles à 4 tuples, l`effacement ou l`écriture d`un symbole (AJ1) et le déplacement de la tête à gauche ou à droite (DK) sont spécifiés comme instructions distinctes. Plus précisément, le tableau indique à la machine de (IA) effacer ou écrire un symbole ou (IB) déplacer la tête à gauche ou à droite, puis (II) assumer le même ou un nouvel État comme prescrit, mais pas les deux actions (IA) et (IB) dans la même instruction. Dans certains modèles, s`il n`y a pas d`entrée dans le tableau pour la combinaison actuelle de symbole et d`État, la machine s`arrêtera; d`autres modèles exigent que toutes les entrées soient remplies. La Convention la plus commune représente chaque «instruction de Turing» dans une «table de Turing» par l`un des neuf 5-tuples, selon la Convention de Turing/Davis (Turing (1936) in the Undecidable, p. 126-127 et Davis (2000) p. 152): que l`ensemble du développement et des opérations de l`analyse sont maintenant capables d`être exécutées par des machines. Une machine de Turing est un exemple général d`une CPU qui contrôle toutes les manipulations de données effectuées par un ordinateur, avec la machine canonique utilisant la mémoire séquentielle pour stocker des données.