Ce programme de 579 bits dans le calcul binaire Lambda a un état d'arrêt inconnu: 01001001000100010001000101100111101111001110010101000001110011101000000111001110 10010000011100111010000001110011101000000111001110100000000111000011100111110100
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...
Il existe de nombreuses façons de définir la complexité de Kolmogorov et, généralement, toutes ces définitions sont équivalentes jusqu'à une constante additive. C'est-à-dire que si et sont des fonctions de complexité de kolmogorov (définies via différents langages ou modèles), alors il existe une...
Selon Wikipedia : Informellement, du point de vue de la théorie algorithmique de l'information, le contenu informationnel d'une chaîne équivaut à la longueur de la représentation autonome la plus courte possible de cette chaîne. Quelle est la définition rigoureuse informelle analogue des...
Je lisais l'entrée de Wikipedia sur la complexité de Kolmogorov ( grâce à cette question ), qui dit: Il peut être démontré que la complexité de Kolmogorov d'une chaîne ne peut pas dépasser de quelques octets la longueur de la chaîne elle-même. Pourquoi auriez-vous besoin de quelque chose de plus...
La méthode d'incompressibilité simplifierait l'analyse des algorithmes pour le cas moyen. D'après ce que je comprends, c'est parce qu'il n'est pas nécessaire de calculer toutes les combinaisons possibles d'entrée pour cet algorithme et de dériver ensuite une complexité moyenne. Au lieu de cela, une...
En classe, notre professeur nous a montré 3 méthodes pour prouver la non-régularité: Théorème de Myhill – Nerode Pompage du lemme pour les langues régulières Preuve de non-régularité, basée sur la complexité de Kolmogorov Maintenant les deux premiers, le théorème de Myhill-Nerode et le lemme de...