Du plus petit programme générant un entier

La culture en toute liberté.
Aller à : Navigation, rechercher

Sommaire

Résumé

On se propose ici de discuter de la faisabilité d'un programme générant le plus petit programme générant un nombre entier. L'idée derrière cette réflexion est celle de trouver des optima dans la compression de données.

Faisabilité et décidabilité

Avant de tenter de concevoir un algorithme réalisant la tâche qu'on se fixe avec des performances qui le rende utile en pratique, nous allons commencer par nous demander si notre problème peut être résolut par un algorithme tout court.

Pour tout nombre entier on connaît un programme susceptible de le générer pour peu qu'on dispose d'un espace de stockage suffisant. La fonction successeur permet par exemple de faire cela. Tout nombre entier est donc générable algorithmiquement.

De plus on peu énumérer tous les programmes d'un langage quelconque, en partant du plus petit possible, et testant si en sortie il produit l'entier attendu. Le premier programme trouvé qui donne le résultat attendu est le plus petit programme qui génère ce nombre.

Mais pour savoir si un programme produit l'entier attendu il faut qu'il termine, et donc qu'on sache s'il termine[1]. Il faudrait donc pouvoir décider si chaque programme généré termine. Ce qui est, comme il est connu, impossible[2].

Nous pouvons cependant nous en sortir en modifiant quelque peu notre énoncé de départ. En effet, au fond peu nous importe d'obtenir le programme le plus compacte pour générer notre nombre, si celui-ci termine (éventuellement) au bout de quelques milliers d'années en produisant le résultat escompté. Nous désirons obtenir des programmes (fichiers compressés) certes compacte, mais dont l'exécution reproduit notre nombre (fichier de départ) en un temps qui nous est utile. Éventuellement, on trouvera acceptable d'attendre une semaine pour récupérer plusieurs péta-octets de données à partir de quelques centaines de kilo-octets, on ne sera peut être pas aussi patient pour quelques documents qui à la base ne font que quelques méga-octets.

Ainsi on peut imaginer un programme qui énumère et exécute i programmes par ordre croissant, i indexant les programmes de 0 à un n ; n indéterminé au départ. Pour chaque programme, on mémorise t[i], l'instant où le i-ème programme démarre. Lorsqu'un problème s'arrête avec la bonne sortie, on affecte son rang à n. On arrête alors de générer et de lancer de nouveaux programmes et on scrute les programmes encore en exécution pour les stopper lorsque leur temps total d’exécution dépasse t[n]. Dans le pire des cas, au bout de 2×t[n], plus aucun programme ne tourne. Éventuellement d'autres programmes retournant la sortie attendue ont été découverts. Un rapide comparatif permet de déterminer le(s) programme(s) ayant le meilleur rapport poids/ temps d’exécutions.

Il est donc algorithmiquement possible de déterminer le programme ayant le meilleur rapport poids/temps d’exécutions, c'est à dire le plus petit programme parmi les programmes qui s’exécute en un minimum de temps pour générer un nombre donnée.

Nous voilà donc rassuré, sur la possibilité, dans l'absolu, de trouver un programme tel que nous nous sommes posé de chercher, ou tout du moins, très proche de notre idée de départ. Cependant l'algorithme proposé ici n'est pas utilisable en pratique, générer et exécuter l'ensemble des n premiers programmes d'un langage donnée n'est évidemment pas envisageable en terme de ressources, et encore moins en terme d'intérêt utilitaire.

Il nous faut donc maintenant chercher s'il existe un algorithme qui étant donné un nombre quelconque, renvois le plus petit programme parmi les programmes qui s’exécute en un minimum de temps pour générer ce nombre, dans un délais acceptable et en utilisant des ressources acceptables.

Définition d'un code (éventuellement) compresseur

Nous allons maintenant définir un code permettant de représenter des nombres entiers, sous forme binaire, mais (éventuellement) autre que dans le codage habituelle en base deux. Pour cela notre code se divisera en deux sous-codes, l'un représentant des nombres, l'autre des opérateurs arithmétiques. La permutation d'un sous code à l'autre se faisant par un code commun au deux. De plus on pose que le plus petit mot utilisable est l'octet. Par défaut on considérera qu'on est en mode nombre.

Table du code
Code (espaces non significative) Signification en mode nombre Signification en mode opérateur
1111 1111 passage en mode opérateur passage en mode nombre
0000 0000 le nombre zéro (0) mise en exposant
00000001 00000000 255 pas encore défini

Les opérateurs seront placés de manière infixe.

Ainsi, au lieu de coder 8 comme 0000 1000, on pourrait coder <math>2^3</math> comme suis :

0000 0010 1111 1111 0000 0000 1111 1111 0000 0011
2 permutation en mode opérateur puissance permutation en mode nombre 3

Évidemment, 5 octets au lieu de un seul cela n'est guère intéressant. En revanche si l'on code <math>42^{42}</math> on aura :

101010 11111111 00000000 11111111 101010

au lieu de :

00000101 10010001 10010100 00010111 11001101 01101010 00010001 11011011 11011111 00101111 01000001 00110110 01010111 10111011 11000000 00111011 11001000 01000010 10101100 01110110 11101111 00111001 00110010 01100100 00000000 00000000 00000000 00000000 00000000

Soit toujours 5 octets, là où il en faut 29 pour la représentation classique.

Notes et références

  1. Merci à Jérémie Koenig pour la remarque
  2. Voir https://secure.wikimedia.org/wikipedia/fr/wiki/Problème_de_l'arrêt

Informations légales

Cette œuvre est basée sur une œuvre originale sous licence art libre.

Source :

Auteurs de l'œuvre originale : psychoslave

Licences : N/A

Outils personnels
Espaces de noms

Variantes
Actions
Wiki
Communauté
Dépôt multimedia
Boîte à outils