John Myhill

John R. Myhill (ur. 11 sierpnia 1923, zm. 15 lutego 1987) – brytyjski matematyk. Od roku 1966 aż do śmierci był wykładowcą na Uniwersytecie Stanowym Nowego Jorku. Wykładał też na kilku innych uniwersytetach.

Jego syn, John Myhill, jest wykładowcą lingwistyki na wydziale anglistyki Uniwersytetu w Hajfie.

Działalność naukowa

Myhill uzyskał doktorat w roku 1949 pod kierunkiem Willarda Van Orman Quine’a^[1], co ukierunkowało jego zainteresowania badawcze.

W teorii języków formalnych Myhill wspólnie z Anilem Nerodem jest autorem twierdzenia Myhilla-Nerode’a, charakteryzujące języki regularne jako takie, które dopuszczają jedynie skończoną liczbę nierównoważnych prefiksów.

W teorii obliczalności twierdzenie Rice’a, znane czasem też jako twierdzenie Rice’a-Myhilla-Shapiro mówi, że dla dowolnej nietrywialnej własności P określonej dla funkcji częściowych stwierdzenie, czy dana maszyna Turinga realizuje daną funkcję z własnością P jest nierozstrzygalne. Z kolei twierdzenie Myhilla o izomorfizmie jest w teorii obliczalności analogiem twierdzenia Cantora-Bernsteina.

Myhill jest też współautorem – wraz z Edwardem Moore’em – dowodu twierdzenia Moore’a o ogrodach Edenu, które głosi, że dla danego automatu komórkowego istnieje ogród Edenu (tj. poprawny stan, który nie powstaje z żadnego innego stanu) wtedy i tylko wtedy, gdy istnieją dla niego dwa stany, które można wzajemnie zamieniać ze sobą nie zmieniając ewolucji automatu (takie stany nazywa się bliźniaczymi).

Myhill postawił także problem „firing squad synchronization” konstrukcji automatu komórkowego, który rozpoczynając ewolucję od pojedynczej komórki, dochodzi do stanu, w którym wszystkie komórki są aktywne w jednej chwili. Znanych jest wiele rozwiązań tego problemu. Autorem jednego z nich jest również Myhill.

W konstruktywnej teorii mnogości Myhill zaproponował system aksjomatów bez aksjomatu wyboru i prawa wyłączonego środka. Rozwinął także wersję konstruktywnej teorii mnogości opartej na pojęciach liczby naturalnej, funkcji i zbioru – znacznie częściej teorie mnogości buduje się wyłącznie w oparciu o pojęcie zbioru.

Paradoks Russella-Myhilla, zamieszczony w Appendixie B do Principles of Mathematics wydanych w 1903 roku (nie mylić ze słynnymi Principiami), jest wersją nieco prostszego paradoksu Russella. Myhill odkrył go niezależnie w roku 1958 – antynomia dotyczy klas zdań rozumianych jako obiektów niezależnych od języka i umysłu. Jako istniejące obiektywnie, zdania takie są elementami pewnych klas. Ale zdania mogą wyrażać pewne własności klas, w tym również klas zdań. Niektóre z takich zdań o klasach znów są elementami klas, o których mówią, inne nie – na przykład zdanie „wszystkie zdania należące do klasy wszystkich zdań są prawdziwe” znów jest elementem klasy wszystkich zdań, podczas gdy zdanie „wszystkie zdania należące do klasy pustej są prawdziwe” nie jest elementem klasy pustej. Rozważmy teraz klasę K złożoną ze zdań, które mówią coś o klasie M, do której one same nie należą. K jest klasą zdań i możemy zbudować zdanie mówiące coś o klasie K – wówczas zdanie takie będzie jednocześnie należało do klasy K i nie.

Przypisy