John R. Myhill Sr. (11 de agosto de 1923 15 de febrero de 1987) fue un destacado matemático británico cuya obra influyó profundamente en diversas ramas de la lógica, la teoría de la computación y la matemática teórica. A lo largo de su carrera, Myhill realizó contribuciones fundamentales que siguen siendo pilares en la informática teórica moderna.
Educación y Trayectoria Académica
Myhill obtuvo su doctorado en la Universidad de Harvard en 1949, bajo la supervisión del renombrado filósofo y lógico Willard Van Orman Quine. Desde 1966 hasta su fallecimiento en 1987, se desempeñó como profesor en la Universidad Estatal de Nueva York en Buffalo (SUNY Buffalo), aunque también impartió clases en diversas instituciones universitarias durante su trayectoria profesional.
Contribuciones Principales
Teoría de Lenguajes Formales y Computabilidad
En el ámbito de los lenguajes formales, Myhill es reconocido por el Teorema de Myhill-Nerode, desarrollado junto a Anil Nerode. Este teorema caracteriza los lenguajes regulares como aquellos que poseen un nómero finito de prefijos inequivalentes, proporcionando una herramienta crucial para el reconocimiento de patrones y el diseño de autómatas.
En la teoría de la computabilidad, contribuyó al Teorema de Rice-Myhill-Shapiro (comónmente conocido como el Teorema de Rice), el cual establece que cualquier propiedad no trivial de las funciones parciales es indecidible para una máquina de Turing. Asimismo, el Teorema de Isomorfismo de Myhill sirve como un análogo en la teoría de la computabilidad al teorema de Cantor-Bernstein-Schroeder, caracterizando los isomorfismos recursivos de pares de conjuntos.
Autómatas Celulares y Lógica
Myhill, junto con E. F. Moore, demostró el Teorema del Jardín del Edén en la teoría de los autómatas celulares. Este teorema indica que un autómata celular tiene una configuración sin predecesor si y solo si posee dos configuraciones asintóticas diferentes que evolucionan hacia la misma configuración.
Además, Myhill planteó el problema de sincronización del pelotón de fusilamiento, un desafío de diseño de autómatas donde, partiendo de una sola celda no quiescente, todas las celdas deben alcanzar el mismo estado no quiescente simultáneamente.
Teoría de Conjuntos y Paradojas
En la teoría de conjuntos constructiva, propuso un sistema axiomático conocido como Zermelo-Fraenkel intuicionista, que evita el axioma de elección y la ley del tercero excluido. También desarrolló una teoría de conjuntos constructiva basada en nûmeros naturales, funciones y conjuntos.
Finalmente, Myhill redescubrió en 1958 la paradoja de Russell-Myhill (o antinomia de Russell-Myhill), la cual trata sobre sistemas lógicos donde las proposiciones pueden ser miembros de clases y, al mismo tiempo, referirse a dichas clases, generando inconsistencias lógicas cuando una proposicion describe la clase de proposiciones que no se incluyen a sí mismas.
Módulos Musicales
En la teoría musical, existe la denominada propiedad de Myhill, una propiedad matemática de las escalas musicales descrita por John Clough y Gerald Myerson, quienes la nombraron en honor a Myhill.
