# John Myhill

John R. Myhill (* 11. August 1923 in Birmingham; † 15. Februar 1987) war ein britischer Mathematiker, Logiker, Philosoph, Informatiker und Hochschullehrer an der State University of New York at Buffalo.

## Leben

Myhill studierte an der Universität Cambridge mit dem Bachelor (B.A.) 1944 und wurde 1949 an der Harvard University bei Willard Van Orman Quine in Philosophie promoviert (A Semantically Complete Foundation for Logic and Mathematics). Danach war er Instructor für Philosophie am Vassar College und an der Temple University und von 1951 bis 1953 Assistant Professor für Philosophie an der Yale University. 1953 wurde er Guggenheim Fellow und Assistant Professor für Philosophie an der University of California, Berkeley, an der er 1959 Professor wurde. Von 1957 bis 1959 war er am Institute for Advanced Study. Von 1960 bis 1963 war er Professor für Philosophie an der Stanford University, war danach noch ein Jahr in Princeton und zwei Jahre Gastprofessor für Mathematik an der University of Illinois. Von 1966 bis zu seinem Tod 1987 war er Professor an der SUNY in Buffalo. Trotz einer längeren Erkrankung an Lungenkrebs hielt er noch 1986 Vorlesungen.
Er war ein Jahr Gastprofessor an der University of Michigan und zwei Jahre an der University of Leeds.
Myhill war mit der mathematischen Logikerin Akiko Kino (gest. 1983) verheiratet, die Associate Professor für Mathematik an der SUNY in Buffalo war. Mit ihr hatte er eine Tochter. Außerdem hatte er drei Kinder aus erster Ehe.

## Werk

Von John Myhill stammen Beiträge zur Logik, Mathematik, Philosophie, Informatik, theoretischen Linguistik und Computermusik.
Er befasste sich viel mit rekursiven Funktionen. J. C. E. Dekker entwickelte er eine Theorie rekursiver Äquivalenztypen. Er war der Erste der tiefliegende Resultate mit dem Rekursionssatz von Kleene erzielte und er trug zur Klärung der intuitionistischen Mathematik von Brouwer bei. Myhill war auch einer der ersten Logiker, die die Bedeutung der Beiträge von Errett Bishop in der konstruktiven Mathematik erkannten und formal analysierten. In der Theorie formaler Sprachen war er beteiligt am Satz von Myhill-Nerode (1958 mit Anil Nerode), der ein notwendiges und hinreichendes Kriterium angibt wann eine formale Sprache regulär ist, und am Satz von Rice (Henry Gordon Rice 1953, manchmal auch Satz von Rice, Myhill und Shapiro genannt), nach dem jede nicht-triviale semantische Eigenschaft von Programmen unentscheidbar ist.
1955 bewies er den Isomorphiesatz von Myhill, der die Berechenbarkeit von Mengen mit denen ihrer Nummerierung vergleicht. Er ist ein Analogon des Satzes von Cantor-Bernstein-Schröder der Mengenlehre in der Theorie der Berechenbarkeit. Mit Edward F. Moore bewies er Anfang der 1960er Jahre den Garten-Eden-Satz in der Theorie zellulärer Automaten.
Er entdeckte auch ein Paradoxon von Russell (1902) wieder, das dieser in Appendix B der Principia Mathematica von 1903 veröffentlichte (manchmal Principles of Mathematics Appendix B Paradox genannt) und eine erweiterte Version des einfacheren Russellschen Antinomie ist. Es betrifft Systeme, in denen sowohl logische Objekte (Propositionen) als auch Klassen existieren und Propositionen nicht nur Elemente von Klassen sein können, sondern auch über Klassen und Klassen von Klassen Aussagen machen können. Es wird Russell-Myhill-Paradoxon genannt, da Myhill es 1958 wiederentdeckte.
Myhill konstruierte ein Axiomensystem der Mengenlehre ohne Auswahlaxiom und Satz vom ausgeschlossenen Dritten (intuitionistisches Zermelo-Fraenkel-System). Von ihm stammt auch eine konstruktive Mengenlehre die außer auf Mengen auf Zahlen und Funktionen basiert. Der Satz von Diaconescu-Goodman-Myhill (manchmal auch einzeln nach Radu Diaconescu (1975) und Noah Goodman/John Myhill benannt) der mathematischen Logik besagt, dass das Auswahlaxiom aus dem Satz vom ausgeschlossenen Dritten hergeleitet werden kann.
Er verfolgte viele Jahre ein Projekt die Ideen von Gottlob Frege so zu erweitern, dass sie eine typenfreie Grundlage der Mathematik liefern und trug zur Entwicklung der intensionalen Logik von Frege bei. Als Philosoph war er insbesondere an Frege, Georg Cantor und Gottfried Wilhelm Leibniz interessiert. Myhill war an Musiktheorie interessiert und komponierte Computermusik. Eine Eigenschaft von musikalischen Skalen in der Diatonik und Pentatonik wurde von John Clough und Gerald Myerson nach Myhill benannt.