Teorema de Post - Post's theorem

Na teoria da computabilidade, o teorema de Post , em homenagem a Emil Post , descreve a conexão entre a hierarquia aritmética e os graus de Turing .

Fundo

A declaração do teorema de Post usa vários conceitos relacionados à definibilidade e teoria da recursão . Esta seção fornece uma breve visão geral desses conceitos, que são abordados em detalhes em seus respectivos artigos.

A hierarquia aritmética classifica certos conjuntos de números naturais que são definíveis na linguagem da aritmética de Peano. Uma fórmula é dito para ser se for uma instrução existencial em forma normal prenex (todos os quantificadores à frente) com alternâncias entre quantificadores existenciais e universais aplicadas a uma fórmula com quantificadores limitadas apenas. Formalmente, uma fórmula na linguagem da aritmética de Peano é uma fórmula se tiver a forma ${\ displaystyle \ Sigma _ {m} ^ {0}}$${\ displaystyle m}$${\ displaystyle \ phi (s)}$${\ displaystyle \ Sigma _ {m} ^ {0}}$

${\ displaystyle \ left (\ existe n_ {1} ^ {1} \ existe n_ {2} ^ {1} \ cdots \ existe n_ {j_ {1}} ^ {1} \ right) \ left (\ forall n_ {1} ^ {2} \ cdots \ forall n_ {j_ {2}} ^ {2} \ direita) \ esquerda (\ existe n_ {1} ^ {3} \ cdots \ direita) \ cdots \ esquerda (Qn_ { 1} ^ {m} \ cdots \ right) \ rho (n_ {1} ^ {1}, \ ldots n_ {j_ {m}} ^ {m}, x_ {1}, \ ldots, x_ {k}) }$

onde contém apenas quantificadores limitados e Q é se m for par e se m for ímpar. ${\ displaystyle \ rho}$${\ displaystyle \ forall}$${\ displaystyle \ existe}$

Diz- se que um conjunto de números naturais é se for definível por uma fórmula, ou seja, se houver uma fórmula tal que cada número esteja dentro se e somente se for válido. Sabe-se que, se um conjunto é , em seguida, é para qualquer , mas para cada m tem um conjunto que não é . Assim, o número de alternâncias de quantificador necessárias para definir um conjunto dá uma medida da complexidade do conjunto. ${\ displaystyle A}$${\ displaystyle \ Sigma _ {m} ^ {0}}$${\ displaystyle \ Sigma _ {m} ^ {0}}$${\ displaystyle \ Sigma _ {m} ^ {0}}$${\ displaystyle \ phi (s)}$${\ displaystyle n}$${\ displaystyle A}$${\ displaystyle \ phi (n)}$${\ displaystyle \ Sigma _ {m} ^ {0}}$${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ displaystyle n> m}$${\ displaystyle \ Sigma _ {m + 1} ^ {0}}$${\ displaystyle \ Sigma _ {m} ^ {0}}$

O teorema de Post usa a hierarquia aritmética relativizada, bem como a hierarquia não relativizada que acabou de ser definida. Diz-se que um conjunto de números naturais é relativo a um conjunto , escrito , se for definível por uma fórmula em uma linguagem estendida que inclui um predicado para pertencer a . ${\ displaystyle A}$${\ displaystyle \ Sigma _ {m} ^ {0}}$${\ displaystyle B}$${\ displaystyle \ Sigma _ {m} ^ {0, B}}$${\ displaystyle A}$${\ displaystyle \ Sigma _ {m} ^ {0}}$${\ displaystyle B}$

Enquanto a hierarquia aritmética mede a definibilidade de conjuntos de números naturais, os graus de Turing medem o nível de incomputabilidade de conjuntos de números naturais. Um conjunto é dito para ser Turing redutível a um conjunto , escrita , se existe uma máquina de Turing a Oracle que, dado um Oracle para , calcula a função característica de . O salto de Turing de um conjunto é uma forma do problema Halting relativo a . Dado um conjunto , o salto de Turing é o conjunto de índices das máquinas de Turing do oráculo que param na entrada quando executadas com o oráculo . É sabido que cada conjunto é Turing redutível ao seu salto de Turing, mas o salto de Turing de um conjunto nunca é Turing redutível ao conjunto original. ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A \ leq _ {T} B}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle A '}$${\ displaystyle 0}$${\ displaystyle A}$${\ displaystyle A}$

