John R. Myhill Sr. (11 de agosto de 1923 - 15 de febrero de 1987) [1] fue un matemático británico .
Myhill recibió su doctorado. de la Universidad de Harvard con Willard Van Orman Quine en 1949. [2] Fue profesor en SUNY Buffalo desde 1966 hasta su muerte en 1987. También enseñó en varias otras universidades.
Su hijo, también llamado John Myhill, es profesor de lingüística en el departamento de inglés de la Universidad de Haifa en Israel. [3]
En la teoría de los lenguajes formales , el teorema de Myhill-Nerode , demostrado por Myhill [4] y Anil Nerode , [5] caracteriza los lenguajes regulares como aquellos que tienen sólo un número finito de prefijos no equivalentes.
En la teoría de la computabilidad , el teorema de Rice-Myhill-Shapiro , [6] más comúnmente conocido como teorema de Rice, establece que, para cualquier propiedad no trivial P de funciones parciales, es indecidible determinar si una determinada máquina de Turing calcula una función con propiedad P . El teorema del isomorfismo de Myhill es un análogo teórico de la computabilidad del teorema de Cantor-Bernstein-Schroeder que caracteriza los isomorfismos recursivos de pares de conjuntos.
En la teoría de los autómatas celulares , Myhill es conocido por demostrar (junto con EF Moore ) el teorema del Jardín del Edén , afirmando que un autómata celular tiene una configuración sin predecesor si y sólo si tiene dos configuraciones asintóticas diferentes que evolucionan hacia la misma configuración. También es conocido por plantear el problema de sincronización del pelotón de fusilamiento al diseñar un autómata que, partiendo de una única celda no inactiva, evoluciona a una configuración en la que todas las células alcanzan el mismo estado no inactivo al mismo tiempo; Este problema fue nuevamente resuelto por Moore.
En teoría constructiva de conjuntos , Myhill es conocido por proponer un sistema de axiomas que evita el axioma de elección y la ley del tercero excluido , conocido como intuicionista Zermelo-Fraenkel . También desarrolló una teoría de conjuntos constructiva basada en números naturales, funciones y conjuntos, en lugar de (como en muchas otras teorías fundamentales) basarla exclusivamente en conjuntos.
La paradoja de Russell-Myhill o antinomia Russell-Myhill , descubierta por Bertrand Russell en 1902 (y analizada en su libro The Principies of Mathematics , 1903) [7] [8] y redescubierta por Myhill en 1958, [9] se refiere a sistemas de lógica en qué proposiciones lógicas pueden ser miembros de clases y también pueden ser sobre clases; por ejemplo, una proposición P puede "enunciar el producto" de una clase C , lo que significa que la proposición P afirma que todas las proposiciones contenidas en la clase C son verdaderas. En tal sistema, la clase de proposiciones que enuncian el producto de clases que no las incluyen es paradójica. Porque, si la proposición P establece el producto de esta clase, surge una inconsistencia independientemente de si P pertenece o no a la clase que describe. [7]
En teoría musical , la propiedad de Myhill es una propiedad matemática de las escalas musicales descritas por John Clough y Gerald Myerson y que llevan el nombre de Myhill.