Existem problemas específicos que se sabe serem indecidíveis por outras razões que não a diagonalização, auto-referência ou redutibilidade?

Todo problema indecidível que eu conheço se enquadra em uma das seguintes categorias:

1. Problemas indecidíveis por causa da diagonalização (auto-referência indireta). Esses problemas, como o problema da parada, são indecidíveis, porque você pode usar um pretenso argumento para a linguagem construir uma TM cujo comportamento leva a uma contradição. Você também pode agrupar muitos problemas indecidíveis sobre a complexidade de Kolmogorov neste campo.

2. Problemas indecidíveis devido à auto-referência direta. Por exemplo, pode-se mostrar que a linguagem universal é indecidível pelo seguinte motivo: se fosse decidível, seria possível usar o teorema da recursão de Kleene para construir uma TM que obtém sua própria codificação, pergunte se aceita sua própria entrada. , então faz o oposto.

3. Problemas indecidíveis devido a reduções de problemas indecidíveis existentes. Bons exemplos aqui incluem o Problema Pós-Correspondência (redução do problema de parada) e o problema de Entscheidung.

Quando ensino teoria da computabilidade para meus alunos, muitos estudam também e frequentemente me perguntam se existem problemas que podemos provar serem indecidíveis sem, no final das contas, traçar algum tipo de truque de auto-referência. Posso provar de maneira não construtiva que existem infinitamente muitos problemas indecidíveis por um simples argumento de cardinalidade que relaciona o número de TMs ao número de idiomas, mas isso não fornece um exemplo específico de um idioma indecidível.

Existem idiomas conhecidos por serem indecidíveis por motivos que não estão listados acima? Em caso afirmativo, quais são eles e quais técnicas foram usadas para mostrar sua indecidibilidade?

Sim, existem tais provas. Eles são baseados no Teorema da Base Baixa .

Consulte esta resposta para: Existem provas da indecidibilidade do problema de parada que não depende de auto-referência ou diagonalização? pergunta sobre a história para mais.

essa não é exatamente uma resposta afirmativa, mas uma tentativa de algo próximo ao que é solicitado por um ângulo criativo. agora existem muitos problemas na física que estão "muito distantes" das formulações matemáticas / teóricas da indecidibilidade e parecem cada vez mais "remotas" e "têm pouca semelhança" com as formulações originais que envolvem o problema da parada, etc .; é claro que eles usam o problema da parada na raiz, mas as cadeias de raciocínio se tornaram cada vez mais distantes e também têm um forte aspecto / natureza "aplicado". infelizmente, ainda não parece haver grandes pesquisas nessa área. um problema recente que foi "surpreendentemente" provado indecidível na física que atraiu muita atenção:

• Indecidibilidade do gap espectral / Cubitt, Perez-Garcia, Wolf

A lacuna espectral - a diferença de energia entre o estado fundamental e o primeiro estado excitado de um sistema - é central para a física quântica de muitos corpos. Muitos problemas abertos desafiadores, como a conjectura de Haldane, a questão da existência de fases líquidas de spin topológico com lacunas e a conjectura de gap de Yang-Mills, dizem respeito a lacunas espectrais. Esses e outros problemas são casos particulares do problema geral do hiato espectral: dado o hamiltoniano de um sistema quântico de muitos corpos, ele está húmido ou sem faixa? Aqui provamos que este é um problema indecidível. Especificamente, construímos famílias de sistemas de spin quântico em uma rede bidimensional com interações translacionalmente invariantes e vizinhos mais próximos, para as quais o problema de gap espectral é indecidível. Esse resultado se estende à indecidibilidade de outras propriedades de baixa energia,

o que você parece estar observando na pergunta é que todas as provas de indecidibilidade (informalmente) têm uma certa estrutura "auto-referencial", e isso foi formalmente comprovado em matemática ainda mais avançada, de modo que tanto o problema de parada de Turing quanto o teorema de Godels podem ser visto como instâncias do mesmo fenômeno subjacente. veja por exemplo:

• Problema de parada, conjuntos incontestáveis: prova matemática comum?

O teorema da parada, o teorema de Cantor (o não isomorfismo de um conjunto e seu conjunto de potências) e o teorema da incompletude de Goedel são todas instâncias do teorema de ponto fixo de Lawvere, que diz que para qualquer categoria fechada cartesiana, se houver um mapa epimórfico e: A → (A⇒B), então todo f: B → B tem um ponto fixo.

há também uma longa meditação sobre esse tema da interconexão (intrínseca?) da autorreferencialidade e da indecidibilidade nos livros de Hofstadter. outra área em que os resultados de indecidibilidade são comuns e foram inicialmente um tanto "surpreendentes" está nos fenômenos fractais. a aparência transversal / significância de fenômenos indecidíveis através da natureza é quase um princípio físico reconhecido neste ponto, observado pela primeira vez por Wolfram como "princípio de equivalência computacional" .