O teorema de Post usa saltos de Turing com iteração finita. Para qualquer conjunto de números naturais, a notação indica o salto de Turing iterado –fold iterado de . Assim é justo , e é o salto de Turing de . ${\ displaystyle A}$${\ displaystyle A ^ {(n)}}$${\ displaystyle n}$${\ displaystyle A}$${\ displaystyle A ^ {(0)}}$${\ displaystyle A}$${\ displaystyle A ^ {(n + 1)}}$${\ displaystyle A ^ {(n)}}$

Teorema de Post e corolários

O teorema de Post estabelece uma conexão estreita entre a hierarquia aritmética e os graus de Turing da forma , ou seja, saltos de Turing finitamente iterados do conjunto vazio. (O conjunto vazio pode ser substituído por qualquer outro conjunto computável sem alterar a verdade do teorema.) ${\ displaystyle \ emptyset ^ {(n)}}$

O teorema de Post afirma:

1. Um conjunto é se e somente se for recursivamente enumerável por uma máquina de Turing oráculo com um oráculo para , isto é, se e somente se for .${\ displaystyle B}$${\ displaystyle \ Sigma _ {n + 1} ^ {0}}$${\ displaystyle B}$${\ displaystyle \ emptyset ^ {(n)}}$${\ displaystyle B}$${\ displaystyle \ Sigma _ {1} ^ {0, \ emptyset ^ {(n)}}}$
2. O conjunto está completo para todos . Isso significa que cada conjunto pode ser reduzido a muitos-um .${\ displaystyle \ emptyset ^ {(n)}}$${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ displaystyle n> 0}$${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ displaystyle \ emptyset ^ {(n)}}$

O teorema de Post tem muitos corolários que expõem relações adicionais entre a hierarquia aritmética e os graus de Turing. Esses incluem:

1. Conserte um conjunto . Um conjunto é se e somente se for . Esta é a relativização da primeira parte do teorema de Post ao oráculo .${\ displaystyle C}$${\ displaystyle B}$${\ displaystyle \ Sigma _ {n + 1} ^ {0, C}}$${\ displaystyle B}$${\ displaystyle \ Sigma _ {1} ^ {0, C ^ {(n)}}}$${\ displaystyle C}$
2. Um conjunto é se e somente se . Mais geralmente, é se e somente se .${\ displaystyle B}$${\ displaystyle \ Delta _ {n + 1}}$${\ displaystyle B \ leq _ {T} \ emptyset ^ {(n)}}$${\ displaystyle B}$${\ displaystyle \ Delta _ {n + 1} ^ {C}}$${\ displaystyle B \ leq _ {T} C ^ {(n)}}$
3. Um conjunto é definido como aritmético se for para alguns . O teorema de Post mostra que, equivalentemente, um conjunto é aritmético se e somente se for Turing redutível para algum m .${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ displaystyle n}$${\ displaystyle \ emptyset ^ {(m)}}$

Prova do teorema de Post

Formalização de máquinas de Turing em aritmética de primeira ordem

A operação de uma máquina de Turing na entrada pode ser formalizada logicamente na aritmética de primeira ordem . Por exemplo, podemos usar os símbolos , e para a configuração da fita, o estado da máquina e a localização ao longo da fita após as etapas, respectivamente. o sistema de transição de determina a relação entre e ; seus valores iniciais (para ) são a entrada, o estado inicial e zero, respectivamente. A máquina para se e somente se houver um número tal que seja o estado de parada. ${\ displaystyle T}$${\ displaystyle n}$ ${\ displaystyle A_ {k}}$${\ displaystyle B_ {k}}$${\ displaystyle C_ {k}}$${\ displaystyle k}$${\ displaystyle T}$${\ displaystyle (A_ {k}, B_ {k}, C_ {k})}$${\ displaystyle (A_ {k + 1}, B_ {k + 1}, C_ {k + 1})}$${\ displaystyle k = 0}$${\ displaystyle k}$${\ displaystyle B_ {k}}$

A relação exata depende da implementação específica da noção de máquina de Turing (por exemplo, seu alfabeto, modo permitido de movimento ao longo da fita, etc.)

