Existe um resultado na teoria da computabilidade que não seja relativizada?

Eu estava lendo o artigo de Andrej Bauer Primeiros Passos na Teoria da Computabilidade Sintética . Na conclusão, ele observa que

Nossa axiomatização tem seu limite: não pode provar nenhum resultado na teoria da computabilidade que falhe em relativizar os cálculos da Oracle. Isso ocorre porque a teoria pode ser interpretada em uma variante dos tópicos efetivos construídos a partir de funções recursivas parciais com acesso a um oráculo.

Isso me fez pensar sobre resultados não relativizados em computabilidade. Todos os resultados que conheço da teoria da computabilidade são relativizados para computação com oráculos.

Existem resultados na teoria da computabilidade que não se relativizam? Ou seja, resultados que valem para computabilidade, mas não valem para computabilidade em relação a algum oráculo?

Por resultado, refiro-me a um teorema conhecido na teoria da computabilidade, não a uma afirmação elaborada. Se a noção de relativização não faz sentido para o resultado, não é o que estou procurando.

Também é interessante saber se o resultado pode ser declarado na linguagem da Teoria da Computabilidade Sintética ou não.

computability relativization Anônimo
fonte

Todo mundo sabe sobre resultados não relativizadores na teoria da complexidade, como IP = PSPACE. Estou perguntando sobre os resultados da teoria da relatividade da computabilidade , e não sobre a teoria da complexidade .

Anônimo

@ Erfan: Seus comentários não são relevantes para a pergunta. Minha pergunta é sobre a teoria da computabilidade, você está falando sobre a teoria da complexidade. Estou procurando resultados não reletivantes, o teorema da hierarquia do tempo se relativiza. Se você tiver uma pergunta sobre o teorema da hierarquia de tempo e a relativização, poderá postar uma pergunta separada.

Anônimo

Coisas relevantes: a conjectura de homogeneidade formulada por H. Rogers foi refutada em Richard A. Shore; A conjectura da homogeneidade (1979): existe um grau de Turing

tal que

não é isomórfico para

(a estrutura dos graus de Turing com ordem parcial

). Veja uma pergunta semelhante sobre lo.logic

a

$\mathbf{a}$

D (\geq a)

$\mathcal{D}(\geq \mathbf{a})$

D

$\mathcal{D}$

\leq_{T}

$\leq_{T}$

Marzio De Biasi

Boa pergunta :-)

Andrej Bauer

@ Marzio: Interessante. " Então isso significa que há uma primeira frase fim na língua única contendo que é verdade sobre os graus de Turing, mas que é falso se relativizar a frase para o Turing graus para alguns (e, claro, , trabalhar nos graus de Turing é equivalente a dar a todas as máquinas de Turing acesso a como um oráculo. Portanto, a prova de que é verdadeira não pode ser relativizada como . $\varphi$ $\leq_T$ $\geq_Tx$ $x$ $\geq_Tx$ $x$ $\varphi$ $x$ "Mas

não é realmente um resultado em computabilidade teoria, ela é preparada para um meta-teorema.

φ

$\varphi$

Anônimo

Respostas:

Teorema de incorporação de Higman: Os grupos apresentados finamente gerados computacionalmente são precisamente os subgrupos finitamente gerados de grupos finitamente apresentados. Além disso, todo grupo apresentado de forma computacional (mesmo os gerados de forma contável) é um subgrupo de um grupo finitamente apresentado.

Observe que esta afirmação pode ser relativizada para: "Os grupos apresentados computação (com algum oráculo ) são precisamente os subgrupos gerados finitamente de grupos apresentados finitamente", mas não o fazem, pois pode-se provar que, para alguns incontestáveis, existem grupos apresentados de forma computacional que não são apresentados computacionalmente. $O$ $O$ $O$ $O$

Na verdade, acho que qualquer resultado não relativizando da teoria da computabilidade deve ter algo de seu sabor, como uma parte do resultado ou sua prova deve de alguma forma "nail down" verdadeira computability de computability com um oráculo . Nesse caso, é a finitude que define a "computabilidade real". Observe que, como Scott Aaronson solicitou, esse resultado é invariável a qualquer dos modelos usuais de computação (máquina de Turing, RAM etc.), mas não é relativizado (novamente, porque todos os modelos usuais de computação "real" compartilham alguns "propriedade finitude" comum). $O$

