John R. Myhill Sr., who lived from 11 August 1923 to 15 February 1987, was a British mathematician and logician. He took his doctorate at Harvard University in 1949 under Willard Van Orman Quine, taught at several universities, and was a professor at SUNY Buffalo from 1966 until his death. His name is attached to results across logic and automata theory. With Anil Nerode he proved the Myhill-Nerode theorem, which characterizes the regular languages as those with only finitely many inequivalent prefixes. He shares credit for the result usually called Rice's theorem, the Myhill isomorphism theorem in computability theory, and, with E. F. Moore, the Garden of Eden theorem on cellular automata. He posed the firing squad synchronization problem, proposed a constructive set theory, and rediscovered in 1958 the paradox now called the Russell-Myhill paradox. His son, also named John Myhill, is a linguist.
Facts
Connections
In Branch
Source John Myhill (Wikipedia)
Source John Myhill (Wikipedia)
Mentored By
Source John Myhill (Wikipedia)
Principal Result
Source John Myhill (Wikipedia)
Source John Myhill (Wikipedia)
Proofs Credited
Source Myhill isomorphism theorem, Wikipedia
Source Myhill-Nerode theorem (Wikipedia)
In the Other Atlases
Nationality
Also in Geography Atlas: the nationality of this subject.
Source John Myhill (Wikipedia)Lead, nationalityQuote, Lead, nationality
John R. Myhill Sr. (11 August 1923 – 15 February 1987) was a British mathematician.
Sources
1. John Myhill (Wikipedia)
Lead, birth
John R. Myhill Sr. (11 August 1923-15 February 1987) was a British mathematician.
Education, career
He was a professor at SUNY Buffalo from 1966 until his death in 1987.
Lead, nationality
John R. Myhill Sr. (11 August 1923-15 February 1987) was a British mathematician.
In Branch: Computability Theory, Contributions, computability
In computability theory, the Rice-Myhill-Shapiro theorem, 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.
In Branch: Set Theory, Contributions, set theory
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.
Principal Result: Myhill-Nerode Theorem, Contributions, formal languages
In the theory of formal languages, the Myhill-Nerode theorem, proven by Myhill and Anil Nerode, characterizes the regular languages as the languages that have only finitely many inequivalent prefixes.
Principal Result: Myhill Isomorphism Theorem, Contributions, isomorphism theorem
The Myhill isomorphism theorem is a computability-theoretic analogue of the Cantor-Bernstein-Schroeder theorem that characterizes the recursive isomorphisms of pairs of sets.
Mentored By: Willard Van Orman Quine, Education
Myhill received his Ph.D. from Harvard University under the supervision of Willard Van Orman Quine in 1949.
View the SourceMyhill-Nerode theorem (Wikipedia)
Proofs Credited: Myhill-Nerode Theorem, Lead sentenceQuote, Proofs Credited: Myhill-Nerode Theorem, Lead sentence
The theorem is named for John Myhill and Anil Nerode, who proved it at the University of Chicago in 1957..
Myhill isomorphism theorem, Wikipedia
Proofs Credited: Myhill Isomorphism Theorem, Lead sentenceQuote, Proofs Credited: Myhill Isomorphism Theorem, Lead sentence
In computability theory the Myhill isomorphism theorem, named after John Myhill, provides a characterization for two numberings to induce the same notion of computability on a set.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.