Per MartinLöf
Per MartinLöf  

Per MartinLöf in 2004


Born  May 8, 1942 
Citizenship  Sweden 
Nationality  Swedish 
Fields  Computer Science Logic Mathematical statistics Philosophy 
Institutions  Stockholm University University of Chicago Aarhus University 
Alma mater  Stockholm University 
Doctoral advisor  Andrei N. Kolmogorov 
Known for  Random sequences Exact tests Repetitive structure Sufficient statistics Expectation maximization method Type theory 
Notable awards  Royal Swedish Academy of Sciences 
Per Erik Rutger MartinLöf (born 1942) is a Swedish logician, philosopher, and mathematical statistician. He is internationally renowned for his work on the foundations of probability, statistics, mathematical logic, and computer science. Since the late 1970s, MartinLöf's publications have been mainly in logic. In philosophical logic, MartinLöf has wrestled with the philosophy of logical consequence and judgment, partly inspired by the work of Brentano, Frege, and Husserl. In mathematical logic, MartinLöf has been active in developing intuitionistic type theory as a constructive foundation of mathematics; MartinLöf's work on type theory has influenced computer science.^{[1]}
Until his retirement in 2009,^{[2]} Per MartinLöf held a joint chair for Mathematics and Philosophy at Stockholm University.^{[3]}
His brother Anders MartinLöf is now emeritus professor of mathematical statistics at Stockholm University; the two brothers have collaborated in research in probability and statistics. The research of Anders and Per MartinLöf has influenced statistical theory, especially concerning exponential families, the expectationmaximization method for missing data, and model selection.^{[4]}
Per MartinLöf is an enthusiastic birdwatcher, whose first scientific publication was on the mortality rates of ringed birds.^{[5]}
Contents
Randomness and Kolmogorov complexity
In 1964 and 1965, MartinLöf studied in Moscow under the supervision of Andrei N. Kolmogorov. He wrote a 1966 article On the definition of random sequences that gave the first suitable definition of a random sequence.
Earlier researchers such as Richard von Mises had attempted to formalize the notion of a test for randomness in order to define a random sequence as one that passed all tests for randomness; however, the precise notion of a randomness test was left vague. MartinLöf's key insight was to use the theory of computation to define formally the notion of a test for randomness. This contrasts with the idea of randomness in probability; in that theory, no particular element of a sample space can be said to be random.
MartinLöf randomness has since been shown to admit many equivalent characterizations — in terms of compression, randomness tests, and gambling — that bear little outward resemblance to the original definition, but each of which satisfies our intuitive notion of properties that random sequences ought to have: random sequences should be incompressible, they should pass statistical tests for randomness, and it should be impossible to make money betting on them. The existence of these multiple definitions of MartinLöf randomness, and the stability of these definitions under different models of computation, give evidence that MartinLöf randomness is a fundamental property of mathematics and not an accident of MartinLöf's particular model. The thesis that the definition of MartinLöf randomness "correctly" captures the intuitive notion of randomness has been called the "MartinLöfChaitin Thesis"; it is somewhat similar to the Church–Turing thesis.^{[6]}
Following MartinLöf's work, algorithmic information theory defines a random string as one that cannot be produced from any computer program that is shorter than the string (Chaitin–Kolmogorov randomness); i.e. a string whose Kolmogorov complexity is at least the length of the string. This is a different meaning from the usage of the term in statistics. Whereas statistical randomness refers to the process that produces the string (e.g. flipping a coin to produce each bit will randomly produce a string), algorithmic randomness refers to the string itself. Algorithmic information theory separates random from nonrandom strings in a way that is relatively invariant to the model of computation being used.
An algorithmically random sequence is an infinite sequence of characters, all of whose prefixes (except possibly a finite number of exceptions) are strings that are "close to" algorithmically random (their length is within a constant of their Kolmogorov complexity).
Mathematical statistics
Per MartinLöf has done important research in mathematical statistics, which (in the Swedish tradition) includes probability theory and statistics.
Birdwatching and sex determination
Per MartinLöf began bird watching in his youth and remains an enthusiastic birdwatcher.^{[7]} As a teenager, he published an article on estimating the mortality rates of birds, using data from bird ringing, in a Swedish zoological journal: This paper was soon cited in leading international journals, and this paper continues to be cited.^{[5]}^{[8]}
In the biology and statistics of birds, there are several problems of missing data. MartinLöf's first paper discussed the problem of estimating the mortality rates of the Dunlin species, using capturerecapture methods. A second problem of missing data arises with studying the sex of birds. The problem of determining the biological sex of a bird, which is extremely difficult for humans, is one of the first examples in MartinLöf's lectures on statistical models.
Probability on algebraic structures
MartinLöf wrote a licenciate thesis on probability on algebraic structures, particularly semigroups, a research program led by Ulf Grenander at Stockholm University.^{[9]}^{[10]}^{[11]}
Statistical models
MartinLöf developed innovative approaches to statistical theory. In his paper "On Tables of Random Numbers", Kolmogorov observed that the frequency probability notion of the limiting properties of infinite sequences failed to provide a foundation for statistics, which considers only finite samples.^{[12]} Much of MartinLöf's work in statistics was to provide a finitesample foundation for statistics.
Model selection and hypothesis testing
In the 1970s, Per MartinLöf made important contributions to statistical theory and inspired further research, especially by Scandinavian statisticians including Rolf Sundberg, Thomas Höglund, and Steffan Lauritzen. In this work, MartinLöf's previous research on probability measures on semigroups led to a notion of "repetitive structure" and a novel treatment of sufficient statistics, in which oneparameter exponential families were characterized. He provided a categorytheoretic approach to nested statistical models, using finitesample principles. Before (and after) MartinLöf, such nested models have often been tested using chisquare hypothesis tests, whose justifications are only asymptotic (and so irrelevant to real problems, which always have finite samples).^{[12]}
Expectation maximization method for exponential families
MartinLöf's student, Rolf Sundberg, developed a detailed analysis of the expectationmaximization (EM) method for estimation using data from exponential families, especially with missing data. Sundberg credits a formula, later known as the Sundberg formula, to previous manuscripts of the MartinLöf brothers, Per and Anders.^{[13]}^{[14]}^{[15]}^{[16]} Many of these results reached the international scientific community through the 1976 paper on the expectation maximization (EM) method by Arthur P. Dempster, Nan Laird, and Donald Rubin, which was published in a leading international journal, sponsored by the Royal Statistical Society.^{[17]}
Logic
Philosophical logic
In philosophical logic, Per MartinLöf has published papers on the theory of logical consequence, on judgments, etc. He has been interested in CentralEuropean philosophical traditions, especially of the Germanlanguage writings of Franz Brentano, Gottlob Frege, and of Edmund Husserl.
Type theory
MartinLöf has worked in mathematical logic for many decades.
From 1968 to '69 he worked as an Assistant Professor at the University of Chicago where he met William Alvin Howard with whom he discussed issues related to the Curry–Howard correspondence. MartinLöf's first draft article on type theory dates back to 1971. This impredicative theory generalized Girard's System F. However, this system turned out to be inconsistent due to Girard's paradox which was discovered by Girard when studying System U, an inconsistent extension of System F. This experience led Per MartinLöf to develop the philosophical foundations of type theory, his meaning explanation, a form of prooftheoretic semantics, which justifies predicative type theory as presented in his 1984 Bibliopolis book, and extended in a number of increasingly philosophical texts, such as his influential On the Meanings of the Logical Constants and the Justifications of the Logical Laws.
The 1984 type theory was extensional while the type theory presented in the book by Nordström et al. in 1990, which was heavily influenced by his later ideas, intensional, and more amenable to being implemented on a computer.
MartinLöf's intuitionistic type theory developed the notion of dependent types and directly influenced the development of the calculus of constructions and the logical framework LF. A number of popular computerbased proof systems are based on type theory, for example NuPRL, LEGO, Coq, ALF, Agda, Twelf and Epigram.
Awards
MartinLöf is a member of the Royal Swedish Academy of Sciences^{[18]} and of the Academia Europaea.^{[3]}
See also
 Franz Brentano
 Rudolf Carnap
 Michael Dummett
 Gottlob Frege
 Jaakko Hintikka
 Edmund Husserl
 Andrei N. Kolmogorov
 Anders MartinLöf
 John von Neumann
 Peter Pagin
 Dag Prawitz
 Charles Sanders Peirce
 Frank P. Ramsey
 Bertrand Russell
 Dana Scott
 Alfred Tarski
 Alan Turing
