John R. Myhill, né le à Birmingham (Angleterre) et mort le , est un mathématicien britannique.
Cursus universitaire Il obtient un Ph. D. de l'université Harvard sous la direction scientifique de Willard Van Orman Quine en 1949. Il enseigne à Vassar College de 1949 à 1950, à l'université Temple de 1950 à 1951, à l'université Yale de 1951 à 1953, à l'université de Chicago de 1953 à 1954, à université de Californie à Berkeley de 1954 à 1960, à l'université Stanford de 1960 à 1963, à l'université de l'Illinois de 1964 à 1966 et enfin à l'université d'État de New York à Buffalo depuis 1966 jusqu'à sa mort en 1987Revue philosophique de Louvain, Volume 85, n° 68, 1987, page 603
Son fils, aussi appelé John Myhill, est professeur de langue et de littérature dans le département d'anglais de l'université de Haïfa en Israël.
Contributions scientifiques En théorie des langages formels, le théorème de Myhill-Nerode, prouvé par Myhill et Nerode, caractérise les langages rationnels comme étant les langages formels qui n'ont qu'un nombre fini de préfixes inéquivalents.
En théorie de la calculabilité le théorème théorème de Rice, aussi connu sous le nom de théorème de Rice-Myhill-Shapiro, affirme que, pour toute propriété non triviale P de fonctions partielles, il est indécidable de déterminer si une machine de Turing donnée calcule une fonction ayant la propriété P. Le est l'analogue, en théorie de calculabilité, du théorème de Cantor-Bernstein qui caractérise les isomorphismes récursifs entre paires d'ensembles.
En théorie des automates cellulaires, Myhill est connu pour avoir prouvé avec E. F. Moore, le théorème du jardin d'Éden. Ce théorème énonce qu'un automate cellulaire possède une configuration sans prédécesseur si et seulement s'il possède deux configurations jumelles (on appelle jumelles deux configurations que l'on peut substituer l'une à l'autre sans changer le comportement ultérieur). C'est aussi lui qui a proposé le , appelé le problème de la ligne de fusiliers en français : il s'agit de décrire un automate qui, initialement dans un état actif dans une seule cellule, évolue vers une configuration où toutes les cellules atteignent le même état actif pour la première fois au même moment. Une première solution a été donnée par Moore. Une solution à 6 états est due à Jacques Mazoyer.
En , Myhill est connu pour avoir proposé un système d'axiomes qui évite l'utilisation de l'axiome du choix et le principe du tiers exclu, connu sous le terme de en logique intuitionniste. Il a également développé une théorie constructive des ensembles basée sur les entiers naturels, fonction et ensembles, plutôt que basée uniquement sur les ensembles.
En théorie de la musique, la est une propriété mathématique d'une gamme musicale décrite par John Clough et Gerald Myerson, à laquelle ils ont donné le nom de propriété de Myhill.
Notes et références
Liens externes
Catégorie:Naissance en août 1923 Catégorie:Naissance à Birmingham Catégorie:Décès en février 1987 Catégorie:Décès à 63 ans Catégorie:Mathématicien britannique du XXe siècle Catégorie:Étudiant de l'université Harvard Catégorie:Professeur à l'université d'État de New York à Buffalo Catégorie:Professeur à l'université Temple Catégorie:Professeur à l'université Yale Catégorie:Professeur à l'université de Chicago Catégorie:Professeur à l'université de Californie à Berkeley Catégorie:Professeur à l'université Stanford Catégorie:Professeur à l'université de l'Illinois Catégorie:Automate cellulaire Catégorie:Boursier Guggenheim