No caso de parar no tempo , a relação entre e deve ser satisfeita apenas para k limitado de cima por . ${\ displaystyle T}$${\ displaystyle n_ {1}}$${\ displaystyle (A_ {k}, B_ {k}, C_ {k})}$${\ displaystyle (A_ {k + 1}, B_ {k + 1}, C_ {k + 1})}$${\ displaystyle n_ {1}}$

Assim, existe uma fórmula em aritmética de primeira ordem com há un delimitada quantificadores , de tal modo que pára sobre a entrada em tempo de , no máximo, se e apenas se for satisfeita. ${\ displaystyle \ varphi (n, n_ {1})}$${\ displaystyle T}$${\ displaystyle n}$${\ displaystyle n_ {1}}$${\ displaystyle \ varphi (n, n_ {1})}$

Exemplo de implementação

Por exemplo, para uma máquina de Turing sem prefixo com alfabeto binário e nenhum símbolo em branco, podemos usar as seguintes notações:

• ${\ displaystyle A_ {k}}$é o símbolo 1- ário para a configuração de toda a fita após as etapas (que podemos escrever como um número com LSB primeiro, o valor da m-ésima localização na fita sendo seu m-ésimo bit menos significativo). Em particular, é a configuração inicial da fita, que corresponde à entrada para a máquina.${\ displaystyle k}$${\ displaystyle A_ {0}}$
• ${\ displaystyle B_ {k}}$é o símbolo 1- ário para o estado da máquina de Turing após as etapas. Em particular, o estado inicial da máquina de Turing.${\ displaystyle k}$${\ displaystyle B_ {0} = q_ {I}}$
• ${\ displaystyle C_ {k}}$é o símbolo 1- ário para a localização da máquina de Turing na fita após as etapas. Em particular .${\ displaystyle k}$${\ displaystyle C_ {0} = 0}$
• ${\ displaystyle M (q, b)}$ é a função de transição da máquina de Turing, escrita como uma função de um dupleto (estado da máquina, bit lido pela máquina) para um tripleto (novo estado da máquina, bit escrito pela máquina, +1 ou -1 movimento da máquina ao longo da fita )
• ${\ bit displaystyle (j, m)}$é o j-ésimo bit de um número . Isso pode ser escrito como uma fórmula aritmética de primeira ordem sem quantificadores ilimitados.${\ displaystyle m}$

Para uma máquina de Turing sem prefixo, podemos usar, para a entrada n, a configuração de fita inicial em que cat significa concatenação; portanto, é uma string de comprimento de seguida por e depois por . ${\ displaystyle t (n) = cat (2 ^ {ceil (log_ {2} n)} - 1,0, n)}$${\ displaystyle t (n)}$${\ displaystyle \ log (n) -}$${\ displaystyle 1-s}$${\ displaystyle 0}$${\ displaystyle n}$

A operação da máquina de Turing nas primeiras etapas pode, portanto, ser escrita como a conjunção das condições iniciais e as seguintes fórmulas, quantificadas para todos : ${\ displaystyle n_ {1}}$${\ displaystyle k}$${\ displaystyle k <n_ {1}}$

• ${\ displaystyle (B_ {k + 1}, bit (C_ {k}, A_ {k + 1}), D) = M (B_ {k}, bit (C_ {k}, A_ {k}))}$. Como M tem um domínio finito, ele pode ser substituído por uma fórmula aritmética livre de quantificador de primeira ordem . A fórmula exata obviamente depende de M.
• ${\ displaystyle C_ {k + 1} = C_ {k} + D}$
• ${\ displaystyle \ forall j: j \ neq C_ {k} \ rightarrow bit (j, A_ {k + 1}) = bit (j, A_ {k})}$. Observe que, nas primeiras etapas, nunca chega a um local ao longo da fita maior que . Assim, o quantificador universal sobre j pode ser limitado por +1, pois os bits além dessa localização não têm relevância para a operação da máquina.${\ displaystyle n_ {1}}$${\ displaystyle T}$${\ displaystyle n_ {1}}$${\ displaystyle n_ {1}}$

T para na entrada no momento, no máximo, se e somente se for satisfeito, onde: ${\ displaystyle n}$${\ displaystyle n_ {1}}$${\ displaystyle \ varphi (n, n_ {1})}$

