John Myhill

John Myhill
Född	( 1923-08-11 ) 11 augusti 1923 Birmingham , Storbritannien
dog	15 februari 1987 (1987-02-15) (63 år)
Nationalitet	brittisk
Alma mater	Harvard Universitet
Känd för	Russell–Myhill paradox Ris–Myhill–Shapiros sats intuitionistisk Zermelo–Fraenkel Myhills egendom Myhill–Nerodes sats Edens trädgårdssats
Make	Akiko Kino (död 1983)
Vetenskaplig karriär
Fält	Matematik
Avhandling	A Semanically Complete Foundation for Logic and Mathematics (1949)
Doktorand rådgivare	Willard Van Orman Quine
Andra akademiska rådgivare	Lynn Harold Loomis

John R. Myhill Sr. (11 augusti 1923 – 15 februari 1987) var en brittisk matematiker .

Utbildning

Myhill fick sin Ph.D. från Harvard University under Willard Van Orman Quine 1949. Han var professor vid SUNY Buffalo från 1966 till sin död 1987. Han undervisade också vid flera andra universitet.

Hans son, även kallad John Myhill, är professor i lingvistik vid engelska avdelningen vid universitetet i Haifa i Israel.

Bidrag

I teorin om formella språk karakteriserar Myhill –Nerode-satsen , bevisad av Myhill och Anil Nerode , de reguljära språken som de språk som bara har ändligt många olikvärdiga prefix.

I beräkningsbarhetsteorin säger Rice -Myhill-Shapiro-satsen , mer allmänt känd som Rice's sats, att det för varje icke-trivial egenskap P för partiella funktioner är obestämbart att avgöra om en given Turing-maskin beräknar en funktion med egenskapen P . Myhill isomorfism-satsen är en beräkningsteoretisk analog till Cantor-Bernstein-Schroeder-satsen som kännetecknar de rekursiva isomorfismerna av par av mängder.

I teorin om cellulära automater är Myhill känd för att bevisa (tillsammans med EF Moore ) Edens trädgårdssats, som säger att en cellulär automat har en konfiguration utan någon föregångare om och bara om den har två olika asymptotiska konfigurationer som utvecklas till samma konfiguration. Han är också känd för att ha ställt till med synkroniseringsproblemet för skjutningsgruppen att designa en automat som, med utgångspunkt från en enda icke-vilande cell, utvecklas till en konfiguration där alla celler når samma icke-vilande tillstånd samtidigt; detta problem löstes återigen av Moore.

I konstruktiv mängdteori är Myhill känd för att föreslå ett axiomsystem som undviker valets axiom och lagen om den uteslutna mitten , känt som intuitionistiska Zermelo–Fraenkel . Han utvecklade också en konstruktiv mängdteori baserad på naturliga tal, funktioner och mängder, snarare än (som i många andra grundläggande teorier) baserat den enbart på mängder.

Russell -Myhill-paradoxen eller Russell-Myhill-antinomin , upptäckt av Bertrand Russell 1902 (och diskuterad i hans The Principles of Mathematics , 1903) och återupptäckt av Myhill 1958, rör logiska system där logiska satser kan vara medlemmar i klasser, och kan också handla om klasser; till exempel kan en proposition P "ange produkten" av en klass C , vilket betyder att proposition P hävdar att alla propositioner som finns i klass C är sanna. I ett sådant system är klassen av propositioner som anger produkten av klasser som inte inkluderar dem paradoxal. För, om sats P anger produkten av denna klass, uppstår en inkonsekvens oavsett om P tillhör eller inte tillhör den klass den beskriver.

Inom musikteorin är Myhills egenskap en matematisk egenskap hos musikskalor som beskrivs av John Clough och Gerald Myerson och uppkallad av dem efter Myhill.

Se även

• Diaconescu–Goodman–Myhill-satsen