Questions concernant le problème d'arrêt qui consiste à décider si un programme donné s'arrête sur une entrée donnée.
Je ne comprends pas pourquoi le problème de l' arrêt est si souvent utilisé pour écarter la possibilité de déterminer si un programme est interrompu. Le [article] [1] de Wikipedia explique correctement qu'une machine déterministe à mémoire finie arrêtera ou répétera un état antérieur. Vous pouvez...
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...
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 comprends la preuve de l'indécidabilité du problème d'arrêt (donnée par exemple dans le manuel de Papadimitriou), basée sur la diagonalisation. Bien que la preuve soit convaincante (j'en comprends chaque étape), elle n'est pas intuitive pour moi en ce sens que je ne vois pas comment quelqu'un 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...
Il est assez simple de comprendre pourquoi le problème d'arrêt est indécidable pour les programmes impurs (c'est-à-dire ceux dont les E / S et / ou les états dépendent de l'état global de la machine); mais intuitivement, il semble que l'arrêt d'un programme pur sur un ordinateur idéal serait...
Je regardais les " Cinq étapes de l'acceptation des mathématiques constructives " d'Andrej Bauer et il dit qu'il y a deux types de preuves par contradiction (ou deux choses que les mathématiciens appellent preuve par contradiction): Supposons que est faux ... bla bla bla, contradiction. Par...
Comme des trous noirs en informatique. Nous pouvons seulement savoir qu'ils existent, mais lorsque nous en aurons un, nous ne saurons jamais que c'est l'un
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 7 ans . "Alan Turing a prouvé en 1936 qu'un algorithme général pour résoudre le problème d'arrêt pour toutes les paires d'entrée de...
Une machine de Turing qui revient à un état rencontré précédemment avec sa tête de lecture / écriture sur la même cellule de la même bande exacte sera prise en boucle. Une telle machine ne s'arrête pas. Quelqu'un peut-il donner un exemple d'une machine sans arrêt qui ne boucle...
J'ai récemment entendu une analogie intéressante qui déclare que la preuve de Turing de l'indécidabilité du problème d'arrêt est très similaire au paradoxe du barbier de Russell. Je me suis donc demandé: les mathématiciens ont finalement réussi à rendre la théorie des ensembles cohérente en passant...
D'après ma compréhension de la preuve que le problème d'arrêt n'est pas calculable, ce problème n'est pas calculable parce que si nous avons un programme P (x) qui calcule si le programme x s'arrête ou non, nous avons un paradoxe lorsque nous donnons P comme entrée au même P, ayant: P (P), essayant...
Serait-il possible pour un environnement d'exécution de détecter des boucles infinies et d'arrêter par la suite le processus associé, ou la mise en œuvre d'une telle logique équivaudrait-elle à résoudre le problème d'arrêt? Aux fins de cette question, je définis une «boucle infinie» pour désigner...
La définition principale de la machine de Turing (TM), au moins dans mon propre manuel de référence (Hopcroft + Ullman 1979) est déterministe. Par conséquent, ma propre compréhension du problème de l' arrêt concerne principalement la MT déterministe, bien que je sache qu'il peut être envisagé pour...
Existe-t-il une machine de Turing qui s'arrête sur toutes les entrées mais cette propriété n'est pas prouvable pour une raison quelconque? Je me demande si cette question a été étudiée. Remarque: «non démontrable» pourrait signifier un système de preuve «limité» (qui au sens faible pense que la...
Il existe des temps spatiaux relativistes (par exemple des temps spatiaux MH; voir Hogarth 1994) où une ligne du monde de durée infinie peut être contenue dans le passé d'un observateur fini. Cela signifie qu'un observateur normal peut avoir accès à un nombre infini d'étapes de calcul. En supposant...
J'ai le problème: Montrez qu'il existe un nombre réel pour lequel aucun programme n'existe qui s'exécute infiniment long et écrit les chiffres décimaux de ce nombre. Je suppose que cela peut être résolu en le réduisant au problème de l'arrêt, mais je ne sais pas comment le faire. J'apprécierais...
J'ai lu dans Wikipedia et dans quelques autres textes Le problème d'arrêt est décidable [...] pour les automates linéaires bornés (LBA) et les machines déterministes à mémoire finie. Mais plus tôt, il est écrit que le problème d'arrêt est un problème indécidable et donc TM ne peut pas le résoudre!...
J'ai du mal à comprendre le problème de l'arrêt de Turing. Sa preuve suppose qu'il existe une machine magique qui pourrait déterminer si un ordinateur s'arrêterait ou ferait une boucle pour toujours pour une entrée donnée. Ensuite, nous attachons une autre machine qui inverse la sortie et nous...