Notes
 ↑ See e.g. Nordström, Bengt; Petersson, Kent; Smith, Jan M. (1990), Programming in MartinLöf ’s Type Theory: An Introduction (PDF), Oxford University Press<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>.
 ↑ Philosophy and Foundations of Mathematics: Epistemological and Ontological Aspects. A conference dedicated to Per MartinLöf on the occasion of his retirement. Swedish Collegium for Advanced Study, Uppsala, May 58, 2009. Retrieved 20140126.
 ↑ ^{3.0} ^{3.1} Member profile, Academia Europaea, retrieved 20140126.
 ↑ For details, see the #Statistical models section of this article.
 ↑ ^{5.0} ^{5.1} MartinLöf (1961).
 ↑ JeanPaul Delahaye, Randomness, Unpredictability and Absence of Order, in Philosophy of Probability, p. 145–167, Springer 1993.
 ↑ George A. Barnard, "Gone Birdwatching", New Scientist, 4 December 1999, magazine issue 2215.
 ↑ S. M. Taylor (1966). "Recent Quantitative Work on British Bird Populations. A Review". Journal of the Royal Statistical Society, Series D,. 16 (=No. 2): 119–170. JSTOR 2986734.CS1 maint: extra punctuation (link)<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ MartinLöf, P. The continuity theorem on a locally compact group. Teor. Verojatnost. i Primenen. 10 1965 367–371.
 ↑ MartinLöf, Per Probability theory on discrete semigroups. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 4 1965 78–102
 ↑ Nitis Mukhopadhyay. A Conversation with Ulf Grenander. Statist. Sci. Volume 21, Number 3 (2006), 404–426.
 ↑ ^{12.0} ^{12.1} Kolmogorov, Andrei N. (1963). "On Tables of Random Numbers". Sankhyā Ser. A. 25: 369–375.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ Rolf Sundberg. 1971. Maximum likelihood theory and applications for distributions generated when observing a function of an exponential family variable. Dissertation, Institute for Mathematical Statistics, Stockholm University.
 ↑ Anders MartinLöf. 1963. "Utvärdering av livslängder i subnanosekundsområdet" ("Evaluation of lifetimes in timelengths below one nanosecond"). ("Sundberg formula")
 ↑ Per MartinLöf. 1966. Statistics from the point of view of statistical mechanics. Lecture notes, Mathematical Institute, Aarhus University. ("Sundberg formula" credited to Anders MartinLöf).
 ↑ Per MartinLöf. 1970. Statistika Modeller (Statistical Models): Anteckningar fran seminarier läsåret 1969–1970 (Notes from seminars in the academic year 1969–1970), with the assistance of Rolf Sundberg. Stockholm University. ("Sundberg formula")
 ↑ Dempster, A.P.; Laird, N.M.; Rubin, D.B. (1977). "Maximum Likelihood from Incomplete Data via the EM Algorithm". Journal of the Royal Statistical Society, Series B. 39 (1): 1–38. JSTOR 2984875. MR 0501537.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ "The Royal Swedish Academy of Sciences: Per MartinLöf". Retrieved 20090501.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>^{[dead link]}
