Existem casos de problemas que sabemos ser insolúveis?

Como diz o título:

Existem casos de problemas que sabemos ser insolúveis?

Ou equivalente

Existem problemas promissores com um número finito de entradas possíveis que são indecidíveis?

Observe: percebo que muitos problemas computacionais são conhecidos por serem insolúveis, mas, pelo que sei (pode ser limitado), todos precisam receber um número infinito de entradas. Portanto, sua existência não implica que não possa haver um número infinito de algoritmos, cada um resolvendo um subconjunto desses problemas.

Observação: desejo apenas considerar problemas bem definidos, ou seja, toda entrada tem uma saída correta.

Em uma nota relacionada, existe uma hierarquia de complexidade para problemas promissores com apenas um número finito de entradas possíveis?

undecidability guest_56763556765
fonte

Respostas:

Todo problema com um número finito de entradas é computável.

Prova: suponha que as entradas sejam e que as saídas desejadas sejam . Em seguida, o programa a seguir resolve o problema: $i_1,\ldots,i_n$ $o_1,\ldots,o_n$

Se a entrada for , . $i_1$ $o_1$
Se a entrada for , . $i_2$ $o_2$
...
Se a entrada for , faça a saída . $i_{n-1}$ $o_{n-1}$
Saída . $o_n$

Yuval Filmus
fonte

Como um aparte, a abordagem análoga para "demonstrar" a computabilidade com um número infinito de entradas não funciona: exigiria um programa com um número infinito de etapas, que não atenda à definição de um algoritmo. (Isto pode ser muito óbvio para a maioria dos leitores, mas eu senti como apontando-o para fora de qualquer maneira.)

Jeroen Mostert