Existe um algoritmo que provavelmente existe, embora não saibamos o que é?

21

Em matemática, existem muitas provas de existência que não são construtivas; portanto, sabemos que um determinado objeto existe, embora não saibamos como encontrá-lo.

Estou à procura de resultados semelhantes em ciência da computação. Em particular: existe um problema que podemos provar que é decidível sem mostrar um algoritmo para isso? Ou seja, sabemos que ele pode ser resolvido por um algoritmo, mas não sabemos como é o algoritmo?

Erel Segal-Halevi
fonte
5
Há uma resposta trivial. Faça qualquer pergunta sim / não cuja resposta seja desconhecida, como "é aleatório", então a pergunta é decidível, mas ainda não sabemos qual dos dois algoritmos possíveis está correto. π
Hendrik Jan
6
basicamente duplicar de tcs.se questão existem não-construtiva provas algoritmo de existência
vzn
1
@babou De fato: uma pergunta com uma resposta única é decidível. Aqui a ignorância é o ponto que parece, é um caso de "não sei" da questão, embora apenas "não saiba agora ". Depois de descobrirmos se é aleatório ou não, precisamos procurar outro exemplo. Sua resposta abaixo é muito melhor, é claro! É uma forma de "não sei" que é inerentemente "nunca saberá". π
Hendrik Jan
1
@ HendrikJan: E esse procedimento é o que chamamos de algoritmo no CS. Mas tomando o problema da parada como exemplo, não podemos nem provar que existe um algoritmo!
MSalters
1
Alguns exemplos mais interessantes podem ser encontrados aqui: cstheory.stackexchange.com/questions/4777/…
Segal-Halevi

Respostas:

14

O caso mais simples que conheço de um algoritmo que existe, embora não seja conhecido qual algoritmo, diz respeito a autômatos de estados finitos.

O quociente de uma língua L 1 por uma língua L 2 é definido como G 1 / G 2 = { x | y L 2  de tal modo que  x y L 1 } .L1/L2L1L2L1/L2={xyL2 such that xyL1}

É fácil provar que um conjunto regular é fechado sob quociente por um conjunto arbitrário. Em outras palavras, se for regular e for arbitrário (não necessariamente regular), então será regular.L 2 L 1 / L 2L1L2L1/L2

A prova é bastante simples. Seja um FSA que aceita o conjunto regular , onde Q e F são, respectivamente, o conjunto de estados e o conjunto de estados que aceitam, e seja L uma linguagem arbitrária. Seja F = { q Q y LRM=(Q,Σ,δ,q0,F)RQFL ser o conjunto de estados a partir do qual um estado final pode ser alcançado por aceitar uma cadeia de caracteres a partir de L .F={qQyLδ(q,y)F}L

O autómato , a qual difere de H apenas na sua conjunto F ' de estados finais reconhece precisamente R / L . (Ou veja Hopcroft-Ullman 1979, página 62 para uma prova desse fato.)M=(Q,Σ,δ,q0,F)MFR/L

No entanto, quando o conjunto não é decidível, pode não haver algoritmo para decidir quais estados têm a propriedade que define F ' . Portanto, enquanto sabemos que o conjunto F ' é um subconjunto de Q , não temos algoritmo para determinar qual subconjunto. Conseqüentemente, enquanto sabemos que R é aceito por um dos 2 | Q | possível FSA, não sabemos qual é. Embora eu deva confessar, sabemos em grande parte como ela é.LFFQR2|Q|

Este é um exemplo do que às vezes é chamado de prova quase construtiva , ou seja, uma prova de que uma de um número finito de respostas é a correta.

Suponho que uma extensão disso possa ser uma prova de que uma de um conjunto enumerável de respostas é a correta. Mas eu não conheço nenhum. Também não conheço uma prova puramente não-construtiva de que algum problema seja resolvido, por exemplo, usando apenas contradição.

babou
fonte
1
@ DW eu disse que é regular, mas L é arbitrário . Não precisa ser recursivamente enumerável ou regular. Nenhuma propriedade de L é usada além do fato de ser um conjunto de cadeias. Se você não confia em mim, verifique Hopcroft-Ullman 1979, página 62.RLL
babou
Obrigado. Esta é a minha resposta favorita porque a linguagem decidível é infinita.
Erel Segal-Halevi
@abou, meu erro, eu li mal o que você escreveu. Minha culpa - desculpe por isso. Eu editei sua postagem para fazer a parte que eu entendi errado, espero que seja mais clara.
DW
@DW Estou divertido por você ter um problema, mas isso acontece comigo também. Mas talvez eu devesse ter sido mais claro. Isso não foi intencional. Dizendo isso porque alguns matemáticos pensam que é mais elegante ser enigmático. Obrigado pela edição.
babou 27/10/14
12

Para expandir o comentário original de Hendrick, considere este problema

n0nπ

Esse problema é decidível, pois um dos dois casos pode obter:

  1. NπN
  2. nπn

No caso (1), um algoritmo de decisão para o problema seria um dos

n>N

e no caso (2) o algoritmo seria

Responda "sim".

Claramente, cada um deles é um algoritmo de decisão; nós simplesmente não sabemos qual. Isso basta, porém, uma vez que a decidibilidade requer apenas a existência de um algoritmo, não a especificação de qual algoritmo usar.

Rick Decker
fonte
+1 Este é um exemplo direto que eu lembro do meu professor de Computabilidade e Lógica usando. É o meu exemplo, uma vez que não requer muito conhecimento de domínio, por isso é fácil de transmitir.
Joshua Taylor
1
Para formulações alternativas, veja também aqui .
Raphael
2

Aqui está uma não resposta. Estou postando porque acredito que é instrutivo, porque originalmente afirmei o contrário e oito pessoas concordaram o suficiente para votar antes do @sdcwc apontar o erro. Eu não queria apenas editar minha primeira resposta, porque não tenho certeza de que muitas pessoas a votariam se soubessem que estava errada.

SS

HH

David Richerby
fonte