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 en la Universidad de Harvard bajo la supervisión de 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 durante su carrera.
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 lenguajes formales , el teorema de Myhill-Nerode , demostrado por Myhill [4] y Anil Nerode [5] , caracteriza a los lenguajes regulares como los lenguajes que tienen sólo un número finito de prefijos no equivalentes.
En teoría de computabilidad , el teorema de Rice-Myhill-Shapiro , [6] más conocido como teorema de Rice, establece que, para cualquier propiedad no trivial P de funciones parciales, es indecidible si una máquina de Turing dada calcula una función con la propiedad P. El teorema de isomorfismo de Myhill es un análogo teórico de computabilidad del teorema de Cantor-Bernstein-Schroeder que caracteriza los isomorfismos recursivos de pares de conjuntos.
En la teoría de autómatas celulares , Myhill es conocido por demostrar (junto con EF Moore ) el teorema del Jardín del Edén , que establece que un autómata celular tiene una configuración sin predecesor si y solo si tiene dos configuraciones asintóticas diferentes que evolucionan a la misma configuración. También es conocido por plantear el problema de sincronización del pelotón de fusilamiento de diseñar un autómata que, partiendo de una única célula no quiescente, evoluciona a una configuración en la que todas las células alcanzan el mismo estado no quiescente al mismo tiempo; este problema fue resuelto nuevamente por Moore.
En la teoría de conjuntos constructivos , Myhill propuso un sistema axiomático que evita el axioma de elección y la ley del tercero excluido , conocido como teoría intuicionista de Zermelo-Fraenkel . También desarrolló una teoría de conjuntos constructivos basada en números naturales, funciones y conjuntos, en lugar de basarla puramente en conjuntos (como en muchas otras teorías fundamentales).
La paradoja de Russell-Myhill o antinomia de Russell-Myhill , descubierta por Bertrand Russell en 1902 (y analizada en su obra Principios de las matemáticas , 1903) [7] [8] y redescubierta por Myhill en 1958, [9] se refiere a sistemas de lógica en los que las proposiciones lógicas pueden ser miembros de clases y también pueden referirse a 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 un sistema de este tipo, la clase de proposiciones que enuncia el producto de clases que no las incluyen es paradójica. Porque, si la proposición P enuncia 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 descrita por John Clough y Gerald Myerson y nombrada por ellos en honor a Myhill.