John Myhill
Encyclopedia
John R. Myhill was a mathematician
, born in 1923. He received his Ph.D. from Harvard University
under Willard Van Orman Quine
in 1949. He was professor at SUNY Buffalo
from 1966 until his death in 1987. He also taught at several other universities.
His son, also called John Myhill, is a professor of linguistics in the English department of the University of Haifa in Israel.
s, the Myhill–Nerode theorem
, proven by Myhill with Anil Nerode
, characterizes the regular language
s as the languages that have only finitely many inequivalent prefixes.
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
to determine 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, stating 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 is known for proposing 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 rediscovered by Myhill in 1958, 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.
In music theory
, Myhill's property
is a mathematical property of musical scale
s described by John Clough and Gerald Myerson and named by them after Myhill.
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
, born in 1923. He received his Ph.D. from Harvard University
Harvard University
Harvard University is a private Ivy League university located in Cambridge, Massachusetts, United States, established in 1636 by the Massachusetts legislature. Harvard is the oldest institution of higher learning in the United States and the first corporation chartered in the country...
under Willard Van Orman Quine
Willard Van Orman Quine
Willard Van Orman Quine was an American philosopher and logician in the analytic tradition...
in 1949. He was professor at SUNY Buffalo
State University of New York
The State University of New York, abbreviated SUNY , is a system of public institutions of higher education in New York, United States. It is the largest comprehensive system of universities, colleges, and community colleges in the United States, with a total enrollment of 465,000 students, plus...
from 1966 until his death in 1987. He also taught at several other universities.
His son, also called John Myhill, is a professor of linguistics in the English department of the University of Haifa in Israel.
Research results
In the theory of formal languageFormal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
s, the Myhill–Nerode theorem
Myhill–Nerode theorem
In the theory of formal languages, the Myhill–Nerode theorem provides a necessary and sufficient condition for a language to be regular. The theorem is named for John Myhill and Anil Nerode, who proved it at the University of Chicago in 1958 ....
, proven by Myhill with Anil Nerode
Anil Nerode
Anil Nerode is a U.S. mathematician, born in 1932. He received his undergraduate education and a Ph.D. in mathematics from the University of Chicago, the latter under the directions of Saunders Mac Lane. He enrolled in the Hutchins College at the University of Chicago in 1947 at the age of 15, and...
, characterizes the regular language
Regular language
In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....
s as the languages that have only finitely many inequivalent prefixes.
In computability theory
Computability theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
, 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
Undecidable
Undecidable may refer to:In mathematics and logic* Undecidable problem - a decision problem which no algorithm can decide* "Undecidable" is sometimes used as a synonym of "independent", where a formula in mathematical logic is independent of a logical theory if neither that formula nor its negation...
to determine whether a given Turing machine computes a function with property P. The Myhill isomorphism theorem
Myhill isomorphism theorem
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.- Myhill isomorphism theorem :...
is a computability-theoretic analogue of the Cantor–Bernstein–Schroeder theorem
Cantor–Bernstein–Schroeder theorem
In set theory, the Cantor–Bernstein–Schroeder theorem, named after Georg Cantor, Felix Bernstein, and Ernst Schröder, states that, if there exist injective functions and between the sets A and B, then there exists a bijective function...
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
Edward F. Moore
Edward Forrest Moore was an American professor of mathematics and computer science, the inventor of the Moore finite state machine, and an early pioneer of artificial life....
) the Garden of Eden theorem, stating 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
Firing squad synchronization problem
The firing squad synchronization problem is a problem in computer science and cellular automata in which the goal is to design a cellular automaton that, starting with a single active cell, eventually reaches a state in which all cells are simultaneously active...
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
Constructive set theory
Constructive set theory is an approach to mathematical constructivism following the program of axiomatic set theory. That is, it uses the usual first-order language of classical set theory, and although of course the logic is constructive, there is no explicit use of constructive types...
, Myhill is known for proposing 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
Bertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...
in 1902 and rediscovered by Myhill in 1958, 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.
In music theory
Music theory
Music theory is the study of how music works. It examines the language and notation of music. It seeks to identify patterns and structures in composers' techniques across or within genres, styles, or historical periods...
, Myhill's property
Myhill's property
In diatonic set theory Myhill's property is the quality of musical scales or collections with exactly two specific intervals for every generic interval, and thus also have the properties of maximal evenness, cardinality equals variety, structure implies multiplicity, and be a well formed generated...
is a mathematical property of musical scale
Musical scale
In music, a scale is a sequence of musical notes in ascending and descending order. Most commonly, especially in the context of the common practice period, the notes of a scale will belong to a single key, thus providing material for or being used to conveniently represent part or all of a musical...
s described by John Clough and Gerald Myerson and named by them after Myhill.