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...
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...
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...
Nous avons appris le concept d'énumération des fonctions. En pratique, ils correspondent à des langages de programmation. Dans une remarque passagère, le professeur a mentionné que la classe de toutes les fonctions totales (c'est-à-dire les fonctions qui se terminent toujours pour chaque entrée)...
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...
Chaque problème indécidable que je connais tombe dans l'une des catégories suivantes: Problèmes indécidables en raison de la diagonalisation (auto-référence indirecte). Ces problèmes, comme le problème d'arrêt, sont indécidables car vous pourriez utiliser un prétendu décideur pour le langage pour...
Existe-t-il des programmes qui peuvent «traduire» le code source entre deux langues quelconques (en supposant que le traducteur a accès aux bibliothèques requises)? Si oui, comment fonctionnent-elles (techniques utilisées, connaissances requises, etc.)? Comment seraient-ils réalisables? S'ils ne le...
Le combinateur à virgule fixe FIX (alias le combinateur Y) dans le calcul lambda (non typé) ( λλ\lambda ) est défini comme: ≜λf.(λx.f (λy.x x y)) (λx.f (λy.x x y))≜λf.(λx.f (λy.x x y)) (λx.f (λy.x x y))\triangleq \lambda f.(\lambda x. f~(\lambda y. x~x~y))~(\lambda x. f~(\lambda y. x~x~y)) Je...
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...
Notez, bien que je sache programmer, je suis tout à fait un débutant en théorie CS. Selon cette réponse La complétude de Turing est un concept abstrait de calculabilité. Si un langage est Turing complet, il est capable de faire n'importe quel calcul que n'importe quel autre langage complet de...
Il n'y a clairement aucun problème indécidable dans NP. Cependant, selon Wikipedia : NP est l'ensemble de tous les problèmes de décision pour lesquels les cas où la réponse est "oui" ont [.. des preuves qui sont] vérifiables en temps polynomial par une machine de Turing déterministe. [...] Un...
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...
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 . J'ai rencontré de nombreuses définitions de langages récursifs et récursivement énumérables. Mais je ne pouvais pas vraiment...
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 . Je viens de poser cette question intéressante. Quelle est la fonction connaissant la croissance la plus rapide connue de...
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...
Dans la théorie de la calculabilité, les fonctions calculables sont également appelées fonctions récursives. Au moins à première vue, ils n'ont rien de commun avec ce que vous appelez "récursif" dans la programmation quotidienne (c'est-à-dire les fonctions qui s'appellent elles-mêmes). Quelle est...
J'ai étudié quelque chose sur la complexité de Kolmogorov , lu des articles et des livres de Vitanyi et Li et utilisé le concept de la distance de compression normalisée pour vérifier la stilométrie des auteurs (identifier comment chaque auteur écrit des textes et des documents de groupe par leur...
Existe-t-il un langage "naturel" indécidable? par "naturel", j'entends un langage défini directement par les propriétés des chaînes, et non via des machines et leurs équivalents. En d'autres termes, si le langage ressemble à où est un TM, DFA (ou regular-exp), PDA (ou grammaire), etc., alors n'est...
Peut-être que ma compréhension limitée du sujet est incorrecte, mais c'est ce que je comprends jusqu'à présent: La programmation fonctionnelle est basée sur Lambda Calculus, formulée par Alonzo Church. La programmation impérative est basée sur le modèle de machine Turing, fabriqué par Alan Turing,...