References
Bird watching and missing data
 MartinLöf, P. (1961). "Mortality rate calculations on ringed birds with special reference to the Dunlin Calidris alpina". Arkiv för Zoologi (Zoology files), Kungliga Svenska Vetenskapsakademien (The Royal Swedish Academy of Sciences) Serie 2. Band 13 (21).CS1 maint: ref=harv (link)<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 George A. Barnard, "Gone Birdwatching", New Scientist, 4 December 1999, magazine issue 2215.
 Seber, G.A.F. The Estimation of Animal Abundance and Related Parameters. Caldwel, New Jersey: Blackburn Press. ISBN 1930665555.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 Royle, J. A.; R. M. Dorazio (2008). Hierarchical Modeling and Inference in Ecology. Elsevier. ISBN 1930665555.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
Probability foundations
 Per MartinLöf. "The Definition of Random Sequences." Information and Control, 9(6): 602–619, 1966.
 Li, Ming and Vitányi, Paul, An Introduction to Kolmogorov Complexity and Its Applications, Springer, 1997. Introduction chapter fulltext.
Probability on algebraic structures, following Ulf Grenander
 Grenander, Ulf. Probability on Algebraic Structures. (Dover reprint)
 MartinLöf, P. The continuity theorem on a locally compact group. Teor. Verojatnost. i Primenen. 10 1965 367—371.
 MartinLöf, Per. Probability theory on discrete semigroups. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 4 1965 78—102
 Nitis Mukhopadhyay. "A Conversation with Ulf Grenander". Statist. Sci. Volume 21, Number 3 (2006), 404–426.
