On Formally Undecidable Propositions of Principia Mathematica and Related Systems"Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I" ("On Formally Undecidable Propositions of Principia Mathematica and Related Systems I") is a paper in mathematical logic by Kurt Gödel. Submitted November 17, 1930, it was originally published in German in the 1931 volume of Monatshefte für Mathematik. Several English translations have appeared in print, and the paper has been included in two collections of classic mathematical logic papers.
Théorèmes d'incomplétude de GödelLes théorèmes d'incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, publiés par Kurt Gödel en 1931 dans son article (« Sur les propositions formellement indécidables des Principia Mathematica et des systèmes apparentés »). Ils ont marqué un tournant dans l'histoire de la logique en apportant une réponse négative à la question de la démonstration de la cohérence des mathématiques posée plus de 20 ans auparavant par le programme de Hilbert.
Théorie de la calculabilitéLa théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est un domaine de la logique mathématique et de l'informatique théorique. La calculabilité (parfois appelée « computationnalité », de l'anglais computability) cherche d'une part à identifier la classe des fonctions qui peuvent être calculées à l'aide d'un algorithme et d'autre part à appliquer ces concepts à des questions fondamentales des mathématiques. Une bonne appréhension de ce qui est calculable et de ce qui ne l'est pas permet de voir les limites des problèmes que peuvent résoudre les ordinateurs.
ComputabilityComputability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem. The most widely studied models of computability are the Turing-computable and μ-recursive functions, and the lambda calculus, all of which have computationally equivalent power.
Lambda-calculLe lambda-calcul (ou λ-calcul) est un système formel inventé par Alonzo Church dans les années 1930, qui fonde les concepts de fonction et d'application. On y manipule des expressions appelées λ-expressions, où la lettre grecque λ est utilisée pour lier une variable. Par exemple, si M est une λ-expression, λx.M est aussi une λ-expression et représente la fonction qui à x associe M. Le λ-calcul a été le premier formalisme pour définir et caractériser les fonctions récursives : il a donc une grande importance dans la théorie de la calculabilité, à l'égal des machines de Turing et du modèle de Herbrand-Gödel.
Théorie oméga-cohérenteEn logique mathématique une théorie arithmétique est appelée théorie ω-cohérente (oméga-cohérente) quand, pour toute propriété P des nombres entiers que l'on peut exprimer dans le langage de la théorie, si pour chaque entier n, P(n) est démontrable dans la théorie, alors ¬∀x P(x) n'est pas démontrable dans la théorie (¬ pour la négation, ∀ pour la quantification universelle, « pour tout »). Quand on prend pour P un énoncé clos (qui ne dépend pas de x) on retrouve la définition de la cohérence, appelée parfois dans ce contexte cohérence simple, qui est donc conséquence de l'ω-cohérence.
Diagonal lemmaIn mathematical logic, the diagonal lemma (also known as diagonalization lemma, self-reference lemma or fixed point theorem) establishes the existence of self-referential sentences in certain formal theories of the natural numbers—specifically those theories that are strong enough to represent all computable functions. The sentences whose existence is secured by the diagonal lemma can then, in turn, be used to prove fundamental limitative results such as Gödel's incompleteness theorems and Tarski's undefinability theorem.