Por outro lado, alguém poderia argumentar que isso "não conta" para esta questão, pois é mais semelhante a uma definição de computabilidade usando grupos do que é um "resultado da teoria da computabilidade". Por outro lado, é uma definição de computabilidade que é robusta para modelar e que não é relativizada . (Em contraste com, digamos, a caracterização de Kleene das funções computáveis que se relativizam facilmente, simplesmente adicionando a função característica de seu oráculo ao conjunto de funções gerador. Parece não haver operação análoga para grupos no contexto da Higman Embedding.)

Joshua Grochow
fonte

É finitude (vs. infinito) que distingue o seu exemplo, ou responsabilidade (vs. incontabilidade)?

András Salamon 27/03

Desculpe minha ignorância, mas o teorema de Higman é uniforme? Ou seja, dado um grupo apresentado de forma computacional, podemos calcular uniformemente um grupo finitamente gerado que o contém?

27417 Andrej Bauer

Opa, substitua "finitamente gerado" por "finitamente apresentado" na minha pergunta. Esse foi um erro trivial. O que estou pensando é se podemos substituir "finitamente apresentado" por algo um pouco mais geral.

Andrej Bauer

S A T^{O}

$SAT^O$

N P^{O}

$NP^O$

@AndrewMorgan: Concordado. Eu pensaria que o gênero nó seria um bom candidato :).

Joshua Grochow 28/03

Isso é algo que eu sempre quis saber também!

Se, por "resultados na teoria da computabilidade", você quer dizer resultados invariáveis em relação à escolha do modelo de máquina (máquinas de Turing, máquinas de RAM etc.), então não conheço um único exemplo desse resultado e eu definitivamente teria lembrado se eu tivesse visto um.

O mais próximo que posso sugerir de uma resposta é: acho que existem muitas questões interessantes na teoria da computabilidade que podem depender do modelo da máquina. Por exemplo: a função Busy Beaver, com sua definição usual em termos de máquinas de Turing, é infinitamente estranha? O valor do BB (20) é independente do ZFC? Quaisquer que sejam as respostas a essas perguntas, elas certamente podem ser diferentes para os análogos relativizados da função BB.

Scott Aaronson
fonte

Aqui está um exemplo mais ou menos trivial: considere o problema de parada para máquinas de Turing que são especificamente proibidas (pela definição do modelo de computação) de acessar um oráculo. É indecidível em relação a nenhum oráculo e a um oráculo trivial, e ainda assim é decidível em relação a um oráculo para o problema de parada. (O problema em si não muda em relação a um oráculo porque não pode acessá-lo, mas a TM (irrestrita) que decide o problema se torna mais poderosa, dado o oráculo.)

Existem muitos outros exemplos também. Apenas brinque um pouco com o modelo de computação e você poderá encontrar outros resultados semelhantes.

Philip White
fonte

Apenas curioso: o que exatamente está errado com esta resposta? Talvez os que recusam não acreditam que seja possível proibir uma máquina de Turing de acessar um oráculo e exigir mais explicações sobre isso?

Philip White

Não parece uma definição muito justa de relativização para permitir que a máquina tenha um oráculo, mas depois não o utilize.

David Eppstein

Interessante, embora não o que estou procurando. Estou procurando um resultado conhecido na teoria da computabilidade que não seja relativizado, não um argumento sobre como elaborar esse resultado.

Anônimo

Considere a seguinte declaração: H (problema de parada para máquinas de Turing sem oráculos) não é computável. Por outro lado, H é computável em relação a um problema de parada do oráculo. Mesmo se considerarmos isso como uma maneira de relativizar a afirmação, ela não é interessante. Provavelmente, existe uma maneira semelhante de relativizar qualquer afirmação que a torne falsa. Uma relativização não é apenas anexar um oráculo em algum lugar. Uma relativização é interessante quando preserva alguma classe interessante de argumentos; portanto, se uma afirmação não relativizar, sabemos que a classe de argumentos não pode provar a afirmação.

Kaveh

Tome, por exemplo, o método de relativização no BGS. É interessante porque preserva argumentos simples de diagonalização para que eles não possam resolver P vs. NP. Se uma relativização não preservar esses argumentos, provavelmente não é uma maneira interessante de relativizar declarações. Uma boa relativização deve perseverar o máximo possível de argumentos conhecidos e resultados comprovados, quanto menos preservar, menos interessante se tornará.

Kaveh