${\ displaystyle {\ begin {alinhados} \ varphi (n, n_ {1}) = & (A_ {0} = t (n)) \ land (B_ {0} = q_ {I}) \ land (C_ { 0} = 0) \ land (B_ {n_ {1}} = q_ {H}) \\ & \ land \ forall k <n_ {1}: ((B_ {k + 1}, bit (C_ {k} , A_ {k + 1}), 1) = M (B_ {k}, bit (C_ {k}, A_ {k})) \ land C_ {k + 1} = C_ {k} +1) & \ \ & \ lor ((B_ {k + 1}, bit (C_ {k}, A_ {k + 1}), - 1) = M (B_ {k}, bit (C_ {k}, A_ {k} )) \ land C_ {k + 1} = C_ {k} -1)) & \\ & \ land \ forall j <n_ {1} +1: j \ neq C_ {k} \ rightarrow (bit (j, A_ {k + 1}) = bit (j, A_ {k})) & \ end {alinhado}}}$

Esta é uma fórmula aritmética de primeira ordem sem quantificadores ilimitados, ou seja, está em . ${\ displaystyle \ Sigma _ {0} ^ {0}}$

Conjuntos recursivamente enumeráveis

Let Ser um conjunto que pode ser recursivamente enumerado por uma máquina de Turing . Em seguida, existe uma máquina de Turing que para cada em , pára quando dado como entrada. ${\ displaystyle S}$${\ displaystyle T}$${\ displaystyle n}$${\ displaystyle S}$${\ displaystyle T}$${\ displaystyle n}$

Isso pode ser formalizado pela fórmula aritmética de primeira ordem apresentada acima. Os membros de são os números que satisfazem a seguinte fórmula: ${\ displaystyle S}$${\ displaystyle n}$

${\ displaystyle \ existe n_ {1}: \ varphi (n, n_ {1})}$

Esta fórmula está em . Portanto, está dentro . Assim, todo conjunto recursivamente enumerável está em . ${\ displaystyle \ Sigma _ {1} ^ {0}}$${\ displaystyle S}$${\ displaystyle \ Sigma _ {1} ^ {0}}$${\ displaystyle \ Sigma _ {1} ^ {0}}$

O inverso também é verdadeiro: para cada fórmula em com k existencial quantificadores, podemos enumerar os -tuples de números naturais e executar uma máquina de Turing que passa por todos eles até encontrar a fórmula é satisfeita. Essa máquina de Turing pára precisamente no conjunto de números naturais que os satisfazem e, assim, enumera seu conjunto correspondente. ${\ displaystyle \ varphi (n)}$${\ displaystyle \ Sigma _ {1} ^ {0}}$${\ displaystyle k}$${\ displaystyle \ varphi (n)}$

Maquinas oracle

Da mesma forma, a operação de uma máquina de oráculo com um oráculo O que para após no máximo etapas na entrada pode ser descrita por uma fórmula de primeira ordem , exceto que a fórmula agora inclui: ${\ displaystyle T}$${\ displaystyle n_ {1}}$${\ displaystyle n}$${\ displaystyle \ varphi _ {O} (n, n_ {1})}$${\ displaystyle \ varphi _ {1} (n, n_ {1})}$

• Um novo predicado,, dando a resposta do oráculo. Este predicado deve satisfazer alguma fórmula a ser discutida abaixo.${\ displaystyle O_ {m}}$
• Uma fita adicional - a fita do oráculo - na qual deve escrever o número m para cada chamada O (m) para o oráculo; a gravação nessa fita pode ser formalizada logicamente de maneira semelhante à gravação na fita da máquina. Observe que uma máquina oracle que pára após no máximo etapas tem tempo para escrever no máximo dígitos na fita oracle. Portanto, o oráculo só pode ser chamado com números que satisfaçam .${\ displaystyle T}$${\ displaystyle n_ {1}}$${\ displaystyle n_ {1}}$${\ displaystyle m <2 ^ {n_ {1}}}$

Se o oráculo é para um problema de decisão, é sempre "Sim" ou "Não", que podemos formalizar como 0 ou 1. Suponha que o próprio problema de decisão possa ser formalizado por uma fórmula aritmética de primeira ordem . Em seguida, para após a maioria das etapas se e somente se a seguinte fórmula for satisfeita: ${\ displaystyle O_ {m}}$${\ displaystyle \ psi ^ {O} (m)}$${\ displaystyle T}$${\ displaystyle n}$${\ displaystyle n_ {1}}$${\ displaystyle \ varphi _ {O} (n, n_ {1}) = \ forall m <2 ^ {n_ {1}}: ((\ psi ^ {O} (m) \ rightarrow (O_ {m} = 1)) \ land (\ lnot \ psi ^ {O} (m) \ rightarrow (O_ {m} = 0))) \ land {\ varphi _ {O}} _ {1} (n, n_ {1} )}$

