Corrado Böhm

Corrado Böhm
ETH Zürich
Scientific career
Fields	Computer science
Institutions	University of Rome "La Sapienza"
Doctoral advisor	Eduard Stiefel Paul Bernays
Doctoral students	Giorgio Ausiello Mariangiola Dezani-Ciancaglini

Corrado Böhm (17 January 1923 – 23 October 2017) was an Italian

languages.

Work

In his PhD dissertation (in Mathematics, at ETH Zurich, 1951; published in 1954), Böhm describes for the first time a full meta-circular compiler, that is a translation mechanism of a programming language, written in that same language. His most influential contribution is the so-called structured program theorem, published in 1966 together with Giuseppe Jacopini. Together with Alessandro Berarducci, he demonstrated an isomorphism between the strictly-positive algebraic data types and the polymorphic lambda-terms, otherwise known as Böhm–Berarducci encoding.^[1]

In the

, which is a semantic property, may be decided through equality of normal forms, a syntactic property, as it coincides with βη-equality.

A special issue of Theoretical Computer Science was dedicated to him in 1993, on his 70th birthday. He is the recipient of the 2001 EATCS Award for a distinguished career in theoretical computer science.

• Böhm, Corrado (1954). "Calculatrices digitales. Du déchiffrage des formules mathématiques par la machine même dans la conception du programme" (PDF). Annali di Mat. pura e applicata. serie IV (tomo XXXVII): 1–51. "Böhm: Digital computers. On encoding logical-mathematical formulas using the machine itself during program conception". Translated by Sestoft, B. 4 May 2016.
• — (1964). "On a family of Turing machines and the related programming language". ICC bulletin. 3: 185–194.
  Turing-complete
  .
• —;
  S2CID 10236439
  .
• — (1968). "Alcune proprietà delle forme β-η-normali nel λ-K-calcolo". Pubbl. INAC (in Italian). 696. Roma.
• —; Berarducci, A. (1985). "Automatic Synthesis of typed Lambda-programs on Term Algebras".
  doi:10.1016/0304-3975(85)90135-5
  .
• — (1988). "Functional Programming and Combinatory Algebras". In Chytil, M.P.; Janiga, L.; Koubek, V. (eds.). MFCS. LNCS 324. Carlsbad, Czechoslovakia. pp. 14–26.

See also

• P′′, a minimal computer programming language
• Structured program theorem
• List of pioneers in computer science
• Böhm tree
• Böhm's theorem

References

1. ^ "Boehm-Berarducci Encoding".

• Vitae (University of Rome)

External links

• Corrado Böhm at the Mathematics Genealogy Project
• "A Collection of Contributions in Honour of Corrado Böhm on the Occasion of his 70th Birthday", Theoretical Computer Science, Volume 121, Numbers 1&2, 1993.
• Corrado Böhm's personal page.

P ≟ NP

This biographical article relating to a computer scientist is a stub. You can help Wikipedia by expanding it.

• v
• t
• e