Джон Р. Майхилл: Жизнь и вклад в математику

Введение

Джон Р. Майхилл старший (11 августа 1923 – 15 февраля 1987) был британским математиком.

Образование

Майхилл получил степень доктора философии в Гарвардском университете под руководством Уилларда Ван Ормана Куина в 1949 году. Он был профессором в SUNY Buffalo с 1966 года до своей смерти в 1987 году. Он также преподавал в ряде других университетов. Его сын, также по имени Джон Майхилл, является профессором лингвистики в отделении английского языка Хайфского университета в Израиле.

Вклад

В теории формальных языков теорема Майхилла — Нерода, доказанная Майхиллом и Анилом Неродом, характеризует регулярные языки как языки, имеющие лишь конечное число неэквивалентных префиксов. В теории вычислимости теорема Райса — Михилла — Шапиро, более известная как теорема Райса, утверждает, что для любого нетривиального свойства P частичных функций невозможно определить, вычисляет ли заданная машина Тьюринга функцию, обладающую свойством P. Теорема изоморфизма Майхилла является теоретико-вычислительным аналогом теоремы Кантора — Бернштейна — Шрёдера, характеризующей рекурсивные изоморфизмы пар множеств. В теории клеточных автоматов Майхилл известен доказательством (совместно с Э. Ф. Муром) теоремы о саде Эдема, утверждающей, что клеточный автомат имеет конфигурацию, не имеющую предшественника, тогда и только тогда, когда у него есть две различные асимптотические конфигурации, эволюционирующие в одну и ту же конфигурацию. Он также известен постановкой задачи синхронизации расстрельного отряда, заключающейся в проектировании автомата, который, начиная с одной непустой ячейки, переходит в конфигурацию, в которой все ячейки одновременно достигают одного и того же непустого состояния; эту задачу вновь решил Мур. В конструктивной теории множеств Майхилл известен предложением аксиоматической системы, избегающей аксиомы выбора и закона исключённого третьего, известной как интуиционистский Зермело — Френкель. Он также разработал конструктивную теорию множеств, основанную на натуральных числах, функциях и множествах, а не (как во многих других фундаментальных теориях) исключительно на множествах. Парадокс Рассела — Майхилла, или антиномия Рассела — Майхилла, открытый Бертраном Расселом в 1902 году (и обсуждаемый в его «Принципах математики» 1903 года) и вновь открытый Майхиллом в 1958 году, касается систем логики, в которых логические высказывания могут быть элементами классов и одновременно относиться к классам; например, высказывание P может «определять произведение» класса C, то есть высказывание P утверждает, что все высказывания, содержащиеся в классе C, истинны. В такой системе класс высказываний, определяющих произведение классов, которые их не включают, является парадоксальным. Ведь если высказывание P определяет произведение этого класса, возникает противоречие, независимо от того, принадлежит ли P описываемому классу или нет. В теории музыки свойство Майхилла — это математическое свойство музыкальных ладов, описанное Джоном Клаугом и Джеральдом Майерсоном и названное ими в честь Майхилла.

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. 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 discussed in his The Principles of Mathematics, 1903) 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 scales described by John Clough and Gerald Myerson and named by them after Myhill.