(s. St. Louis, Missouri, 8. joulukuuta 1919; d.Berkeley, Kalifornia, 30. heinäkuuta 1985), matematiikka, matemaattinen logiikka, lukuteoria, päätösongelmat, määriteltävyys.
Robinsonin matemaattisessa työssä on voimaa ja charmia. Hän taklasi vaikeita ongelmia ja pyrki tyylikkäisiin ratkaisuihin. Hänen elämäänsä ja työtään ei voi oikein nähdä panematta merkille, että naisena miesvaltaisella alalla hän oli melkoinen tienraivaaja. Hänen métier oli rajapinta kahden haaran matematiikan, logiikan ja teorian numerot, tavallisesti ajatellut on vähän tekemistä keskenään. Hän on erityisen tunnettu hänen panoksensa ratkaisun kymmenes ongelma on kuuluisa luettelo kaksikymmentäkolme ehdottama matemaatikko David Hilbert vuonna 1900. Hänet valittiin National Academy of Sciences ja myös puheenjohtajavaltion American Mathematical Society, molemmissa tapauksissa ensimmäinen naispuolinen matemaatikko on niin kunnia, ja oli myös vastaanottaja, joka MacArthur Fellowship.
nuorena syntynyt Julia Bowman koki nuorena kaksi onnettomuutta. Hän oli vain kaksi, kun hänen äitinsä kuoli, jättäen isänsä selviytymään Julia ja hänen vanhempi sisarensa Constance. Hänen mentyään uudelleen naimisiin perhe muutti länteen, lopulta San Diegoon, jossa hänen sisarpuolensa Billie syntyi. Kun Julia oli yhdeksän hän tehtiin tuhoisa sairaus: tulirokko seurasi reumaattinen kuume. Hän oli kaksi vuotta poissa koulusta ja sai erittäin vakavia vaurioita sydämeensä. Akateemisesti hän menestyi ja pian muodostavat hänen menetetty maahan. Lukiossa hän oli ainoa tyttö, joka otti edistyneen tieteen ja matematiikan kursseja ja valmistui useita arvosanoin. Vuonna 1936 hän tuli San Diego State College, pääaineena matematiikka. Etsien laajempia näkymiä, hän siirtyi Kalifornian yliopistoon Berkeleyyn seniorivuodeksi. Niistä viisi matematiikan kursseja hän otti, että vuosi oli yksi teorian numerot opettanut Raphael Robinson. Hänen kykynsä teki häneen vaikutuksen, ja hän sai hänet jatkamaan opintojaan jatko-opiskelijana. Raphael oli matemaatikko laaja etuja ja tietoa ja ihanteellinen mentori. Pian heidän suhteensa muuttui kuitenkin henkilökohtaisemmaksi ja he menivät naimisiin joulukuussa 1941. Heidän toiveensa perheen perustamisesta kariutuivat, kun Julia sai keskenmenon ja lääkäri varoitti häntä siitä, että hänen vakavasti vaurioituneen sydämensä vuoksi raskaus olisi erittäin vaarallinen. Hänen käsityksensä oli, että hän todennäköisesti kuolisi ennen neljänkymmenen ikävuoden täyttymistä. Kun pyritään auttamaan Julia voittaa syvä masennus, johon hän oli flung, Raphael kannusti häntä etsimään lohtua matematiikkaan.
matemaattinen tausta 1930-luvulla oli tapahtunut kumouksellista kehitystä antiikin logiikan alalla, joka muuttui radikaalisti perinteisestä Aristoteleen alullepanemasta alasta. Kurt Gödelin kuuluisa epätäydellisyyslause oli viitannut logiikan muodollisten järjestelmien luontaisiin rajoituksiin matemaattisen käytännön kapseloinnissa. Työn Alonzo Church, Alan Turing, ja Emil Post sekä Gödel itse oli osoittanut, että kysymys olemassaolosta algorithmic ratkaisuja erityisiä matemaattisia ongelmia voitaisiin antaa tarkka muotoilu. Tämä avasi mahdollisuuden, että tietyissä tapauksissa tällaisia algoritmisia ratkaisuja ei välttämättä ole olemassa, ja jopa että tällaisissa tapauksissa tämä voidaan todistaa. Alfred Tarski oli selittänyt, kuinka määritellä semanttiset käsitteet totuudesta ja muodollisten kielten määritettävyydestä. Nämä olivat kehitystä, joka tarjosi yhteydessä Julia Robinson ’ s tutkimus.
mikä tahansa matematiikan haara käyttää symboleita edustamaan niitä tiettyjä operaatioita ja suhteita, jotka ovat kyseisen subjektin kannalta olennaisia. Näiden symbolien lisäksi moderni matemaattinen logiikka käyttää erikoismerkkejä
yhdessä tutun = merkin kanssa. Yksi puhuu näistä symboleista yhdessä niiden kanssa, jotka vastaavat tiettyä haaraa matematiikan kuin muodostavat kielen. Julia Robinson työ oli suurelta osin yhteydessä kielen aritmeettinen, joka käyttää kaksi symbolia + ja × pysyvän lisäksi ja kertolasku, vastaavasti, sekä symboleja 0 ja 1. Aakkosten kirjaimia käytetään muuttujina, ja aritmeettisessa kielessä niiden ymmärretään yleensä vaihtelevan tutuilla luonnollisilla luvuilla 0,1,2…. joten esimerkiksi ”lause”
ilmaisee todellisen väitteen, että lisäämällä kaksi paritonta lukua saadaan parillinen luku. Kaava (u) (x = u+u+1)> itse määrittelee parittomien lukujen joukon, eli jos x korvataan tietyllä luonnollisella luvulla, tuloksena oleva lause on tosi, jos ja vain jos kyseinen luku on pariton. Kysymykset määriteltävyys ja olemassaolo algoritmit olivat perustavanlaatuisia Robinson työtä.
luonnollisten lukujen joukkoa S kutsutaan laskennalliseksi (tai rekursiiviseksi), jos on olemassa algoritmi, joka voi määrittää tietylle luonnolliselle luvulle n kuuluuko n S: ään vai ei.luonnollisten lukujen joukkoa kutsutaan luetteloitavaksi (Julia Robinsonin suosima termi) tai rekursiivisesti lueteltavaksi, jos on olemassa algoritmi, jolla systemaattisesti tehdään luettelo S: n jäsenistä. kaikki unsolvability-tulokset voidaan ajatella keskeisen lauseen seurauksina: on olemassa luetteloitava joukko, joka ei ole laskettavissa. Nämä asiat olivat myös hyvin tärkeitä Robinsonin työssä.
Julia Robinsonin väitöskirja kahdennenkymmenennen vuosisadan suuriin loogikkoihin kuuluvan karismaattisen Alfred Tarskin johtamassa seminaarissa Robinson löysi métierinsä. Tarski oli jättänyt hänen kotimaassaan Puolassa elokuussa 1939, mitä oli ollut lyhyt matka osallistua konferenssiin, Yhdysvallat, juuri ennen Saksan hyökkäys Puola nopeutti toisen maailmansodan. Tarski aiheutti useita ratkaisemattomia kysymyksiä määriteltävyyden kielellä aritmeettinen, johon Robinson oli houkutellut. 1940-luvulle tultaessa oli hyvin tiedossa, ettei ole olemassa algoritmia, jolla voitaisiin määrittää, onko aritmetiikan kielellä annettu lause, jossa muuttujat vaihtelevat luonnollisten lukujen yli, tosi. Kuten eräs sanoo, Tämä on algoritmisesti ratkaisematon ongelma. Tarski halusi tietää, onko sama pätee, kun tällä samalla kielellä muuttujien sallitaan vaihdella kaikkien rationaalilukujen sijaan vain luonnolliset luvut. (Rationaaliluvut ovat niitä, jotka lausutaan murtolukuina m/n tai-m / n, missä m on luonnollinen luku ja n ei-nolla luonnollinen luku.) Oli kehitetty tekniikoita yhden tällaisen” päätösongelman ””vähentämiseksi” toiseen. Tässä tapauksessa yksi osoittaisi, että jos oli algoritmi testaamiseen totuus lause kielen aritmeettinen kanssa muuttujia rajoitettu vaihdella yli järkevä numerot, tällainen algoritmi voitaisiin käyttää toimittamaan algoritmi tehdä sama, kun muuttujat vaihtelevat yli luonnolliset luvut. Joten, koska viimeksi mainitulle ei ole olemassa tällaista algoritmia, siitä seuraisi, ettei edellistä voisi olla olemassa.
Robinsonin väitöskirjan päätulos oli aritmeettisessa kielenkäytössä eksplisiittinen kaava, jossa muuttujien on pakko vaihdella rationaalilukujen suhteen, joka määrittelee tarkasti kokonaislukujen joukon (eli luonnollisten lukujen joukon ja niiden negatiivit). Tästä seurasi, että aritmeettisen lauseen totuuden määrittämisen ongelma pysyy ratkaisemattomana silloinkin, kun muuttujat vaihtelevat rationaalilukujen yli. Myös muita epäolennaisia tuloksia seurasi. Robinson lähestymistapa oli monimutkainen, tyylikäs, ja nerokas käyttäen joitakin melko syviä ideoita lukuteoria.
elegantit luonnehdinnat Robinson pyrki aina eleganssiin ja yksinkertaisuuteen matemaattisessa työssään. Yksi hänen varhaisen papereita osoitti, miten luonnehtia, erityisen yksinkertaisella tavalla, algorithmically computable toimintoja (kutsutaan myös rekursiiviset toiminnot), jotka kartoittavat luonnolliset luvut itseensä. Hänen kaunis Luonnehdinta liittyy kaksi alkuperäistä tehtäviä ja kolme toimintaa saada uusia tehtäviä annetuista tehtävistä. Yksi alkufunktioista on vain seuraajafunktio S (x)= x+1. Toinen, jota Robinson kutsuu E: ksi, määritellään annetun luvun ja suurimman täydellisen neliön erotuksena, joka ei ylitä sitä. (Näin E(19) = 19 – 16 = 3 ja E(25) = 25-25 = 0.) Kolme operaatiota ovat seuraavat: (1) annetuista funktioista F ja G saavat funktion H(x)=F(G (x)); (2) annetuista funktioista F ja G saavat funktion H(x)=F(x) + G (x); ja(3) annetusta funktiosta F, jonka arvot sisältävät kaikki luonnolliset luvut, saadaan funktio H, jossa H(x) on pienin luku t, jolle F (T)=x.
on todella merkillistä, että kaikki laskennalliset funktiot (luonnollisista luvuista luonnollisiin lukuihin) voidaan saada aloittamalla kahdesta alkufunktiosta ja soveltamalla näitä kolmea operaatiota yhä uudelleen.
paljon myöhemmin Robinson osoitti samaa eleganssia ja verve löytää uusia luonnehdintoja verkkotunnuksen kaukana computable. Luetteloitavan joukon k olemassaolo, joka ei ole laskettavissa, on jo mainittu. K: n jäsenyyden määrittämiseen ei siis ole algoritmia. Tarkastelemalla joukkoja, jotka voidaan luetella algoritmeilla, joilla on pääsy tällaisten joukkojen jäsenyystietoihin (vertauskuvallisesti ”oraakkelin” kautta), joukkoon voidaan tuoda lisää joukkoja, ja tämä prosessi voidaan iteroida. Sallimalla tämän iteraation tapahtua minkä tahansa äärellisen määrän kertoja, saadut joukot osoittautuvat täsmälleen sellaisiksi, joita kutsutaan aritmeettisiksi eli aritmeettisiksi joukoiksi, joiden muuttujat vaihtelevat luonnollisten lukujen yli. Tähän ei kuitenkaan tarvitse pysähtyä. Voidaan määritellä ei-aritmeettinen joukko, ja sitten käyttää, että ”oraakkeli” voi luetella vielä lisää joukkoja. On olemassa luonnollinen paikka, jossa tämä prosessi päättyy, ja näin saatuja luonnollisten lukujen joukkoja kutsutaan hyperaritmeettisiksi. Se oli tämä harvinainen valtakunta, jolle Robinson tarjosi yksinkertaisen ja suoran luonnehdinnan.
eksistentiaalinen Määriteltävyys ja Hilbertin kymmenes ongelma teos, josta Julia Robinson muistetaan parhaiten, sai alkunsa ilmeisesti yksinkertaisesta Alfred Tarskin aiheuttamasta ongelmasta. Tarski halusi tietää, mitkä joukko luonnollisia lukuja ovat määriteltävissä kaavoja kielen aritmeettinen, jos symbolit ja jätetään pois. Hän kutsui tällaisia asetetaan eksistentiaalisesti määriteltävissä ja ehdotti ongelma todistaa, että asetettu {1,2,4,8,16,….} potensseista 2 ei ole eksistentiaalisesti määriteltävissä. Tämä oli juuri sellainen ongelma, että Robinson piti. Eksistentiaalisen määriteltävyyden käsitteen voidaan helposti nähdä liittyvän läheisesti lukuteoreetikkojen tutkimiin ongelmiin, niin sanottuihin Diofanttisiin ongelmiin. Näillä on tyypillisesti tekemistä polynomiyhtälön p (a, x, y, z, u, v, w,….) = 0 kanssa kokonaisluku kertoimia,joissa a on parametri ja x,y,z,u,v, w,…. ovat ” tuntemattomia.”(Muista, että tällainen polynomi on vain termien summa, kuten 5a3x2v5 ja-7a4x3z6.) Erityisesti Diophantine yhtälöt tällaista, määrä teoreetikot yrittävät määrittää, jolle luonnollinen luku arvot parametrin a, yhtälö on luonnollinen luku ratkaisuja tuntemattomia. Nyt yksinkertaisilla standardimenetelmillä on helppo nähdä, että joukko luonnollisia lukuja S On eksistentiaalisesti määriteltävissä, jos ja vain jos on olemassa polynomiyhtälö tällainen sellainen, että S on täsmälleen sen parametrin arvojoukko, jolle yhtälö on luonnollinen luku ratkaisuja. Tästä syystä eksistentiaalisesti määriteltäviä joukkoja kutsutaan myös Diofantiiniksi, ja tämä termi on omaksuttu myöhemmässä kirjallisuudessa.
koska Tarskin konjektuuria ei ole onnistuttu todistamaan, että 2: n valtuuksien joukko ei ole Diophantine, Robinson alkoi harkita mahdollisuutta, että Tarskin arvaus saattoi olla väärä. Edistyäkseen hänen oli otaksuttava tietty hypoteesi, jota ei tuolloin todistettu, jota alettiin kutsua nimellä J. R.; karkeasti ottaen J. R. todetaan,että on olemassa Diophantine yhtälö kaksi parametria a,b kanssa omaisuutta, että paria (a, b), jolle yhtälö on ratkaisut ovat sellaisia, että b kasvaa eksponentiaalisesti kuin funktio a. olettaen J. R. ja suorittaa monimutkainen ja nerokas analyysi, hän osoitti paitsi, että valtuudet 2 ovat Diophantine, mutta myös, että joukko alkuluvut sekä monet muut ovat myös. On helppo nähdä, että kaikki Diofanttiset joukot ovat luetteloitavissa, mutta nyt hän pohti, voisiko converse olla totta, voivatko kaikki luetteloitavat joukot olla Diofanttisia. Hän tiesi, että sillä olisi syvällisiä seurauksia.
vuonna 1900, tervehtiäkseen uutta vuosisataa, suuri matemaatikko David Hilbert ehdotti haasteeksi kahdenkymmenenkolmen ongelman luetteloa. Kymmenes hänen luettelo oli tarjota algoritmi määrittää, onko tietyn polynomin Diophantine yhtälö on ratkaisuja. Jos todellakin kaikki luetteloitavissa asetetaan olivat Diophantine, hän tajusi, niin erityisesti olisi ei-computable Diophantine asettaa, mikä tarkoittaa, että ei voisi olla mitään algoritmia, kuten Hilbert oli pyytänyt. Tämä olisi kielteinen ratkaisu Hilbertin kymmenes ongelma.
kesällä 1959 Robinson sai postissa ennakkopainoksen Martin Davisin ja Hilary Putnamin tekemästä tutkielmasta. Paperi sisälsi todiste siitä, että, olettaen J. R., kaikki luetteloitavat sarjat ovat todellakin Diophantine. Todisteissa oli kuitenkin tärkeä aukko. Se käytti sitä, että on olemassa mielivaltaisen pitkiä alkulukujonoja, joilla on erityinen ominaisuus, että peräkkäisten jaksojen ero on vakio. Vaikka tämä on totta, vuonna 1959 se oli pelkkä hypoteesi; se todistettiin vasta vuonna 2004. Robinson tunsi Davisin ja Putnamin aikaisemman työn erittäin hyvin ja ilmaisi olevansa yllättynyt ja mielissään heidän saavutuksestaan. Hyvin lyhyessä järjestyksessä hän osoitti, miten ilman ylimääräistä hypoteesia alkuluvuista, ja löysi jopa lyhyen version todistuksesta. Niin, saada odotettu negatiivinen ratkaisu Hilbert ’ s kymmenes ongelma, se vain jäi todistamaan J. R.
tämä oli suoritettu tammikuussa 1970, jonka kaksikymmentäkaksi-vuotias Yuri Matiyasevich käyttäen kuuluisa Fibonacci sekvenssi 1,1,2,3,5,8,13,…. Hän löysi Diophantine yhtälö kaksi parametria a, b, että hän pystyi todistamaan on ratkaisuja vain siinä tapauksessa b on Fibonacci numero, 2a-th paikka tässä järjestyksessä. Koska Fibonacci numerot eivät kasva eksponentiaalisesti, tämä ei muodostavat todiste J. R. Robinson oli iloinen Matiyasevich n nerokas todiste ja matkusti Leningrad, jossa heidän perheensä tapasivat. Heidän yhteistyönsä oli hedelmällistä, yhdessä he pystyivät osoittamaan, että Hilbert kymmenes ongelma on ratkaisematon jopa yhtälöt 13 tuntemattomia. (Myöhemmin Matijasevitš onnistui vähentämään lukumäärää 9.)
Coda Kalifornian yliopistossa voimassa olleet” nepotismin ” säännöt olisivat tehneet Robinsonin säännöllisen tiedekuntanimityksen mahdottomaksi niin kauan kuin hänen miehensä oli tiedekunnassa. Joka tapauksessa voi olla, että hänen terveysongelmansa olisivat estäneet kokopäivätyön. Hän ei joskus opettaa tietenkin kuin adjunct, ja hän palveli de facto neuvonantajana kaksi erinomaista väitöskirjaa opiskelijat, Leonard Adleman ja Kenneth Manders. Robinson uhmasi lääkärin ennustusta, jonka mukaan hän ei eläisi nelikymppiseksi, mutta nelikymppisenä hänen vaurioitunut sydämensä oli vienyt hänet lähes invalidisoituun asemaan. Hänet pelastettiin kirurgisella toimenpiteellä, joka oli vasta äskettäin tullut saataville ja joka paransi suuresti hänen tilannettaan ja mahdollisti sen, että hän saattoi elää aktiivista elämää vielä kaksikymmentäviisi vuotta.
hänen erinomaisesta työstään sai tunnustusta hänen valintansa vuonna 1975 Kansalliseen tiedeakatemiaan, joka oli ensimmäinen nainen, joka valittiin matematiikan osastoon. Samana vuonna hän oli vihdoin tarjotaan professorin nimityksen University of California at Berkeley.
hänen pyynnöstään kyseessä oli neljännesvälierä. MacArthur Fellowship tuli vuonna 1983. Hänet valittiin presidentiksi American Mathematical Society 1983-1984, ensimmäinen nainen pitää tätä virkaa. Traagista kyllä, hän ei päässyt kautensa loppuun. Hänen todettiin sairastavan leukemiaa kesällä 1984. Julia Robinson kuoli sairauteen 30.heinäkuuta 1985.
bibliografia
Robinsonin teokset
” Definability and Decision Problems in Arithmetic.”Journal of Symbolic Logic 14 (1949): 98-114. Tämä oli Robinsonin väitöskirja. ”Yleiset Rekursiiviset Funktiot.”Proceedings of the American Mathematical Society 1 (1950): 703-718. Sen lisäksi, että Luonnehdinta computable toiminnot yhden väitteen edellä kuvattu, monia muita mielenkiintoisia tuloksia on keskusteltu tässä asiakirjassa. ”Eksistentiaalinen Määriteltävyys Aritmetiikassa.”Transactions of the American Mathematical Society 72 (1952): 437-449. A fundamental paperi, jossa mitä tuli kutsua J. R. osoitettiin merkitä eksistentiaalinen definability, valtuudet 2, primes, ja itse asiassa, koko eksponentiaalinen funktio.
Martin Davisin ja Hilary Putnamin kanssa.”Eksponentiaalisten Diophantine-yhtälöiden Päätösongelma.”Annals of Mathematics 74 (1961): 425-436. Se oli tässä asiakirjassa, että se oli osoittautunut, että J. R. merkitsee unsolvability, Hilbert kymmenes ongelma. ”Johdatus Hyperaritmeettisiin funktioihin.”Journal of Symbolic Logic 32 (1967): 325-342. Tämä oli Robinsonin yksi retki erittäin uncomptable.
Juri Matijasevitšin Kanssa. ”Mielivaltaisen Diofantiiniyhtälön vähentäminen yhteen 13 tuntemattomasta.”Acta Arithmetica 27 (1975): 521-553. Virtuoosimainen lukuteoria! Martin Davisin ja Yuri Matiyasevichin kanssa. ”Hilbertin kymmenes ongelma. Diophantine yhtälöt: positiivisia näkökohtia negatiivinen ratkaisu.”Matemaattisessa kehityksessä, joka johtuu Hilbertin ongelmista, Felix Browderin toimittamana. Providence, Ri: American Mathematical Society, 1976.
Proceedings of Symposia in Pure Mathematics 28 (1976): 323-378. A survey of the proof of the unsolvability, Hilbert ’ s kymmenes ongelma sekä matemaattinen kehitys johtuu siitä, että kolme neljästä matemaatikot, joiden työ johti siihen, että todiste.
Julia Robinsonin kootut teokset. Toimittanut Solomon
Feferman. Providence, Ri: American Mathematical Society, 1996. Kaikki kaksikymmentäviisi Robinsonin julkaisut ovat uusintapainos täällä kokonaisuudessaan. Lisäksi on fefermanin kansalliselle tiedeakatemialle kirjoittama hieno elämäkerrallinen essee hänestä.
muut lähteet
Davis, Martin. ”Hilbertin kymmenes ongelma on ratkaisematon.”
American Mathematical Monthly 80 (1973): 233-269; uusintapainos an appendix in Computability and Unsolvability, edited by Martin Davis. New York: Dover, 1983. Steele-palkittu essee, joka tarjoaa täydellisen todisteen siitä, että unsolvability, Hilbert kymmenes ongelma. The Dover uusintapainos on yksi ensimmäisistä kirjan pituus hoitoja computability theory.
—, ja Reuben Hersh. ”Hilbertin kymmenes ongelma.”
Scientific American 229 (Marraskuu 1973): 84-91. Uusintapainos, Chauvenet Papers, Vol. 2, toimittanut J. C. Abbott. Washington, DC: Mathematical Association of America, 1978. A Chauvenet-palkinnon voittanut artikkeli tarkoitettu yleinen koulutettu yleisö.
Matijasevitš, Juri. ”Yhteistyöni Julia Robinsonin kanssa.”
The Mathematical Intelligencer 14 (1992): 38-45. Hänen tarinansa siitä, miten nuori venäläinen ja paljon vanhempi amerikkalainen nainen tulivat tuottamaan eleganttia matematiikkaa yhdessä.
———. Hilbertin kymmenes ongelma. Cambridge, MA: MIT Press,
1993. Erinomainen johdanto ja tutkimus sopii perustutkintoa matematiikan majors, jossa on hyvin osallistava kirjallisuusluettelo.
Reid, Constance. Julia, elämä matematiikassa. Washington, DC:
Mathematical Association of America, 1996. Siinä on Robinsonin siskon valokuvia, Reidin hyödyllinen elämäkerta ”The Autobiography of Julia Robinson” sekä Martin Davisin lyhyt muistio hänen työstään Hilary Putnamin kanssa.
Martin Davis
