Existe um vínculo oculto entre a existência de conjuntos incontáveis ​​e a indecidibilidade do problema de parada?

9

Como ambas as provas fazem uso do argumento diagonal, estou me perguntando se existe um elo obscuro entre a existência de conjuntos infinitos incontáveis ​​e a indecidibilidade do problema de parada. O problema da parada seria decidível se todos os conjuntos fossem contáveis?

halting-problem Lenar Hoyt
fonte
10
Sim, o argumento diagonal!
Mahdi Cheraghchi
11
@MCH Meu pensamento era que talvez haja uma caracterização diferente além do argumento diagonal que conecta os dois. Essa pergunta talvez seja muito embaçada para o SE.
Lenar Hoyt 7/08/2013
4
Este pode ser um link parcial: claramente, o conjunto de todos os idiomas em um determinado alfabeto é incontável. No entanto, o conjunto de todas as máquinas de Turing é contável. Isso implica diretamente a existência de problemas indecidíveis. No entanto, esse raciocínio não implica nada sobre o problema da parada.
044 de
9
Certamente existem modelos teóricos de conjuntos de ZFC em que todos os conjuntos são contáveis ​​(embora não estejam dentro do modelo), mas o problema de parada é sempre indecidível. Veja esta pergunta do MathOverflow .
Peter Shor
4
Por favor, diga indecidibilidade a partir de agora.
precisa

Respostas:

14

Não é um link oculto, mas que foi explicitado usando a linguagem da teoria das categorias e também uma pergunta muito natural a ser feita e estudada. Há um pouco de material sobre o assunto.

Vijay D
fonte