Statistics foundations
 Anders MartinLöf. 1963. "Utvärdering av livslängder i subnanosekundsområdet" ("Evaluation of lifetimes in timelengths below one nanosecond"). ("Sundberg formula", according to Sundberg 1971)
 Per MartinLöf. 1966. Statistics from the point of view of statistical mechanics. Lecture notes, Mathematical Institute, Aarhus University. ("Sundberg formula" credited to Anders MartinLöf, according to Sundberg 1971)
 Per MartinLöf. 1970. Statistika Modeller (Statistical Models): Anteckningar fran seminarier läsåret 1969–1970 (Notes from seminars in the academic year 1969–1970), with the assistance of Rolf Sundberg. Stockholm University.
 MartinLöf, P. "Exact tests, confidence regions and estimates", with a discussion by A. W. F. Edwards, G. A. Barnard, D. A. Sprott, O. BarndorffNielsen, D. Basu and G. Rasch. Proceedings of Conference on Foundational Questions in Statistical Inference (Aarhus, 1973), pp. 121–138. Memoirs, No. 1, Dept. Theoret. Statist., Inst. Math., Univ. Aarhus, Aarhus, 1974.
 MartinLöf, P. Repetitive structures and the relation between canonical and microcanonical distributions in statistics and statistical mechanics. With a discussion by D. R. Cox and G. Rasch and a reply by the author. Proceedings of Conference on Foundational Questions in Statistical Inference (Aarhus, 1973), pp. 271–294. Memoirs, No. 1, Dept. Theoret. Statist., Inst. Math., Univ. Aarhus, Aarhus, 1974.
 MartinLöf, P. The notion of redundancy and its use as a quantitative measure of the deviation between a statistical hypothesis and a set of observational data. With a discussion by F. Abildgård, A. P. Dempster, D. Basu, D. R. Cox, A. W. F. Edwards, D. A. Sprott, G. A. Barnard, O. BarndorffNielsen, J. D. Kalbfleisch and G. Rasch and a reply by the author. Proceedings of Conference on Foundational Questions in Statistical Inference (Aarhus, 1973), pp. 1–42. Memoirs, No. 1, Dept. Theoret. Statist., Inst. Math., Univ. Aarhus, Aarhus, 1974.
 MartinLöf, Per The notion of redundancy and its use as a quantitative measure of the discrepancy between a statistical hypothesis and a set of observational data. Scand. J. Statist. 1 (1974), no. 1, 3—18.
 Sverdrup, Erling. "Tests without power." Scand. J. Statist. 2 (1975), no. 3, 158—160.
 MartinLöf, Per Reply to Erling Sverdrup's polemical article: ``Tests without power (Scand. J. Statist. 2 (1975), no. 3, 158–160). Scand. J. Statist. 2 (1975), no. 3, 161–165.
 Sverdrup, Erling. A rejoinder to: ``Tests without power (Scand. J. Statist. 2 (1975), 161—165) by P. MartinLöf. Scand. J. Statist. 4 (1977), no. 3, 136—138.
 MartinLöf, P. Exact tests, confidence regions and estimates. Foundations of probability and statistics. II. Synthese 36 (1977), no. 2, 195—206.
 Rolf Sundberg. 1971. Maximum likelihood theory and applications for distributions generated when observing a function of an exponential family variable. Dissertation, Institute for Mathematical Statistics, Stockholm University.
 Sundberg, Rolf. Maximum likelihood theory for incomplete data from an exponential family. Scand. J. Statist. 1 (1974), no. 2, 49—58.
 Sundberg, Rolf An iterative method for solution of the likelihood equations for incomplete data from exponential families. Comm. Statist.—Simulation Comput. B5 (1976), no. 1, 55—64.
 Sundberg, Rolf Some results about decomposable (or Markovtype) models for multidimensional contingency tables: distribution of marginals and partitioning of tests. Scand. J. Statist. 2 (1975), no. 2, 71—79.
 Höglund, Thomas. The exact estimate — a method of statistical estimation. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 29 (1974), 257—271.
 Lauritzen, Steffen L. Extremal families and systems of sufficient statistics. Lecture Notes in Statistics, 49. SpringerVerlag, New York, 1988. xvi+268 pp. ISBN 0387968725
