| Property |
Value |
| dbo:abstract
|
- En logique mathématique, on appelle problème de la décision ou, sous son nom d'origine en allemand, Entscheidungsproblem, le fait de déterminer de façon mécanique (par un algorithme) si un énoncé est un théorème de la logique égalitaire du premier ordre, c’est-à-dire s'il se dérive dans un système de déduction sans autres axiomes que ceux de l'égalité (exemples : système à la Hilbert, calcul des séquents, déduction naturelle). De façon équivalente par le théorème de complétude, il s'agit finalement de savoir si un énoncé est universellement valide, c’est-à-dire vrai dans tous les modèles (de l'égalité). Le problème de la décision est un exemple de problème de décision : une question de décidabilité au sens algorithmique. Ici la question est celle de la décidabilité du calcul des prédicats égalitaire du premier ordre : l'ensemble des énoncés universellement valides du calcul des prédicats du premier ordre est-il décidable ? Le problème de la décision dépend en fait du choix du langage du premier ordre : sa signature, les « briques » de base qui permettent la construction des énoncés, les symboles de constantes, de fonctions (ou opérations), et de prédicat (par exemple 0, +, ≤…). Dans un langage donné (exemple : dans l'arithmétique de Peano, c'est le langage arithmétique), une solution positive AU problème de la décision fournit une solution positive AUX problèmes de la décision pour toutes les théories finiment axiomatisables de ce langage. En effet, un énoncé C se déduit d'un système fini d'axiomes si et seulement si on peut dériver en logique pure que la conjonction de ces axiomes entraîne C. (fr)
- En logique mathématique, on appelle problème de la décision ou, sous son nom d'origine en allemand, Entscheidungsproblem, le fait de déterminer de façon mécanique (par un algorithme) si un énoncé est un théorème de la logique égalitaire du premier ordre, c’est-à-dire s'il se dérive dans un système de déduction sans autres axiomes que ceux de l'égalité (exemples : système à la Hilbert, calcul des séquents, déduction naturelle). De façon équivalente par le théorème de complétude, il s'agit finalement de savoir si un énoncé est universellement valide, c’est-à-dire vrai dans tous les modèles (de l'égalité). Le problème de la décision est un exemple de problème de décision : une question de décidabilité au sens algorithmique. Ici la question est celle de la décidabilité du calcul des prédicats égalitaire du premier ordre : l'ensemble des énoncés universellement valides du calcul des prédicats du premier ordre est-il décidable ? Le problème de la décision dépend en fait du choix du langage du premier ordre : sa signature, les « briques » de base qui permettent la construction des énoncés, les symboles de constantes, de fonctions (ou opérations), et de prédicat (par exemple 0, +, ≤…). Dans un langage donné (exemple : dans l'arithmétique de Peano, c'est le langage arithmétique), une solution positive AU problème de la décision fournit une solution positive AUX problèmes de la décision pour toutes les théories finiment axiomatisables de ce langage. En effet, un énoncé C se déduit d'un système fini d'axiomes si et seulement si on peut dériver en logique pure que la conjonction de ces axiomes entraîne C. (fr)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 7402 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1936 (xsd:integer)
- 1937 (xsd:integer)
- 1938 (xsd:integer)
|
| prop-fr:doi
| |
| prop-fr:langue
| |
| prop-fr:lienAuteur
|
- Alan Turing (fr)
- Alonzo Church (fr)
- Alan Turing (fr)
- Alonzo Church (fr)
|
| prop-fr:lienPériodique
|
- London Mathematical Society#Publications (fr)
- London Mathematical Society#Publications (fr)
|
| prop-fr:lireEnLigne
| |
| prop-fr:nom
|
- Turing (fr)
- Church (fr)
- Turing (fr)
- Church (fr)
|
| prop-fr:pages
|
- 40 (xsd:integer)
- 230 (xsd:integer)
- 245 (xsd:integer)
- 544 (xsd:integer)
|
| prop-fr:prénom
|
- Alan (fr)
- Alonzo (fr)
- Alan (fr)
- Alonzo (fr)
|
| prop-fr:revue
|
- American Journal of Mathematics (fr)
- Proc. London Math. Soc. (fr)
- Journal of Symbolic Logic (fr)
- American Journal of Mathematics (fr)
- Proc. London Math. Soc. (fr)
- Journal of Symbolic Logic (fr)
|
| prop-fr:sousTitre
|
- A Correction (fr)
- A Correction (fr)
|
| prop-fr:série
| |
| prop-fr:titre
|
- On Computable Numbers, with an Application to the Entscheidungsproblem (fr)
- A Note on the Entscheidungsproblem (fr)
- An Unsolvable Problem of Elementary Number Theory (fr)
- [idem] (fr)
- On Computable Numbers, with an Application to the Entscheidungsproblem (fr)
- A Note on the Entscheidungsproblem (fr)
- An Unsolvable Problem of Elementary Number Theory (fr)
- [idem] (fr)
|
| prop-fr:volume
|
- 1 (xsd:integer)
- 42 (xsd:integer)
- 43 (xsd:integer)
- 58 (xsd:integer)
|
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdfs:comment
|
- En logique mathématique, on appelle problème de la décision ou, sous son nom d'origine en allemand, Entscheidungsproblem, le fait de déterminer de façon mécanique (par un algorithme) si un énoncé est un théorème de la logique égalitaire du premier ordre, c’est-à-dire s'il se dérive dans un système de déduction sans autres axiomes que ceux de l'égalité (exemples : système à la Hilbert, calcul des séquents, déduction naturelle). De façon équivalente par le théorème de complétude, il s'agit finalement de savoir si un énoncé est universellement valide, c’est-à-dire vrai dans tous les modèles (de l'égalité). (fr)
- En logique mathématique, on appelle problème de la décision ou, sous son nom d'origine en allemand, Entscheidungsproblem, le fait de déterminer de façon mécanique (par un algorithme) si un énoncé est un théorème de la logique égalitaire du premier ordre, c’est-à-dire s'il se dérive dans un système de déduction sans autres axiomes que ceux de l'égalité (exemples : système à la Hilbert, calcul des séquents, déduction naturelle). De façon équivalente par le théorème de complétude, il s'agit finalement de savoir si un énoncé est universellement valide, c’est-à-dire vrai dans tous les modèles (de l'égalité). (fr)
|
| rdfs:label
|
- Avgörbarhetsproblemet (sv)
- Entscheidungsproblem (it)
- Problème de la décision (fr)
- Задача розв'язності (uk)
- Проблема разрешения (ru)
- مسألة القرار (رياضيات) (ar)
- 可判定性 (zh)
- Avgörbarhetsproblemet (sv)
- Entscheidungsproblem (it)
- Problème de la décision (fr)
- Задача розв'язності (uk)
- Проблема разрешения (ru)
- مسألة القرار (رياضيات) (ar)
- 可判定性 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
