Esse problema de gráfico finito é decidível? Quais fatores tornam um problema decidível?

Quero saber se o seguinte problema é decidível e como descobrir. Todos os problemas que vejo podem dizer "sim" ou "não" a ele; portanto, a maioria dos problemas e algoritmos é decidível, exceto alguns (que são fornecidos aqui )?

Entrada: Um gráfico direcionado e finito , com v e u como vértices. Pergunta: Existe um caminho em G com u como vértice inicial e v como vértice final?$G$$v$$u$
$G$$u$$v$

Qualquer problema que exija apenas o exame de uma quantidade finita de dados é decidível, porque existe um algoritmo que consiste em enumerar todas as soluções possíveis. Pode ser ridiculamente lento, mas isso não é relevante: se houver um algoritmo, é decidível.

O problema que você declara assume um gráfico finito, o que sugere fortemente que é decidível. A rigor, você precisa procurar um pouco mais. O problema é uma propriedade nos caminhos no gráfico e, às vezes, há um número infinito de caminhos, quando o gráfico contém um ciclo (você pode percorrer esse ciclo quantas vezes quiser). No entanto, é fácil transformar o problema em um problema finito: se houver um caminho que comece com e termine com v que inclua um ciclo, você poderá cortar todos os ciclos nesse caminho e terá uma nova solução que não inclua um ciclo. Como existe um número finito de caminhos que não envolvem um ciclo (se o gráfico tiver k arestas, haverá no máximo k $u$$v$$k$$k!$caminhos que não usam a mesma aresta mais de uma vez), o problema de encontrar um caminho de a v é finitário, portanto é decidível.$u$$v$

Aliás, essa propriedade é chamada de conectividade .

Essa abordagem é comum, chamada redução . Dado um problema que não é direto, reduzimos para um problema que sabíamos resolver.

Muitas vezes é difícil provar que um problema é indecidível. Para provar que um problema é decidível, tudo o que precisamos fazer é exibir um algoritmo que o decida. Para provar que um problema é indecidível, precisamos provar que nenhum algoritmo pode existir. Existem alguns problemas indecidíveis bem conhecidos. Na prática, na maioria das vezes, quando provamos que um problema é indecidível, mostramos que há um problema indecidível conhecido que se reduz ao nosso problema. Como um algoritmo para o nosso problema resolveria o conhecido problema indecidível, nosso problema também deve ser indecidível.

Você realmente não pode dizer que “a maioria” dos problemas é decidível ou a “maioria” dos problemas é indecidível. Em algum sentido teórico, quase todos os problemas são indecidíveis, mas temos uma forte tendência para lidar com problemas "interessantes", e é mais provável que eles tenham uma solução.

O problema é trivialmente decidível, como apontado por Gilles em um comentário. Quanto à sua outra pergunta ...

a maioria dos problemas e algoritmos são decidíveis, exceto alguns (que são fornecidos aqui )?

Não. Na verdade, a maioria dos problemas é indecidível. De fato, existem incontáveis ​​problemas (idiomas), mas existem apenas muitas máquinas de Turing, o que significa que existem no máximo muitos problemas decidíveis.

Sim, isso é decidível, porque você pode fazer uma pesquisa exaustiva de todos os caminhos possíveis. Não há necessidade de procurar nenhum caminho que repita um vértice, pois o "desvio" pode ser ignorado. Mas o comprimento de qualquer caminho não repetitivo é limitado pelo tamanho do gráfico, que é finito, e portanto existem apenas muitos desses caminhos, que podem ser verificados um por um.

$G$$a$$b$$a$$b$

Não existe um método que indique se um problema específico é decidível ou não. Com o tempo, você pode ter um bom "palpite", independentemente de um problema específico ser decidido ou não.

O que eu costumo fazer é o seguinte:

1. tente resolver o problema. Ou seja, tente pensar em um programa de computador que resolva o problema em questão. Para o seu problema sugerido - um programa muito simples verificará qualquer caminho possível e, portanto, sempre será bem-sucedido em encontrá-lo (se houver) ou informar que não existe outro caminho.
2. formular o problema claramente. Muitos problemas são vagos demais, mas, quando escritos com clareza, é muito fácil ver se eles são decidíveis ou não (comparando-se com outros problemas, conhecidos por serem incontroláveis ​​ou por métodos conhecidos, como o teorema de Rice )
3. Se (2) não funcionou, mas você ainda acredita que o problema é indecidível, tente prová-lo através da redução de um problema indecidível (o problema de parada (ou seu complemento) funciona em muitos casos).

Quase sempre, ao tentar executar a etapa (1) para um problema indecidível, você precisará do seu programa para verificar um número infinito de coisas. Isso geralmente é um sinal de que o problema não é decidível.