| Property |
Value |
| dbo:abstract
|
- 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)
- 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)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 907 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdfs:comment
|
- 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)
- 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
|
- Post's theorem (en)
- Théorème de Post (fr)
- ポストの定理 (ja)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
