Qu'est-ce qu'une explication profane de la recherche universelle?

Je suis en train de lire un livre sur un sujet informatique, mais je manque de connaissances préalables. Normalement, lorsque je rencontre des termes que je ne comprends pas, je les recherche simplement, mais pour la recherche universelle, je n'ai tout simplement pas été en mesure de trouver une explication appropriée pour un lecteur sans formation en statistique / informatique.

J'ai lu cet article sur la recherche universelle de Scholarpedia , qui semble couvrir le sujet. J'apprécierais une explication de ce que signifie la recherche universelle (ou recherche Levin ).

Pensez-y comme ça. Vous avez un problème avec l'entrée et vous savez comment vérifier une solution si vous en avez trouvé une (comme l'inverse d'une matrice ou tout ce que vous aimeriez imaginer).$x$

Maintenant, prenez votre langage de programmation préféré (par exemple Python) et créez chaque programme Python composé d'au plus 10 caractères! Ensuite, vous exécutez tous ces programmes avec votre entrée pendant 10 secondes chacun, chacun sur l'entrée . Si aucun d'entre eux ne vous donne la réponse, vous allez jusqu'au 11. Exécutez chaque programme d'au plus 11 caractères (y compris ceux que vous avez déjà essayés, bien sûr) pendant 11 secondes chacun, sur l'entrée . Si aucun d'eux ne vous donne la bonne réponse, vous passez à 12 et ainsi de suite.$x$$x$

Plus formellement, dans l'itération , vous exécutez tous les programmes de longueur au plus i (en nombre fini, mais bien sûr exponentiel en i ), chacun pendant i secondes (ou pas).$i$$i$$i$$i$

$P$$s$$i = \max\{|P|, s\}$$s$$P$

Juste pour ajouter à ce que Pål GD a dit, rappelez-vous que vous exécutez tous les programmes de longueur ou moins et que vous les laissez fonctionner pendant au plus secondes. Il se peut donc qu'il existe un programme qui obtient la bonne réponse de 100 caractères, mais cela prend 120 secondes pour s'exécuter. Appelez ce programme . Sur vous vérifierez ce programme, mais son exécution est trop longue, vous le rejetez donc. Après avoir vérifié tous les programmes de longueur 100, vous ne trouvez aucun d'eux qui donne la bonne réponse, vous essayez donc les programmes de longueur et tous les programmes que vous avez essayés auparavant . Donc, vous réessayez$i$$i$$P$$i=100$$101$ $P$, le programme qui (nous le savons) vous donnera la bonne réponse, mais il prend encore trop de temps pour que vous le jetiez. Nous continuons ce processus jusqu'à ce que nous arrivions à . Ensuite, nous essayons tous les programmes de longueur , et quand nous arrivons à nous le laissons fonctionner suffisamment longtemps pour qu'il donne la bonne réponse. Ensuite, nous nous arrêtons - nous avons trouvé l'algorithme que nous voulions. L'itération sur laquelle nous sommes est , car bien que la longueur du programme soit inférieure (nous écririons ), nous avons dû attendre jusqu'à 120 secondes ( ). Donc signifie simplement le maximum de la longueur du programme$i=120$$\leq 120$$P$$i = 120$$P$$|P|=100$$s=120$$i=\mathrm{max}\{|P|,s\}$$P$et le temps qu'il a fallu pour appliquer l' .$s$

$P$$s$ $|P|$ $s$$i < |P|$$i < s$

Notez que cette méthode de recherche n'est garantie que si vous en avez une; il n'est pas garanti de trouver la réponse la plus courte ou la plus rapide. La raison de cela devrait être évidente si vous considérez que le processus se termine dès qu'il trouve un programme qui donne la bonne réponse.