Questions sur les machines de Turing, un modèle théorique de calcul mécanique capable de simuler n'importe quel programme informatique.
Je suis un étudiant de premier cycle en CS. Je comprends comment Turing a créé sa machine abstraite (modéliser une personne effectuant un calcul), mais cela me semble être une abstraction maladroite et inélégante. Pourquoi considérons-nous une "bande" et une tête de machine écrivant des symboles,...
Nous savons que le problème d’arrêt (sur les machines de Turing) est indécidable pour les machines de Turing. Y a-t-il des recherches sur la capacité de l'esprit humain à gérer ce problème, éventuellement avec l' aide de Turing Machines ou d'ordinateurs à usage général? Note : Évidemment, dans le...
Existe-t-il un ensemble de constructions de langage de programmation dans un langage de programmation afin que celui-ci soit considéré comme Turing Complete? D'après ce que je peux dire sur wikipedia , la langue doit prendre en charge la récursion ou, apparemment, doit pouvoir fonctionner sans...
Je conviens qu'une machine de Turing peut résoudre "tous les problèmes mathématiques possibles". Mais c’est parce qu’il ne s’agit que d’une représentation machine d’un algorithme: faites ceci en premier, puis faites-le, et enfin en sortie. Je veux dire que tout ce qui peut être résolu peut être...
Dans le calcul quantique, quel est le modèle équivalent d'une machine de Turing? Il est tout à fait clair pour moi que les circuits quantiques puissent être construits à partir de portes quantiques, mais comment pouvons-nous définir une machine de Turing quantique (QTM) pouvant réellement...
Dans cette réponse, il est mentionné Un langage régulier peut être reconnu par un automate fini. Un langage sans contexte nécessite une pile et un langage sensible au contexte nécessite deux piles (ce qui revient à dire qu'il nécessite une machine Turing complète) . Je voulais savoir en ce qui...
Existe-t-il des machines théoriques dépassant les capacités des machines de Turing dans au moins certaines
Je vois que la plupart des définitions de ce que signifie être Turing-complet sont, dans une certaine mesure, tautologiques. Par exemple, si vous Google "que signifie Turing Complete", vous obtenez: Un ordinateur est complet à Turing s'il peut résoudre tout problème qu'une machine de Turing peut...
Alan Turing a proposé un modèle pour une machine (la Turing Machine, TM) qui calcule (nombres, fonctions, etc.) et a démontré le théorème de Halting . Une MT est un concept abstrait d'une machine (ou d'un moteur si vous le souhaitez). Le théorème de l'arrêt est un résultat impossible. Un moteur...
Je passais par la discussion sur la question Comment définir les machines de Turing quantiques? et je sens que TM quantique et TM non déterministe sont une seule et même chose. Les réponses à l'autre question ne touchent pas à cela. Ces deux modèles sont-ils identiques? Sinon, Quelles sont les...
La thèse de Church-Turing déclare que tout ce qui peut être physiquement calculé, peut être calculé sur une machine de Turing. L'article «Analog computation via neural networks» (Siegelmannn et Sontag, Theoretical Computer Science , 131: 331–360, 1994; PDF ) affirme qu'un réseau neuronal d'une...
Cette question a été migrée à partir de la bourse théorique de l'informatique, car elle peut être répondue sur la bourse de la science informatique. Migré il y a 6 ans . Je lis actuellement un livre sur les algorithmes et la complexité. En ce moment, je suis en train de lire sur les fonctions...
Voulez-vous améliorer ce post? Fournissez des réponses détaillées à cette question, y compris des citations et une explication de la raison pour laquelle votre réponse est correcte. Les réponses sans suffisamment de détails peuvent être modifiées ou supprimées. J'ai rencontré ci-dessous la...
Wikipédia ainsi que d'autres sources que j'ai trouvées listent le voidtype C comme type d'unité par opposition à un type vide. Je trouve cela déroutant car il me semble que cela voidcorrespond mieux à la définition d'un type vide / bas. Autant voidque je sache , aucune valeur n'habite . Une...
Le problème d'arrêt indique qu'aucun algorithme ne déterminera si un programme donné s'arrête. En conséquence, il devrait y avoir des programmes sur lesquels nous ne pouvons pas dire s'ils se terminent ou non. Quels sont les exemples les plus simples (les plus petits) connus de tels...
Je fais une présentation sur les machines Turing et je voulais donner quelques informations sur les FSM avant de présenter les machines Turing. Le problème est que je ne sais vraiment pas ce qui est TRÈS différent les uns des autres. Voici ce que je sais que c'est différent: FSM a des états...
Récemment, dans ma classe CS, j'ai découvert la machine de Turing. Après le cours, j'ai passé plus de 2 heures à essayer de comprendre quelle est la relation entre une bande et une machine. J'ignorais complètement l'existence des bandes d'ordinateurs ou la façon dont les bandes et les machines...
Je suis ingénieur électricien et je n'avais qu'un seul cours CS au collège il y a 26 ans. Cependant, je suis également un utilisateur dévoué de Mathematica. J'ai le sentiment que les machines de Turing sont très importantes en informatique. L'importance n'est-elle que dans la théorie de...
En considérant uniquement l'alphabet , les chaînes qui peuvent être données en entrée aux machines de Turing proviennent de l'ensemble . Mais est-il logique que l'entrée soit une chaîne binaire infinie? Par exemple, si une machine Turing accepte toutes les chaînes commençant par un 0, une chaîne...
J'ai du mal à comprendre la preuve de l'indécidabilité du problème de l'arrêt. Si renvoie si le programme s'arrête ou non sur l'entrée , pourquoi devons-nous passer le code de pour et ?a b P a bH( a , b )H(a,b)H(a,b)uneaabbbPPPuneaabbb Pourquoi ne pouvons-nous pas alimenter avec et une entrée...