Phenquestions
Turingi masin on arvutiteaduse keskne teoreetiline konstruktsioon. Turingi masin on arvutamise abstraktne matemaatiline mudel. Turingi masinate kasutamine aitab selgitada, mis on arvutus, piiritledes nn “arvutatavad funktsioonid”.”
Alan Turingi varajane loogika uurimine keskendus kuulsale lahendamata probleemile, mida nimetatakse Entscheidungsproblemiks. Probleemi Entscheidungsprobleemi (umbes tõlgitud saksa keelest kui otsustamisprobleem) pakkus välja filosoof ja matemaatik David Hilbert 1928. aastal. Probleemiks küsiti, kas on olemas algoritm, mis otsustab iga avalduse ametlikus keeles.
Ametlik keel on aksioomide ja järeldusreeglite süsteem, näiteks aritmeetilises või esimese järgu loogikas. Aksioomid võivad olla mis tahes sümbolid ja järeldusreeglid võivad olla mis tahes reeglite loetelu nende sümbolitega manipuleerimiseks. „Iga väite otsustamine” tähendas kas avalduse tõesuse / vale väljaandmist või avalduse tuletatavuse / alahindamise avaldamist. Kurt Godeli täielikkuse teoreem tõestas, et kehtivuse üle otsustav algoritm on samaväärne tuletatavuse üle otsustava tõhusa protseduuriga. Alan Turingi 1936. aasta artikkel „Arvutatavatest numbritest koos rakendusega Entscheidungsproblemile” osutas negatiivsele tulemusele, et ametliku süsteemi iga avalduse algoritmiline otsustamine oli võimatu.
Alan Turing
Entscheidungsprobleemi negatiivse tulemuse tõestamiseks oli Turingil vaja algoritmi mõiste vormistada. Turingi algoritmi vormistamine oli arvutamise matemaatiline mudel, mis hiljem sai nimeks Turingi masin. Turingi masinal on piiratud hulk olekuid, milles masin võib olla. Turingi masinal on lõpmata pikk lint, mis on jagatud ruutudeks. Igal lindil oleval ruudul on sümbol, mis on tõmmatud piiratud sümbolite hulgast. Arvutamise igal hetkel loeb Turingi masin lindi ühel ruudul sümbolit. Turingi masin võib selle sümboli teise sümboliga asendada ja liikuda kas ruudule paremale või ruudule vasakule. Toimingu, mille Turingi masin teeb, määrab automaatselt masina olek. Pärast asendussümboli ja teisele ruudule liikumise toimumist võib Turingi masin minna üle teisele olekule. Igal erineval riigil on erinevad reeglid, kuidas sümboleid asendada ja mis suunas liikuda.
Turingi masina disaini haruldane füüsiline teostus (ilma lõpmatu lindita)
Turingi masina kanooniline sõnastus koosneb tavaliselt binaarsest tähestikust, mis koosneb ainult 0-st ja 1-st. See sõnastus sobib kaasaegsete arvutiprogrammeerijate intuitsiooniga, arvestades, et kõik kaasaegsed arvutid kasutavad binaarseid. Tegelikult on Turingi masinad sümbolite tähestiku suuruse suhtes neutraalsed. Turingi masin võib kasutada ka mis tahes sümbolit, nii numbrit kui ka muud tüüpi tähestikku, näiteks pildisümboleid või ladina tähestikku,. Iga võimaliku piiratud tähestiku mis tahes sõnastus on tõendatavalt taandatav binaarseks Turingi masinaks.
Turingi masinad eeldavad, et mälu on lõputult palju. Ükski reaalselt füüsiliselt ekspresseeritud masin ei suuda seda Turingi masinaks olemise nõuet täita. Turingi masin eeldab ka, et funktsiooni arvutamiseks võib kulutada lõpmatult palju aega. Need eeldused tehti selleks, et genereerida Turingi arvutatavate funktsioonide määratluse jaoks võimalikult ulatuslik funktsioonide klass. Turingi arvutatavad funktsioonid on mis tahes funktsioonid, mida Turingi masin saab arvutada. Paljusid neist arvutatavatest funktsioonidest ei pruugi ükski füüsiliselt ekspresseeritud masin kunagi arvutada, kuna need nõuavad liiga palju aega või mälu.
Kiriku-Turingi väitekiri kinnitab arvutatavate funktsioonide ja funktsioonide samaväärsust, mida saab Turingi masinaga arvutada. See tähendab, et kõiki funktsioone, mida Turingi masinad ei saa välja arvutada, ei saa arvutada ühegi muu meetodiga. David Hilbert oli oodanud Entscheidungsprobleemile positiivset vastust, mis tähendaks, et kõik probleemid on arvutatavad. Turingi tulemus on viinud paljude väljaarvutamatute probleemide avastamiseni.
Kuulsaim väljaarvutamatu probleem on peatamisprobleem. Peatumisprobleem on algoritmi loomise probleem, mis võib üldjuhul otsustada, kas arvutiprogramm koos sisendiga peatub või jätkub igavesti. Kuigi on konkreetseid juhtumeid, kus peatamisprobleemi saab lahendada, ei saa seda lahendada iga arvutiprogrammi jaoks, millel on sisend. Sellel tulemusel on olnud olulised tagajärjed arvutiprogrammeerimise jaoks, kuna programmeerijad peavad enne programmide käivitamist olema teadlikud lõpmatute silmuste võimalikkusest ja võimatusest kõiki lõpmatuid silmuseid tuvastada.
Teine Turingi masina mõte on universaalsete Turingi masinate võimalus. Turingi disainis on implitsiitselt mõte salvestada programm, mis muudab andmeid koos muudetavate andmetega. See pakkus võimalust kasutada üldotstarbelisi ja ümber programmeeritavaid arvuteid. Kaasaegsed arvutid on tavaliselt universaalsed Turingi masinad selles mõttes, et neid saab programmeerida mis tahes algoritmi käitamiseks. See välistas vajaduse iga potentsiaalse arvutiprogrammi jaoks erineva riistvara järele ja tutvustas riistvara / tarkvara vahet.
Turingi masinamudel viis otseselt arvutite leiutamiseni, kuid see pole sama plaan, mida kasutatakse tänapäevaste arvutite väljatöötamiseks. Kaasaegsete arvutite kavandina kasutatud von Neumanni arhitektuur kasutab salvestatud programmi kontseptsiooni, mis on implitseeritud Turingi masina mudelis, kuid erineb ülejäänud Turingi masina mudelist mitmel olulisel viisil. Suurimad erinevused on see, et von Neumanni arhitektuur ei kasuta kirjutamis- ja kirjutamispead ning sisaldab selle asemel mitut registrit, vabamälu, andmebusse, väikest masina põhijuhiste komplekti ja mitme bitise töötlemise võimalusi. Samuti lubab von Neumanni arhitektuur selgesõnaliselt spetsiaalseid sisend- ja väljundseadmeid, nagu klaviatuurid ja monitorid.
Turingi masinamudel oli esimene arvutamise matemaatiline mudel. See viis otseselt füüsiliste arvutite leiutamiseni. Füüsilistel arvutitel on kõik samad võimalused nagu Turingi masinatel, eeldades, et tegelikuks arvutamiseks on piiratud mälu ja ajapiirangud. Turingi formulatsioon mängib arvutamise uurimisel endiselt keskset rolli. Arvutiteadlased tegelevad endiselt aktiivselt selle uurimisega, kas konkreetsed funktsioonid on Turingi masinate abil arvutatavad.
