John R. Myhill

Il obtient un Ph. D. de l'université Harvard sous la direction scientifique de Willard Van Orman Quine en 1949[1] 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 1987[2]^,[3]

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.

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 théorème d'isomorphisme de Myhill (en) 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 firing squad synchronization problem (en), 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 théorie constructive des ensembles (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 système de Zermelo-Fraenkel intuitionniste (en) 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 propriété de Myhill (en) 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.

• Notices d'autorité :

  • Fichier d’autorité international virtuel
  • International Standard Name Identifier
  • Système universitaire de documentation
  • Bibliothèque du Congrès
  • Gemeinsame Normdatei
  • Bibliothèque royale des Pays-Bas
  • Bibliothèque nationale d’Israël
  • Bibliothèque universitaire de Zagreb
  • WorldCat

• Portail des mathématiques