onde é uma fórmula de primeira ordem sem quantificadores ilimitados. ${\ displaystyle {\ varphi _ {O}} _ {1} (n, n_ {1})}$

Salto de Turing

Se O é um oráculo para o problema de parada de uma máquina , então é o mesmo que "existe tal que começar com a entrada m está no estado de parada após as etapas". Assim: onde está uma fórmula de primeira ordem que se formaliza . Se é uma máquina de Turing (sem oráculo), está em (ou seja, não tem quantificadores ilimitados). ${\ displaystyle T '}$${\ displaystyle \ psi ^ {O} (m)}$${\ displaystyle m_ {1}}$${\ displaystyle T '}$${\ displaystyle m_ {1}}$${\ displaystyle \ psi ^ {O} (m) = \ existe m_ {1}: \ psi _ {H} (m, m_ {1})}$${\ displaystyle \ psi _ {H} (m, m_ {1})}$${\ displaystyle T '}$${\ displaystyle T '}$${\ displaystyle \ psi _ {H} (m, m_ {1})}$${\ displaystyle \ Sigma _ {0} ^ {0} = \ Pi _ {0} ^ {0}}$

Uma vez que existe um número finito de números m satisfatórios , podemos escolher o mesmo número de passos para todos eles: existe um número , tal que pára após os passos precisamente naquelas entradas para as quais ele pára. ${\ displaystyle m <2 ^ {n_ {1}}}$${\ displaystyle m_ {1}}$${\ displaystyle T '}$${\ displaystyle m_ {1}}$${\ displaystyle m <2 ^ {n_ {1}}}$

Movendo para a forma normal prenex , obtemos que a máquina oracle pára na entrada se e somente se a seguinte fórmula for satisfeita: ${\ displaystyle n}$${\ displaystyle \ varphi (n) = \ existe n_ {1} \ existe m_ {1} \ forall m_ {2}: (\ psi _ {H} (m, m_ {2}) \ rightarrow (O_ {m} = 1)) \ land (\ lnot \ psi _ {H} (m, m_ {1}) \ rightarrow (O_ {m} = 0))) \ land {\ varphi _ {O}} _ {1} ( n, n_ {1})}$

(informalmente, há um "número máximo de passos", tal que todo oráculo que não para nos primeiros passos não para de forma alguma; entretanto, para cada , cada oráculo que para após os passos pára). ${\ displaystyle m_ {1}}$${\ displaystyle m_ {1}}$${\ displaystyle m_ {2}}$${\ displaystyle m_ {2}}$

Observe que podemos substituir ambos e por um único número - seu máximo - sem alterar o valor verdadeiro de . Assim, podemos escrever: ${\ displaystyle n_ {1}}$${\ displaystyle m_ {1}}$${\ displaystyle \ varphi (n)}$${\ displaystyle \ varphi (n) = \ existe n_ {1} \ forall m_ {2}: (\ psi _ {H} (m, m_ {2}) \ rightarrow (O_ {m} = 1)) \ land (\ lnot \ psi _ {H} (m, n_ {1}) \ rightarrow (O_ {m} = 0))) \ land {\ varphi _ {O}} _ {1} (n, n_ {1} )}$

Para o oráculo do problema da parada sobre as máquinas de Turing, está e está na . Assim, todo conjunto recursivamente enumerável por uma máquina oráculo com um oráculo para , está em . ${\ displaystyle \ psi _ {H} (m, m_ {1})}$${\ displaystyle \ Pi _ {0} ^ {0}}$${\ displaystyle \ varphi (n)}$${\ displaystyle \ Sigma _ {2} ^ {0}}$${\ displaystyle \ emptyset ^ {(1)}}$${\ displaystyle \ Sigma _ {2} ^ {0}}$

