Emil Post
- Emil Post
-
Pour les articles homonymes, voir
Post.
Emil Leon Post (né le 11 février 1897 à Augustów et mort le 21 avril 1954 à New York) est un mathématicien américain né sur le territoire de l'actuelle Pologne dans une famille juive. Il est à l'origine du problème de correspondance de Post (en)[1].
Il a également publié en 1921 une étude exhaustive des clones des algèbres à deux éléments.
Travaux sur le calcul propositionnel
Dans son Introduction to a general theory of elementary propositions de 1921, il établit la complétude sémantique du calcul propositionnel des Principia Mathematica de Whitehead et Russell par le système des table de vérités. Puis il généralise ce résultat à tout calcul propositionnel fini-valent (et non uniquement bivalent ).
Le problème de correspondance de Post
On part de deux suites finies U et V contenant le même nombre de mots finis sur un alphabet quelconque. Par exemple
.
On cherche une suite d'indices i1,i2,...in telle que la concaténation des 
corresponde à celle des 
. Ici la suite (1,2,3,2,1) est une solution puisque
.
Le problème de correspondance de Post (en abrégé PCP) consiste à déterminer s'il existe une telle suite. Il est indécidable : il n'existe pas d'algorithme général capable de fournir une réponse pour des U et V arbitraires.
Bibliographie
- Emil Post, Introduction to a general theory of elementary propositions, 1921. Reproduit dans (en) Jean van Heijenoort (dir.), From Frege To Gödel: A Source Book in Mathematical Logic, 1879-1931, Harvard Univ. Press., 1977 (1re éd. 1967) [présentation en ligne] pp. 264-283. Traduction française, Jean Largeault (dir.), Logique Mathématique : Textes, Armand Colin, 1972
Note et référence
- ↑ (en) E. L. Post, « A variant of a recursively unsolvable problem », dans Bull. Amer. Math. Soc, vol. 52, 1946 [texte intégral]
Articles connexes
Catégories :
- Personnalité américaine d'origine russe
- Personnalité américaine en informatique
- Personnalité en informatique théorique
- Naissance en 1897
- Décès en 1954
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Emil Post de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Emil Post — Emil Leon Post Emil Leon Post (* 11. Februar 1897 in Augustów, Polen; † 21. April 1954 in New York, USA) war ein polnisch US amerikanischer Mathematiker und Logiker … Deutsch Wikipedia
POST (E. L.) — POST EMIL LEON (1897 1954) Mathématicien américain né à Augustów (Pologne) et mort à New York. Arrivé aux États Unis en 1904, Emil Post obtint son Ph.D. à l’université Columbia de New York en 1920. Il était membre de l’American Mathematical… … Encyclopédie Universelle
Post's inversion formula — for Laplace transforms, named after Emil Post, is a simple looking but usually impractical formula for evaluating an inverse Laplace transform.The statement of the formula is as follows: Let f ( t ) be a continuous function on the interval [0,… … Wikipedia
Emil Leon Post — Infobox Scientist name = Emil Leon Post image width = birth date = February 11, 1897 birth place = Augustów, then Russian Empire death date = April 21 1954, death place = New York City, flagicon|USA U.S. residence = nationality = field =… … Wikipedia
Post–Turing machine — The article Turing machine gives a general introduction to Turing machines, while this article covers a specific class of Turing machines. A Post–Turing machine is a program formulation of an especially simple type of Turing machine, comprising a … Wikipedia
Emil — The name Emil or Emile is a male given name, deriving from the latin Aemilius of the gens Aemilia . The female given name is Emily .Famous bearers of the name Emil include: *Emil Ali, Business Owner, Former Music Industry Executive *Emil Brown,… … Wikipedia
Post canonical system — A Post canonical system, as created by Emil Post, is a string manipulation system that starts with finitely many strings and repeatedly transforms them by applying a finite set of specified rules of a certain form, thus generating a formal… … Wikipedia
Post — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Pour l’article homophone, voir Poste. Sigles d’une seule lettre … Wikipédia en Français
Post correspondence problem — The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946.[1] Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability. Contents 1… … Wikipedia
Post's lattice — In logic and universal algebra, Post s lattice denotes the lattice of all clones on a two element set {0, 1}, ordered by inclusion. It is named for Emil Post, who published a complete description of the lattice in 1941 [E. L. Post, The two valued … Wikipedia
Emil Leon Post
