O que é uma explicação leiga para a pesquisa universal?

Estou lendo um livro sobre um tópico de ciência da computação, mas não tenho alguns dos pré-requisitos. Normalmente, quando me deparo com termos que não entendo, simplesmente os procuro, mas para a Pesquisa Universal simplesmente não consegui encontrar uma explicação adequada para um leitor sem formação em estatística / ciência da computação.

Estive lendo este artigo na Pesquisa Universal da Scholarpedia , que parece abordar o tópico. Gostaria de receber uma explicação para o que significa Universal Search (ou Levin Search ).

Pense nisso assim. Você tem um problema com a entrada sabe como verificar uma solução se alguma vez encontrou uma (como o inverso de uma matriz ou o que você gostaria de imaginar).$x$

Agora, pegue sua linguagem de programação favorita (por exemplo, Python) e crie todos os programas Python que consistem em no máximo 10 caracteres! Em seguida, você executa todos esses programas com sua entrada por 10 segundos cada, cada um na entrada . Se nenhum deles fornecer a resposta, você vai até 11. Execute cada programa com no máximo 11 caracteres (incluindo os que você já tentou, é claro) por 11 segundos cada, na entrada x . Se nenhum deles fornecer a resposta correta, você continua com 12 e assim por diante.$x$$x$

Mais formalmente, na iteração , você executa todos os programas de extensão no máximo i (finitamente muitos, mas é claro exponencial em i ), cada um por i segundos (ou etapas).$i$$i$$i$$i$

Existe um programa, digamos que fornece a saída correta em s segundos. Quando você chega à iteração i = max { | P | , s } , este programa será executado por pelo menos s segundos e você produzirá P e a solução.$P$$s$$i = \max\{|P|, s\}$$s$$P$

$i$$i$$P$$i=100$$101$ $P$$i=120$$\leq 120$$P$$i = 120$$P$$|P|=100$$s=120$) Então .$i=\mathrm{max}\{|P|,s\}$$P$$s$

$P$$s$ $|P|$ $s$$i < |P|$$i < s$ , em seguida, nós não deixar o programa funcionar por tempo suficiente.

Observe que esse método de pesquisa só garante uma resposta se houver uma; não é garantido encontrar a resposta mais curta ou mais rápida. O motivo disso deve ser aparente se você considerar que o processo termina assim que encontrar um programa que dê a resposta certa.