Hilbertin kymmenes tehtävä on yksi 23 ongelmasta , jotka David Hilbert ehdotti 8. elokuuta 1900 II kansainvälisessä matemaatikoiden kongressissa . Se koostuu universaalin menetelmän löytämisestä mielivaltaisen algebrallisen diofantiiniyhtälön ratkottavuuden määrittämiseksi . Tämän ongelman algoritmisen ratkaisemattomuuden todistaminen kesti noin kaksikymmentä vuotta, ja Juri Matiyasevitš valmistui vuonna 1970 [1] [2] .
Hilbertin raportissa kymmenennen ongelman muotoilu on lyhin kaikista:
Annetaan diofantiiniyhtälö mielivaltaisilla tuntemattomilla ja kokonaislukujen rationaalisilla numeerisilla kertoimilla. Ilmoita menetelmä, jolla on mahdollista äärellisen määrän operaatioiden jälkeen määrittää, onko tämä yhtälö ratkaistavissa rationaalisilla kokonaisluvuilla [3] .
Alkuperäinen teksti (saksa)[ näytäpiilottaa] Eine Diophantische Gleichung mit irgend welchen Unbekannten und mit ganzen rationalen Zahlencoefficienten sei vorgelegt: man soll ein Verfahren angeben, nach welchem sich mittelst einer endlichen Anzahl von Operationen entscheiden läßt, ob die lözen rationalen is zahlen lözen rationalen .Muodollisesti puhumme muodon yhtälöiden kokonaisluku [5] ratkaisusta
jossa on polynomi kokonaislukukertoimilla ja kokonaislukueksponenteilla [6] . Yhtälön aste on yhtä suuri kuin polynomin aste .
Kaikista 23 ongelmasta se on ainoa ratkaistavuuden ongelma [7] . Ilmeisesti Hilbert uskoi, että haluttu menetelmä on olemassa ja se löydetään ennemmin tai myöhemmin [8] . Kysymys siitä, ettei tällaista menetelmää olisi periaatteessa olemassa, ei tullut esille Hilbertin aikana [9] [10] .
Algebrallisten yhtälöiden kokonaislukuratkaisu on kiinnostanut matemaatikoita muinaisista ajoista lähtien. Esimerkiksi yhtälöön kiinnitettiin paljon huomiota : jos sen ratkaisu olisi luonnollisten lukujen joukko , niin Pythagoraan lauseen käänteisellä lauseella voitaisiin saada suorakulmainen kolmio pituusosista [11] . Euclid antoi kaavat tämän yhtälön kaikkien kokonaislukuratkaisujen löytämiseksi [12] . Joitakin toisen asteen yhtälötyyppejä ja niiden järjestelmiä tarkasteli Diophantus Aleksandrialainen [13] , hänen teoksiaan käyttivät myöhemmin Leonhard Euler , Pierre Fermat , Joseph Louis Lagrange , Carl Friedrich Gauss ja muut lukuteoriaan osallistuvat matemaatikot . Erityisesti Fermat esitti kuuluisan hypoteesinsa . Vuoteen 1768 mennessä Lagrange oli täysin tutkinut kysymyksen kokonaislukuratkaisuista mille tahansa toisen asteen yhtälölle kahdessa tuntemattomassa [14] .
1800-luvulla monet matemaatikot, jotka ratkaisivat Fermatin viimeisen lauseen , yrittivät tutkia diofantiiniyhtälöitä, joiden aste oli korkeampi kuin toinen. Siitä huolimatta tällaisten yhtälöiden ratkaisemisen ongelma jäi avoimeksi : yleistä menetelmää ei saatu, vain erityisiä menetelmiä löydettiin tietyntyyppisille yhtälöille. Todennäköisimmin Hilbert epäili, että tämän alueen lisätutkimus johtaisi yksityiskohtaisten ja syvien teorioiden luomiseen, jotka eivät rajoittu diofantiiniyhtäloihin, ja tämä sai hänet luettelemaan ongelman raporttiinsa [9] .
1940-luvulle asti tutkittiin kymmenennestä ongelmasta, jotta löydettiin tarvittava algoritmi ainakin joillekin diofantiiniyhtälöiden luokille. Muutama vuosi Hilbertin raportin jälkeen, vuonna 1908, Axel Thue osoitti, että Thue-yhtälössä kahdelle tuntemattomalle ei voi olla äärettömän monta kokonaislukuratkaisua [15] . Vuonna 1938 Turalf Skolem julkaisi menetelmän diofantiiniyhtälöiden tutkimiseksi muodossa, jossa on epätäydellinen hajoava muoto ( pelkistymätön polynomi , joka laajenee rationaalilukujen alalla lineaaristen tekijöiden tuloksi ) , joka täyttää tietyt ehdot [16] . Thuen tuloksesta huolimatta jopa yhtälöt, joissa oli kaksi tuntematonta, uhmasivat matemaatikoiden ponnisteluja (algoritmi yhtälöiden ratkaisemiseksi yhdellä tuntemattomalla seuraa Bézoutin lauseesta ).
1930-luvun puolivälissä algoritmin käsite formalisoitiin, ja myös ensimmäiset esimerkit matemaattisen logiikan algoritmisesti ratkaisemattomista joukoista ilmestyivät . Tärkeä hetki oli Andrei Markovin ja Emil Postin (toisistaan riippumatta) todiste Thuen ongelman ratkaisemattomuudesta vuonna 1947 [17] [18] . Tämä oli ensimmäinen todiste algebrallisen ongelman ratkaisemattomuudesta. Se, samoin kuin diofantiiniyhtälöiden tutkijoiden kohtaamat vaikeudet, johtivat oletukseen, että Hilbertin vaatimaa algoritmia ei ole olemassa. Hieman aikaisemmin, vuonna 1944, Emil Post kirjoitti jo yhdessä kirjoituksessaan, että kymmenes ongelma " anelee ratkaisemattomuuden todistetta" [ 19] .
Postin sanat inspiroivat opiskelijaa Martin Davisia etsimään todisteita siitä, että kymmenes ongelma oli ratkaisematon. Davis siirtyi kokonaislukujen formuloinnista luonnollisten lukujen muotoiluun, mikä on luonnollisempaa algoritmien teorialle [20] . Nämä ovat kaksi eri tehtävää, mutta jokainen niistä tiivistyy toiseen. Vuonna 1953 hän julkaisi artikkelin, jossa hän hahmotteli tavan ratkaista kymmenennen luonnollisten lukujen ongelma [21] .
Davis yhdessä klassisten diofantiiniyhtälöiden kanssa harkitsi niiden parametrista versiota:
jossa polynomi kokonaislukukertoimilla voidaan jakaa kahteen osaan - parametreihin ja muuttujiin.Yhtälöllä voi olla ratkaisu yhdelle parametriarvojoukolle, toiselle ratkaisuja ei välttämättä ole olemassa. Davies valitsi joukon , joka sisältää kaikki parametriarvot ( -t), joille yhtälöllä on ratkaisu:
Hän kutsui tällaista merkintää joukon diofantiiniksi, ja itse joukkoa kutsuttiin myös Diofantiiniksi . Kymmenennen tehtävän ratkaisemattomuuden osoittamiseksi tarvittiin vain osoittaa, että mikä tahansa numeroitu joukko on Diofantiini eli osoittaa mahdollisuus muodostaa yhtälö, jolla olisi luonnolliset juuret vain kaikille tähän numeroitavaan joukkoon kuuluville: koska numeroituja joukkoja on ratkaisemattomia , jolloin ratkaisematon joukko perustaksi otettaessa olisi mahdotonta saada yleistä menetelmää, joka määrittäisi yksitellen, onko yhtälöllä luonnolliset juuret tässä joukossa. Kaikki tämä johti Davisin seuraavaan hypoteesiin:
Diofantin ja numeroitavien joukkojen käsitteet ovat yhtenevät. Tämä tarkoittaa, että joukko on diofantiini, jos ja vain jos se on numeroitavissa. |
Davis otti myös ensimmäisen askeleen - hän osoitti, että mikä tahansa lueteltava joukko voidaan esittää seuraavasti:
Tätä esitystä kutsutaan "Davisin normaalimuodoksi". Tuolloin hän ei pystynyt todistamaan arveluaan päästämällä eroon universaalista kvantorista .
Davisista riippumatta Julia Robinson alkoi työskennellä kymmenennen ongelman parissa samoina vuosina . Aluksi hän yritti todistaa Alfred Tarskin olettamuksen, jonka mukaan kahden kaikkien potenssien joukko ei ole diofantiini, mutta se ei onnistunut [22] . Sen jälkeen Robinson siirtyi tutkimaan kysymystä siitä, onko kolmioista koostuva joukko diofantiinia . Hän ei löytänyt diofantiiniesitystä eksponentiooperaatiolle, mutta siitä huolimatta hän osoitti työssään [23] riittävän ehdon sen olemassaololle:
lisäksi:
Robinson kutsui suhdetta ja " eksponentiaalista kasvuriippuvuutta ", mutta myöhemmin tätä riippuvuutta alettiin kutsua hänen kunniakseen - "Robinson-riippuvuus", "Robinson-predikaatit" tai yksinkertaisesti "JR".
Vuonna 1958 Martin Davis ja Hilary Putnam julkaisivat [24] , jossa Robinsonin tuloksen perusteella he tarkastelivat eksponentiaali-diofantiiniyhtälöiden luokkaa, jolla on muoto:
missä ja ovat eksponentiaaliset polynomit, eli lausekkeet, jotka on saatu muuttujista ja rationaaliluvuista käyttämällä yhteen- , kerto- ja eksponentiooperaatioita , ja osoittivat myös diofantiiniesityksen tällaisille yhtälöille. Davisin ja Putnamin todisteissa oli kuitenkin aukko - he käyttivät olettamusta mielivaltaisen pitkien , vain alkuluvuista koostuvien aritmeettisten progressioiden olemassaolosta ( Green-Tao -lause ), joka todistettiin vasta vuonna 2004.
Vuonna 1961 Julia Robinson pystyi täyttämään tämän aukon . Heidän yhteisessä työssään [25] saatiin eksponentiaalinen diofantiiniesitys mille tahansa numeroitavasta joukosta:
Yksi työn seurauksista oli mahdollisuus pelkistää mikä tahansa eksponentiaalinen diofantiiniyhtälö eksponentiaaliseksi diofantiiniyhtälöksi, jossa on kiinteä määrä muuttujia (vähintään kolme [26] ).
Daviesin, Putnamin ja Robinsonin tuloksen siirtämiseksi "tavallisiin" diofantiiniyhtälöihin piti todistaa, että kolmiosista koostuva joukko on diofantiini. Sitten olisi mahdollista, lisätuntemattomien lisäämisen kustannuksella, kääntää eksponentiaalisesti diofantininen esitys diofantiniseksi esitykseksi:
Toisin sanoen Davis-oletuksen täydelliseksi todistamiseksi oli tarpeen todistaa vain yksi tietty tapaus siitä, tai tarkemmin sanottuna, todistaa Robinson-oletus (löytää polynomi , joka täyttää kaikki ehdot).
Huolimatta kahden parametrin diofantiiniyhtälöiden syvällisestä tutkimuksesta Diophantuksen ajoista lähtien, ei tuolloin ollut tunnettua yhtälöä, joka ilmaisi eksponentiaalisen kasvun riippuvuutta. Myös yritykset rakentaa se keinotekoisesti epäonnistuivat.
Hilbertin ongelmia | |
---|---|