John Myhill

John R. Myhill (born 11 August 1923, died 15 February 1987) is a British mathematician. From 1966 until his death he was a lecturer at the State University of New York. He also lectured at several other universities. His son, John Myhill, is a lecturer in linguistics at the Faculty of English at the University of Haifa. Scientific activity

Myhill obtained his doctorate in 1949 under the direction of Willard Van Orman Quine, which focused his research interests.

In my theory of formal languages, Myhill, along with Angela Nerode, is the author of Myhill-Nerode's theorem, which characterizes regular languages ​​as such that allow only a finite number of unambiguous prefixes.

In the theory of calculus, Rice's theorem, sometimes known as Rice-Myhiel-Shapiro's theorem, states that for any non-trivial property P defined for partial functions, the statement that a given Turing machine performs a given function with property P is undecidable. On the other hand, Myhill's theorem on isomorphism is in Cantor-Bernstein's theorem of calculus.

Myhill is also co-author of Moore's Theorem on Eden Gardens, which states that there is a Garden of Eden for a given cellular automaton (ie, a condition that does not arise from any other state). If there are two states that can be exchanged with each other without changing the evolution of the automaton (such states are called twin).

Myhill also posed the problem of "firing squad synchronization" of a cellular automaton that, starting with a single cell, comes to a state in which all cells are active at once. There are many solutions to this problem. The author of one of these is also Myhill.

In my constructive set theory, Myhill proposed an axiom system without the axiom of choice and the law of excluded measure. He also developed a version of constructive set theory based on the notions of natural numbers, functions and sets - much more often set theory is based solely on the notion of harvest. The Russell-Myhill Paradox, published in Appendix B to the Principles of Mathematics published in 1903 (not to be confused with the famous Principia), is a version of Russell's somewhat simpler paradox. Myhill discovered it independently in 1958 - antinomy refers to classes of sentences understood as objects independent of language and mind. As objectively existing, such sentences are elements of certain classes. But sentences can express certain properties of classes, including classes of sentences. Some of these class statements are again elements of the class they are talking about, others do not - for example, the sentence "all sentences belonging to the class of all sentences are true" is again an element of the class of all sentences, while the sentence "all sentences belonging to the empty class are real "is not an empty class element. Let's now consider the class K consisting of statements that say something about class M, to which they do not belong. K is a class of sentences and we can construct a sentence saying something about class K - then such a sentence will be at the same time class K and not.

wiki