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

13

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 ).

quant
fonte

Respostas:

15

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.xx

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).iiii

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.Psi=max{|P|,s}sP

Pål GD
fonte
3

iiPi=100101 Pi=120120Pi=120P|P|=100s=120) Então .i=max{|P|,s}Ps

Ps |P| si<|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.

Tom Potts
fonte