| dbo:abstract
|
- 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. (cs)
- 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 (fr)
- In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees. (en)
- ポストの定理（英: Post's theorem）は、計算可能性理論における定理で、算術的階層とチューリング次数の関係を表している。名称はエミール・ポストに因んでいる。 (ja)
- 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. (pt)
- Теорема По́ста — теорема теории вычислимости о рекурсивно перечислимых множествах. (ru)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 18257 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- 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. (cs)
- In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees. (en)
- ポストの定理（英: Post's theorem）は、計算可能性理論における定理で、算術的階層とチューリング次数の関係を表している。名称はエミール・ポストに因んでいる。 (ja)
- 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. (pt)
- Теорема По́ста — теорема теории вычислимости о рекурсивно перечислимых множествах. (ru)
- 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 : (fr)
|
| rdfs:label
|
- Postova věta (cs)
- Théorème de Post (fr)
- ポストの定理 (ja)
- Post's theorem (en)
- Teorema de Post (pt)
- Теорема Поста (ru)
|
| rdfs:seeAlso
| |
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:knownFor
of | |
| is rdfs:seeAlso
of | |
| is foaf:primaryTopic
of | |
