Post's theorem
http://dbpedia.org/resource/Post's_theorem an entity of type: Thing
Postova věta popisuje v teoretické informatice vztah mezi rekurzivitou a rekurzivní spočetností. Říká, že množina M je rekurzivní právě tehdy, pokud jsou jak M, tak její doplněk rekurzivně spočetné. Je pojmenována podle Emila Posta.
rdf:langString
In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.
rdf:langString
ポストの定理（英: Post's theorem）は、計算可能性理論における定理で、算術的階層とチューリング次数の関係を表している。名称はエミール・ポストに因んでいる。
rdf:langString
Na teoria da computação, o Teorema de Post,em homenagem à Emil Post, descreve a conexão entre hierarquia aritmética e os graus de Turing.
rdf:langString
Теорема По́ста — теорема теории вычислимости о рекурсивно перечислимых множествах.
rdf:langString
En théorie de la calculabilité, le théorème de Post, du nom d'Emil Post, fait le lien entre hiérarchie arithmétique et degré de Turing. Théorème — Pour tout n > 0 :
* B appartient à Σn+1 si et seulement si B est récursivement énumérable avec oracle (ou Σn) ;
* ∅(n), c'est-à-dire le n-ième degré de Turing après ∅, est Σn-complet. En particulier :
rdf:langString
rdf:langString
Postova věta
rdf:langString
Théorème de Post
rdf:langString
ポストの定理
rdf:langString
Post's theorem
rdf:langString
Teorema de Post
rdf:langString
Теорема Поста
xsd:integer
764468
xsd:integer
1029346782
rdf:langString
Postova věta popisuje v teoretické informatice vztah mezi rekurzivitou a rekurzivní spočetností. Říká, že množina M je rekurzivní právě tehdy, pokud jsou jak M, tak její doplněk rekurzivně spočetné. Je pojmenována podle Emila Posta.
rdf:langString
En théorie de la calculabilité, le théorème de Post, du nom d'Emil Post, fait le lien entre hiérarchie arithmétique et degré de Turing. Théorème — Pour tout n > 0 :
* B appartient à Σn+1 si et seulement si B est récursivement énumérable avec oracle (ou Σn) ;
* ∅(n), c'est-à-dire le n-ième degré de Turing après ∅, est Σn-complet. En particulier :
* B est dans Σn+1 si et seulement si B est récursivement énumérable avec l'oracle ∅(n) ;
* B est dans Δn+1 si et seulement si B est Turing-réductible à ∅(n).
* Portail de l'informatique théorique
* Portail de la logique
* Portail des mathématiques
rdf:langString
In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.
rdf:langString
ポストの定理（英: Post's theorem）は、計算可能性理論における定理で、算術的階層とチューリング次数の関係を表している。名称はエミール・ポストに因んでいる。
rdf:langString
Na teoria da computação, o Teorema de Post,em homenagem à Emil Post, descreve a conexão entre hierarquia aritmética e os graus de Turing.
rdf:langString
Теорема По́ста — теорема теории вычислимости о рекурсивно перечислимых множествах.
xsd:nonNegativeInteger
18257