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?

28

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?

templatetypedef
fonte
@EvilJS Meu entendimento era que a prova de indecidibilidade envolvia a capacidade de simular TMs, embora talvez eu esteja enganado?
templatetypedef
Você pode dizer que o teorema de Rice pode não se encaixar em nenhuma dessas categorias, mas a prova do teorema se encaixa.
Ryan
11
@EvilJS Esse é um bom ponto. Realmente, o que estou procurando aqui é se existe alguma técnica fundamentalmente diferente que possamos usar. Seria bom, por exemplo, se alguém identificasse um problema como indecidível em um caso em que esse problema não tem relação conhecida com a auto-referência da MT ou um argumento do tipo Godeling. Se o melhor que podemos fazer é "descobrimos isso há muito tempo, percebemos que é mais fácil provar isso de outra maneira", que em certo sentido seria uma resposta - as três técnicas acima explicam fundamentalmente todas as provas de indecidibilidade que conhecemos.
templatetypedef
2
A função de ocupado Beaver cresce muito rápido para qualquer programa computar. Concretamente, você pode definir uma função como uma mais o maior número calculado por um programa de comprimento no máximo . Isso conta como diagonalização? f(n)n
Yuval Filmus
11
@YuvalFilmus Talvez eu esteja sendo muito rigoroso aqui, mas isso soa como um argumento do tipo diagonal para mim: você está construindo uma função definida para ser diferente de todas as funções calculadas pelas TMs.
templatetypedef

Respostas:

10

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.

Kaveh
fonte
Se alguém estiver interessado em técnicas avançadas em teoria da computabilidade, consulte os livros de Robert I. Soare Conjuntos e graus recursivamente enumeráveis e Teoria e aplicações da computabilidade .
precisa saber é o seguinte
Corrija-me se eu estiver errado, mas a prova do teorema da base baixa envolve aplicar um funcional a si mesmo e perguntar se ele não produz um valor? Em caso afirmativo, isso não é apenas uma camada de indireção sobre um argumento diagonal?
templatetypedef
@templatetypedef, eu não sou um especialista, mas tanto quanto eu entendo não. Veja, por exemplo, a página 109 do livro de Soare.
Kaveh
@templatetypedef, ps1: há alguma imprecisão na pergunta sobre o que consideramos diagonalização. Se não tomarmos cuidado, podemos expandir o que consideramos diagonalização toda vez que vemos algo que não era. Tome, por exemplo, métodos prioritários ou qualquer método geral de construção de objetos, parte por parte, de maneira a evitar ser igual a qualquer objeto de uma determinada classe.
Kaveh
2
@ David, :) Abro a página do livro que quero compartilhar, clico no botão de compartilhamento na parte superior e removo os parâmetros, exceto o ide pgdo link.
Kaveh
0

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:

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:

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" .

vzn
fonte
outro "surpreendente / aplicada" áreas de indecisão: tilings aperiódicos , eventual estabilização em Conway Game of Life ( autômatos celulares )
vzn
3
Entendo que as provas de que todos esses problemas são indecidíveis se resumem a reduções do problema da parada. Isso está incorreto?
templatetypedef
a resposta basicamente admite que (todos os resultados indecidíveis conhecidos podem ser reduzidos ao problema da parada). sua pergunta é quase formulada como uma conjectura, e não estou ciente de nenhum conhecimento conflitante, e vejo muitas evidências circunstanciais a seu favor. mas a mais próxima de uma prova formal conhecida são aparentemente as formulações de indecidibilidade de ponto fixo (não parece haver outras formulações formais de "auto-referencial".) essencialmente do mesmo fenômeno.
vzn