O inverso também é verdadeiro: suponha que seja uma fórmula com quantificadores existenciais seguidos por quantificadores universais. Equivalentemente, tem > quantificadores existenciais seguidos por uma negação de uma fórmula em ; a última fórmula pode ser enumerada por uma máquina de Turing e, portanto, pode ser verificada imediatamente por um oráculo . ${\ displaystyle \ varphi (n)}$${\ displaystyle \ Sigma _ {2} ^ {0}}$${\ displaystyle k_ {1}}$${\ displaystyle k_ {2}}$${\ displaystyle \ varphi (n)}$${\ displaystyle k_ {1}}$${\ displaystyle \ Sigma _ {1} ^ {0}}$${\ displaystyle \ emptyset ^ {(1)}}$

Podemos, assim, enumerar as –tuplos dos números naturais e operar uma máquina de oráculo com um oráculo para que passe por todos eles até encontrar uma satisfação para a fórmula. Esta máquina oráculo pára precisamente no conjunto de números naturais que satisfazem e, portanto, enumera seu conjunto correspondente. ${\ displaystyle k_ {1}}$${\ displaystyle \ emptyset ^ {(1)}}$${\ displaystyle \ varphi (n)}$

Saltos de Turing mais altos

De maneira mais geral, suponha que cada conjunto recursivamente enumerável por uma máquina oráculo com um oráculo para está em . Então, para uma máquina oráculo com um oráculo para , está em . ${\ displaystyle \ emptyset ^ {(p)}}$${\ displaystyle \ Sigma _ {p + 1} ^ {0}}$${\ displaystyle \ emptyset ^ {(p + 1)}}$${\ displaystyle \ psi ^ {O} (m) = \ existe m_ {1}: \ psi _ {H} (m, m_ {1})}$${\ displaystyle \ Sigma _ {p + 1} ^ {0}}$

Como é o mesmo do salto de Turing anterior, ele pode ser construído (como acabamos de fazer acima) de forma que em . Depois de passar para a forma formal prenex, o novo está disponível . ${\ displaystyle \ psi ^ {O} (m)}$${\ displaystyle \ varphi (n)}$${\ displaystyle \ varphi (n)}$${\ displaystyle \ psi _ {H} (m, m_ {1})}$${\ displaystyle \ Pi _ {p} ^ {0}}$${\ displaystyle \ varphi (n)}$${\ displaystyle \ Sigma _ {p + 2} ^ {0}}$

Por indução, todo conjunto recursivamente enumerável por uma máquina oráculo com um oráculo para , está em . ${\ displaystyle \ emptyset ^ {(p)}}$${\ displaystyle \ Sigma _ {p + 1} ^ {0}}$

A outra direção também pode ser provada por indução: suponha que cada fórmula em possa ser enumerada por uma máquina de oráculo com um oráculo para . ${\ displaystyle \ Sigma _ {p + 1} ^ {0}}$${\ displaystyle \ emptyset ^ {(p)}}$

Agora, suponha que seja uma fórmula em com quantificadores existenciais seguidos por quantificadores universais etc. Equivalentemente, tem > quantificadores existenciais seguidos por uma negação de uma fórmula em ; a última fórmula pode ser enumerada por uma máquina de oráculo com um oráculo para e, portanto, pode ser verificada imediatamente por um oráculo para . ${\ displaystyle \ varphi (n)}$${\ displaystyle \ Sigma _ {p + 2} ^ {0}}$${\ displaystyle k_ {1}}$${\ displaystyle k_ {2}}$${\ displaystyle \ varphi (n)}$${\ displaystyle k_ {1}}$${\ displaystyle \ Sigma _ {p + 1} ^ {0}}$${\ displaystyle \ emptyset ^ {(p)}}$${\ displaystyle \ emptyset ^ {(p + 1)}}$

Podemos, assim, enumerar as –tuplos dos números naturais e operar uma máquina de oráculo com um oráculo para que passe por todos eles até encontrar uma satisfação para a fórmula. Esta máquina oráculo pára precisamente no conjunto de números naturais que satisfazem e, portanto, enumera seu conjunto correspondente. ${\ displaystyle k_ {1}}$${\ displaystyle \ emptyset ^ {(p + 1)}}$${\ displaystyle \ varphi (n)}$

Referências

Rogers, H. Theory of Recursive Functions and Effective Computability , MIT Press. ISBN  0-262-68052-1 ; ISBN  0-07-053522-1

Soare, R. Conjuntos e graus recursivamente enumeráveis. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN  3-540-15299-7