Il s'agit d'une question théorique, alors attendez-vous à ce que de nombreux détails ne soient pas calculables en pratique ou même en théorie.ensembles possibles de manipulations de code préservant la sortie
Disons que j'ai une chaîne s que je veux compresser. Le résultat devrait être un binaire auto-extractible (peut être x86 asm mais peut aussi être un autre langage hypothétique Turing-complete low-level) qui produit s.
Maintenant, nous pouvons facilement parcourir tous les binaires/programmes possibles, classés par taille. Soit B_s être la sous-liste de ces binaires qui sortent s (bien sûr B_s est uncomputable).
Comme chaque ensemble d'entiers positifs doit avoir un minimum, il doit y avoir un plus petit programme b_min_s dans B_s
De s, je peux aussi construire un programme canonique b_cano_s qui sort juste s de manière triviale. C'est à dire. la taille de b_cano_s sera en O(#s) - si nous pensons à ELF avec des segments de données, nous aurons même #b_cano_s ~ #s.
Y at-il un ensemble A d'opérations possibles sur les binaires qui:
1. Préserve la sortie.
2a. Compte tenu b_cano_s, nous pouvons arriver en quelque sorte par des opérations de A au b_min_s.
(2b. Compte tenu b_cano_s, nous pouvons arriver à tous les programmes B_s.)
pour toutes les chaînes possibles s.
Les conditions 1 + 2a sont plus faibles que les conditions 1 + 2b. Peut-être, s'il y a un tel ensemble A, nous aurons automatiquement les deux, cependant. (Est-ce le cas?)
Existe-t-il un tel ensemble A? Je pensais à des opérations évidentes, comme chercher des chaînes répétées et raccourcir cela. Ou certaines des autres méthodes de compression courantes. Cependant, ce n'est probablement pas suffisant pour arriver à tous les programmes B_s et mon intention ne dit pas nécessairement non plus à b_min_s pour la même raison.
S'il existe, pouvons-nous l'exprimer, c'est-à-dire s'il est calculable?