John Myhill Explained

John Myhill
Birth Date:11 August 1923
Birth Place:Birmingham, United Kingdom
Nationality:British
Fields:Mathematics
Alma Mater:Harvard University
Thesis Title:A Semantically Complete Foundation for Logic and Mathematics
Thesis Url:https://www.worldcat.org/oclc/25214080
Thesis Year:1949
Doctoral Advisor:Willard Van Orman Quine
Academic Advisors:Lynn Harold Loomis
Known For:Russell–Myhill paradox
Rice–Myhill–Shapiro theorem
intuitionistic Zermelo–Fraenkel
Myhill's property
Myhill–Nerode theorem
Garden of Eden theorem
Spouse:Akiko Kino (died 1983)

John R. Myhill Sr. (11 August 1923 – 15 February 1987)[1] was a British mathematician.

Education

Myhill received his Ph.D. from Harvard University under the supervision of Willard Van Orman Quine in 1949.[2] He was a professor at SUNY Buffalo from 1966 until his death in 1987. He also taught at several other universities during his career.

His son, also called John Myhill, is a professor of linguistics in the English department of the University of Haifa in Israel.[3]

Contributions

In the theory of formal languages, the Myhill–Nerode theorem, proven by Myhill[4] and Anil Nerode,[5] characterizes the regular languages as the languages that have only finitely many inequivalent prefixes.

In computability theory, the Rice–Myhill–Shapiro theorem,[6] more commonly known as Rice's theorem, states that, for any nontrivial property P of partial functions, it is undecidable whether a given Turing machine computes a function with property P. The Myhill isomorphism theorem is a computability-theoretic analogue of the Cantor–Bernstein–Schroeder theorem that characterizes the recursive isomorphisms of pairs of sets.

In the theory of cellular automata, Myhill is known for proving (along with E. F. Moore) the Garden of Eden theorem, which states that a cellular automaton has a configuration with no predecessor if and only if it has two different asymptotic configurations which evolve to the same configuration. He is also known for posing the firing squad synchronization problem of designing an automaton that, starting from a single non-quiescent cell, evolves to a configuration in which all cells reach the same non-quiescent state at the same time; this problem was again solved by Moore.

In constructive set theory, Myhill proposed an axiom system that avoids the axiom of choice and the law of the excluded middle, known as intuitionistic Zermelo–Fraenkel. He also developed a constructive set theory based on natural numbers, functions, and sets, rather than (as in many other foundational theories) basing it purely on sets.

The Russell–Myhill paradox or Russell–Myhill antinomy, discovered by Bertrand Russell in 1902 (and discussed in his The Principles of Mathematics, 1903)[7] [8] and rediscovered by Myhill in 1958,[9] concerns systems of logic in which logical propositions can be members of classes, and can also be about classes; for instance, a proposition P can "state the product" of a class C, meaning that proposition P asserts that all propositions contained in class C are true. In such a system, the class of propositions that state the product of classes that do not include them is paradoxical. For, if proposition P states the product of this class, an inconsistency arises regardless of whether P does or does not belong to the class it describes.[7]

In music theory, Myhill's property is a mathematical property of musical scales described by John Clough and Gerald Myerson and named by them after Myhill.

See also

Notes and References

  1. Revue philosophique de Louvain, Volume 85, 1987, p. 603.
  2. .
  3. Web site: Prof. John Myhill. english.haifa.ac.il. en-GB. 2021-04-05.
  4. Finite automata and representation of events . John Myhill . Wright Air Development Center . WADC Report TR . 57–624 . 1957 .
  5. 2033204 . 10.1090/S0002-9939-1958-0135681-9 . Anil Nerode . Proceedings of the American Mathematical Society . 9 . 4 . 541 - 544 . 1958 . free .
  6. Book: Rosenberg, Arnold L. . 9.5 The Rice–Myhill–Shapiro Theorem . 10.1007/978-0-387-09639-1_9 . New York . 165–169 . Springer . The Pillars of Computation Theory . 2009.
  7. par-russ . Russell's Paradox.
  8. russell-paradox . Russell's Paradox . Andrew David . Irvine . 2016. "The reason is that in Appendix B Russell also presents another paradox which he thinks cannot be resolved by means of the simple theory of types."
  9. "Problems Arising in the Formalization of Intensional Logic." Logique et Analyse 1 (1958): 78–83