Джон Р. Майхилл-старший (11 августа 1923 – 15 февраля 1987) [1] был британским математиком .
Майхилл получил докторскую степень в Гарвардском университете под руководством Уилларда Ван Ормана Куайна в 1949 году. [2] Он был профессором в Университете штата Нью-Йорк в Буффало с 1966 года до своей смерти в 1987 году. За время своей карьеры он также преподавал в нескольких других университетах.
Его сын, которого также зовут Джон Майхилл, является профессором лингвистики на кафедре английского языка Хайфского университета в Израиле. [3]
В теории формальных языков теорема Майхилла –Нерода , доказанная Майхиллом [4] и Анилом Неродом [5] , характеризует регулярные языки как языки, имеющие лишь конечное число неэквивалентных префиксов.
В теории вычислимости теорема Райса–Майхилла–Шапиро [6], более известная как теорема Райса, утверждает, что для любого нетривиального свойства P частичных функций невозможно решить , вычисляет ли данная машина Тьюринга функцию со свойством P. Теорема Майхилла об изоморфизме является аналогом теоремы Кантора–Бернштейна–Шредера в теории вычислимости , которая характеризует рекурсивные изоморфизмы пар множеств.
В теории клеточных автоматов Майхилл известен тем, что доказал (вместе с Э. Ф. Муром ) теорему о Эдемском саду , которая гласит, что клеточный автомат имеет конфигурацию без предшественника тогда и только тогда, когда у него есть две различные асимптотические конфигурации, которые эволюционируют к одной и той же конфигурации. Он также известен тем, что поставил задачу синхронизации расстрельного отряда , заключающуюся в проектировании автомата, который, начиная с одной неподвижной клетки, эволюционирует к конфигурации, в которой все клетки достигают одного и того же неподвижного состояния в одно и то же время; эта задача была снова решена Муром.
В конструктивной теории множеств Майхилл предложил систему аксиом, которая избегает аксиомы выбора и закона исключенного третьего , известную как интуиционистская теория Цермело–Френкеля . Он также разработал конструктивную теорию множеств, основанную на натуральных числах, функциях и множествах, а не (как во многих других фундаментальных теориях) основывающуюся исключительно на множествах.
Парадокс Рассела –Майхилла или антиномия Рассела–Майхилла , открытая Бертраном Расселом в 1902 году (и обсуждаемая в его «Принципах математики» , 1903) [7] [8] и вновь открытая Майхиллом в 1958 году [9] , касается систем логики, в которых логические предложения могут быть членами классов, а также могут быть о классах; например, предложение P может «утверждать произведение» класса C , что означает, что предложение P утверждает, что все предложения, содержащиеся в классе C, истинны. В такой системе класс предложений, которые утверждают произведение классов, которые их не включают, является парадоксальным. Поскольку, если предложение P утверждает произведение этого класса, возникает несоответствие независимо от того, принадлежит ли P классу, который оно описывает, или нет. [7]
В теории музыки свойство Майхилла — математическое свойство музыкальных гамм, описанное Джоном Клафом и Джеральдом Майерсоном и названное ими в честь Майхилла.