Certos problemas são conhecidos por serem indecidíveis, mas, no entanto, é possível progredir na solução deles. Por exemplo, o problema de parada é indecidível, mas é possível progredir na criação de ferramentas para detectar possíveis loops infinitos em seu código. Os problemas de lado a lado são...
Eu sei que o problema da parada é indecidível em geral, mas existem algumas máquinas de Turing que obviamente param e outras que obviamente não. De todas as máquinas de torção possíveis, qual é a menor em que ninguém tem uma prova, quer pare ou
Sabe-se que com um conjunto contável de algoritmos (caracterizado por um número de Gödel), não podemos computar (construir um algoritmo binário que verifique a pertença) todos os subconjuntos de N. Uma prova poderia ser resumida como: se pudéssemos, então o conjunto de todos os subconjuntos de N...
Fiquei me perguntando se existe uma boa bibliografia de tentativas de investigar a conjectura de Collatz como uma gramática formal. (ou quaisquer outras tentativas na comunidade de CS para lidar com essa classe de fenômenos generativos e suas propriedades de
Estou procurando obter uma resposta definitiva para a pergunta do título. Existe um conjunto de regras que traduz qualquer programa em uma configuração de peças finitas em um tabuleiro infinito, de modo que, se preto e branco executam apenas movimentos legais, o jogo termina em um tempo finito se...
Estou interessado no problema "mais próximo" (e "mais complexo") da conjectura de Collatz que foi resolvida com sucesso (que Erdos disse famosa "a matemática ainda não está propícia a tais problemas"). Está provado que uma classe de problemas "tipo Collatz" é indecidível. No entanto, problemas...
Existe uma máquina de Turing que pode decidir se quase todas as outras máquinas de Turing são interrompidas? Suponha que tenhamos alguma enumeração de máquinas de Turing e alguma noção de "tamanho" de um conjunto de números naturaise definimos:N→{Mi}N→{Mi}\mathbb{N} \rightarrow \{M_i\}∥⋅∥‖⋅‖\|...
A teoria do tipo construtivo, com sua interpretação básica sob a correspondência curry howard, consiste apenas de funções computáveis totais. Na literatura, alguns foram mencionados sobre o uso da "teoria dos tipos computacionais" para representar a não terminação em programas funcionais; no...
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
Tenho uma pergunta ingênua: existe uma máquina de Turing cujo término é verdadeiro, mas não pode ser provado por nenhuma teoria natural, consistente e finamente axiomatizável? Peço uma mera prova de existência e não um exemplo específico. Isso pode ter alguma conexão com a análise ordinal . De...