Foundations of mathematics, logic, and computer science
 Per MartinLöf. A theory of types. Preprint, Stockholm University, 1971.
 Per MartinLöf. An intuitionistic theory of types. In G. Sambin and J. Smith, editors, TwentyFive Years of Constructive Type Theory. Oxford University Press, 1998. Reprinted version of an unpublished report from 1972.
 Per MartinLöf. An intuitionistic theory of types: Predicative part. In H. E. Rose and J. C. Shepherdson, editors, Logic Colloquium ‘73, pages 73–118. North Holland, 1975.
 Per MartinLöf. Constructive mathematics and computer programming. In Logic, Methodology and Philosophy of Science VI, 1979. Eds. Cohen, et al. NorthHolland, Amsterdam. pp. 153–175, 1982.
 Per MartinLöf. Intuitionistic type theory. (Notes by Giovanni Sambin of a series of lectures given in Padua, June 1980). Napoli, Bibliopolis, 1984.
 Per MartinLöf. Philosophical implications of type theory, Unpublished notes, 1987?
 Per MartinLöf. Substitution calculus, 1992. Notes from a lecture given in Göteborg.
 Bengt Nordström, Kent Petersson, and Jan M. Smith. Programming in MartinLöf's Type Theory. Oxford University Press, 1990. (The book is out of print, but a free version has been made available.)
 Per MartinLöf. On the Meanings of the Logical Constants and the Justifications of the Logical Laws. Nordic Journal of Philosophical Logic, 1(1): 11–60, 1996.
External links
 CS1 maint: extra punctuation
 Articles with dead external links from October 2010
 CS1 maint: ref=harv
 CS1: long volume value
 Members of the Royal Swedish Academy of Sciences
 Members of Academia Europaea
 Mathematical logicians
 Swedish logicians
 Swedish statisticians
 Contemporary philosophers
 20thcentury philosophers
 21stcentury philosophers
 Swedish philosophers
 Swedish information theorists
 Swedish mathematicians
 20thcentury mathematicians
 21stcentury mathematicians
 Stockholm University academics
 Swedish birdwatchers
 Swedish ornithologists
 1942 births
 Living people
 Tarski lecturers