Sageli lahendame erineva keerukusega ülesandeid: igapäevaseid, matemaatilisi jne. Mõnda on lihtne lahendada, mõni nõuab palju läbimõtlemist ja mõne puhul ei leia me lahendust kunagi.
Üldiselt saab probleemi lahendamise meetodit (kui see on olemas) kirjeldada piiratud arvu elementaarsete toimingute abil.
Näiteks ruutvõrrandi lahendamine:
Saame tutvustada järgmist intuitiivset algoritmi kontseptsiooni:
Algoritm on juhiste kogum, mis kirjeldab täitja tegevuste järjekorda, et saavutada ülesande lahendamise tulemus piiratud arvu tegevustega mis tahes lähteandmete kogumi jaoks.
See ei ole muidugi range määratlus, kuid see kirjeldab algoritmi kontseptsiooni olemust.
Algoritmid koostatakse konkreetsest lähtudes esineja, ja seepärast tuleb need koostada esitajale arusaadavas keeles.
Algoritmi täitjaks võib olla inimene või arvuti või mõni muu masin, näiteks kangasteljed.
Algoritmide järgmised omadused on esile tõstetud:
Algoritmi diskreetsus peab olema eraldi, selgelt määratletud sammude (toimingute) teatud jada. Kõik need toimingud peavad olema ajaliselt piiratud. Algoritmi iga etapi determinism; järgmise sammu määrab üheselt süsteemi praegune olek. Selle tulemusena tagastab algoritm samadel algandmetel iga kord samad tulemused, olenemata sellest, mitu korda seda käivitatakse. Arusaadavus Algoritm peab olema sõnastatud esitajale arusaadavas keeles. Kui me räägime arvutist, siis peab algoritm kasutama ainult neid käske, mis on arvutile teada ja mille tulemus on rangelt määratletud. Lõplikkus Algoritm peab lõpule jõudma piiratud arvu etappidega. Massiivne algoritm peab olema rakendatav erinevatele sisendandmete kogumitele. Teisisõnu, algoritm peab suutma lahendada klassülesandeid. Tulles tagasi ruutvõrrandi näite juurde, siis algoritm sobib lahendamiseks kõik ruutvõrrandid, mitte ainult üks või paar. Efektiivsus Algoritm peab lõppema kindla tulemusega. Oletame, et probleemi lahendamine või lahenduste puudumise väljaselgitamine. Kui mingi algoritm tulemuseni ei vii, jääb arusaamatuks, milleks seda üldse vaja on.
Mitte iga viis probleemi lahendamiseks ei ole algoritm. Oletame, et algoritm ei sisalda valikut. Näiteks enamik kulinaarsed retseptid ei ole algoritmid, sest nad kasutavad selliseid fraase nagu "lisa maitse järgi soola". Selle tulemusena rikutakse determinismi nõuet.
Igal probleemil, millele on lahendus olemas, ei ole ka lahendusalgoritmi. Näiteks pildituvastuse probleem on endiselt suures osas lahendamata ja seda kindlasti mitte range algoritmi abil. Närvivõrkude kasutamine annab aga päris häid tulemusi.
Tavaliselt on algoritmi jaoks komplektid vastuvõetav sisendandmed. Oleks kummaline proovida rakendada õhtusöögi valmistamisel võrrandilahenduse algoritmi või vastupidi.
Lisaks on piiratud ka teostaja võimalike toimingute ring, sest kui mõni tegevus oleks lubatav, siis peaks nende hulgas olema ka “vastuvõetamatud”.
Eespool toodud algoritmi määratlus ei ole range. See tekitab mõningaid raskusi. Eelkõige on sellise definitsiooniga võimatu täpselt tõestada, kas antud ülesannete klass on algoritmi abil lahendatav.
Selgub, et seal on klass Algoritmiliselt lahendamatud probleemid– probleemid, millele lahendusalgoritmi koostamine on võimatu. Kuid algoritmilise otsustamatuse rangeks tõestamiseks peab teil kõigepealt olema algoritmi range definitsioon.
20. sajandi 20-30ndatel töötasid erinevad matemaatikud algoritmi range määratlemise probleemiga, eriti Alan Turing, Emil Leon Post, Andrei Andreevitš Markov, Andrei Nikolajevitš Kolmogorov, Alonzo Church jt. Nende töö viis lõpuks algoritmide teooria, arvutatavuse teooria ja erinevate lähenemisviiside tekkeni ja arenemiseni arvutuses ning, muide, programmeerimises üldiselt. Nende töö üheks tulemuseks oli algoritmi mitme range definitsiooni tekkimine, mis on kasutusele võetud erineval viisil, kuid üksteisega samaväärsed.
Vaatame lähemalt Turingi definitsiooni ja kraabime samaväärsete Posti, Churchi ja Markovi definitsioonide pinda.
Algoritmi formaalse definitsiooni tutvustamiseks leiutas ja kirjeldas Turing abstraktset arvutusmasinat, mida nimetatakse Turingi masinaks või lihtsalt Turingi masinaks.
Alan Turing (1912-1954)
Inglise matemaatik, loogik, krüptograaf, võib-olla maailma esimene "häkker", seisis arvutiteaduse ja tehisintellekti teooria lähtekohas. Ta andis olulise panuse liitlasvägede võidusse Teises maailmasõjas.
Turingi masina sisendandmed on sõnad, mis on koostatud kasutades teatud tähestik, see tähendab komplekt tegelased.
Turingi masina väljundiks on samuti sõnad.
Kutsutakse sõna, millele algoritm rakendatakse sisend. Tööst tulenev sõna on puhkepäevadel.
Kutsutakse välja sõnade hulk, millele algoritm rakendatakse algoritmi kohaldamisala.
Rangelt võttes on võimatu tõestada, et mis tahes objekti saab esitada mõnes tähestikus koostatud sõnade kujul - selleks vajaksime objekti ranget määratlust. Siiski saab kontrollida, et iga juhuslikult valitud algoritmi, mis töötab objektidel, saab teisendada nii, et see töötab sõnadega, samas kui algoritmi olemus ei muutu.
Turingi masin koosneb mõlemas suunas piiramatust lindist, mis on jagatud rakkudeks, ja juhtseadmest (nn. lugemis-kirjutamispea või lihtsalt masin), mis on võimeline asuma ühes paljudest osariikidest. Juhtseadme võimalike olekute arv on piiratud ja täpselt määratletud.
Juhtseade võib liikuda mööda linti vasakule ja paremale, lugeda ja kirjutada lahtritesse mõne lõpliku tähestiku märke. Eraldatakse spetsiaalne tühi märk \(a_0\) või \(\Lambda\) , mis täidab kõik lindi lahtrid, välja arvatud need (lõplik arv), millele sisendandmed on kirjutatud.
Juhtseade töötab üleminekureeglite järgi, mis esindavad antud Turingi masina poolt rakendatud algoritmi. Iga üleminekureegel käsib masinal olenevalt hetkeolekust ja praeguses lahtris vaadeldavast sümbolist kirjutada sellesse lahtrisse uus sümbol, liikuda uude olekusse ja liigutada üks lahter vasakule või paremale. Mõnda Turingi masina olekut saab märkida terminaliks ja üleminek ükskõik millisele neist tähendab töö lõppu, algoritmi peatamist.
Kuigi Turingi masin on abstraktne mõiste, on sellist masinat üsna lihtne ette kujutada (ehkki piiratud lindiga) ja on isegi seda tüüpi näidismasinaid:
Turingi masina algoritmi on mugav esitada tabeli kujul: tabeli veerud vastavad lindil olevale (vaadeldud) sümbolile, read vastavad masina hetkeolekule ja lahtrid salvestavad käsk, mida masin peab täitma.
Käsklusel võib omakorda olla järgmine struktuur:
\[ a_k \left\lsulg \begin(maatriks) L \\ N \\ P \end(maatriks)\right\rsulg q_m \]
Kõigepealt tuleb tähestiku sümbol, mis tuleb kirjutada jooksvasse lahtrisse \(a_k\), seejärel näidatakse masina liikumist vasakule (L), paremale (R) või mitte kuhugi (paigale jääda, N). Lõpus näidatakse uut olekut, kuhu automaat \(q_m\) peaks minema.
Tabeli lahter on selgelt määratud praeguse sümboli \(a_i\) ja masina hetkeolekuga \(q_j\) .
Leppigem kokku, et töö alguses on Turingi masin sees algseisund, tähisega \(q_1\) ja asukohale liikumisel peatus olek\(q_0\) algoritm on lõpule viidud ja masin peatub.
Koostame Turingi masina jaoks algoritmi, mis lisab sisendsõnale 1, mis on kümnendarv.
Seejärel saab algoritmi kirjeldavalt formuleerida järgmiselt:
Kirjutame selle algoritmi tabeli kujul. Tähestik koosneb numbritest 0 kuni 9 ja "tühjast märgist" \(\Lambda\) . Vajame ka 4 masina olekut, loendades peatumisoleku, mis vastab algoritmi kirjelduse sammudele.
Leppigem kokku, et algseisund \(1\) on sisendsõna alguse otsing, \(2\) on sisendsõna lõpu otsing, \(3\) on 1 liitmine.
| \(_(q_j)\kaldkriips^(a_i)\) | Λ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | ΛП1 | 0H2 | 1H2 | 2H2 | 3H2 | 4H2 | 5N2 | 6N2 | 7N2 | 8N2 | 9N2 |
| 2 | ΛЛ3 | 0P2 | 1P2 | 2P2 | 3P2 | 4P2 | 5P2 | 6P2 | 7P2 | 8P2 | 9P2 |
| 3 | 1Н0 | 1Н0 | 2Н0 | 3Н0 | 4Н0 | 5Н0 | 6Н0 | 7Н0 | 8Н0 | 9Н0 | 0L3 |
Vaatame näite abil, kuidas see algoritm töötab. Esimene rida vastab lindile, teine näitab masina asukohta ja hetkeseisu.
| 1 | 9 | 9 | ||
| 1 |
Olekus 1 asub masin tühja lahtri kohal. Vastav käsk tabelist “ΛП1”, st jätke lahter tühjaks, liigutage paremale ja jääge olekusse 1:
| 1 | 9 | 9 | ||
| 1 |
Nüüd jälgib masin väärtust “1”. Vastav käsk on "1H2", st jätke see lahtrisse "1", ärge liigutage ja minge olekusse "2":
| 1 | 9 | 9 | ||
| 2 |
Olekus “2” jälgib masin väärtust “1”. Vastav käsk on “1P2”, st lahkuda “1”, liikuda paremale ja jääda olekusse “2”:
Olukord kordub:
Nüüd, olekus 3 ja jälgides sümbolit “9”, täidab masin käsu “0L3”:
| 1 | 9 | 0 | ||
| 3 |
Olukord kordub:
Olek "0" – seisak. Algoritm on valmis.
Matemaatiliselt saab Turingi masinat kirjeldada järgmiselt:
Thuringi masin (MT)
see on vormi süsteem \(\(A, a_0, Q, q_1, q_0, T, \tau\)\), Kus
Algoritmide teooria võti on Turingi väitekiri.
Lõdvalt sõnastatud Turingi tees on järgmine:
Turingi tees: iga algoritmiliselt lahendatava ülesande jaoks on Turingi masin, mis selle ülesande lahendab. vastasel juhul on iga algoritmi jaoks samaväärne Turingi masin.
Turingi lõputöö võimaldab algoritmidest rääkida üsna lihtsa matemaatilise aparatuuri abil. Pealegi on Turingi masin ise universaalne täiturmehhanism, ja juba sellise kujuteldava masina loomise võimalus sai põhjuseks rääkida universaalse arvutustehnoloogia loomisest.
Peale Turingi masina on mitmeid sõltumatuid definitsioone, mis on samaväärsed Turingi definitsiooniga.
Eelkõige määratlus postimasina, Churchi lambda-arvutuse ja tavalise Markovi algoritmi kaudu.
Vaatleme neid meetodeid.
Aasta pärast Turingi pakkus Ameerika matemaatik Emil Leon Post iseseisvalt välja teise abstraktse universaalse arvutusmasina, mis on Turingi masinaga võrreldes mõningane lihtsustus.
Posti masin töötab kahekohalise tähestikuga ja masina sisemine olek asendatakse programmi rida.
Muus osas sarnaneb Postimasin Turingi masinaga: seal on automaat ja lõpmatu rakkudega lint.
Postimasin suudab täita järgmisi käske:
Samuti on Posti masinal mitu keelatud käsku:
Sellised sündmused põhjustavad ebanormaalset väljalülitamist.
Postimasina jaoks programmide kirjutamiseks võite kasutada järgmist tähistust:
Näidisprogramm:
1. → 2 2. ? 1; 3 3. × 4 4. ← 5 5. !
See programm kustutab esimese märgi (1), mis asub masina algasendist paremal, ja peatab masina sellest vasakul asuvas lahtris.
Suures plaanis on Posti auto eelkäija hädavajalik programmeerimiskeeled, näiteks C, Fortran jne.
Postimasin on samaväärne Turingi masinaga. Teisisõnu, iga Turingi masina programmi jaoks saab kirjutada samaväärse programmi Postmasina jaoks ja vastupidi.
Selle samaväärsuse üks oluline tagajärg on see mis tahes tähestikku saab taandada kahendkoodiks.
Sarnaselt Turingi teesile on olemas ka Posti tees.
Postituse lõputöö kujutame ette iga algoritmi postimasinana.
Markovi tavaalgoritmid on loodud kasutamiseks mitmesuguste tähestike sõnadele.
Tavalise algoritmi määratlus koosneb kahest osast:
Algoritmi ennast rakendatakse sõnad, see tähendab märgijadasid tähestik.
Tavalise algoritmi skeem on lõplik järjestatud hulk nn asendusvalemid, millest igaüks võib olla lihtne või lõplik. Lihtsad asendusvalemid on avaldised kujul \(L\kuni D\) , kus \(L\) ja \(D\) on kaks suvalist sõna, mis on koostatud algoritmi tähestikust (nimetatakse vastavalt vasakule ja paremale poolele asendusvalemist). Samamoodi on lõplikud asendusvalemid avaldised kujul \(L\to\cdot D\) , kus \(L\) ja \(D\) on kaks suvalist sõna, mis on koostatud algoritmi tähestikust.
Eeldatakse, et abisümbolid \(\to\) ja \(\to\cdot\) ei kuulu algoritmi tähestikusse.
Suvalisele sõnale \(V\) tavaalgoritmi rakendamise protsess on järgmine toimingute jada:
Iga tavaline algoritm on samaväärne mõne Turingi masinaga ja vastupidi – iga Turingi masin on samaväärne mõne tavalise algoritmiga.
Tavaliselt nimetatakse Turingi teesi analoogi tavaalgoritmidele normaliseerimise põhimõte.
See algoritm teisendab kahendarvud "üksikuteks" numbriteks (milles mittenegatiivse täisarvu N esitus on N pulga jada). Näiteks binaararv 101 teisendatakse 5 pulgaks: |||||.
Tähestik: ( 0, 1, | ) Reeglid:
Turingi masinaga samaväärse süsteemi saab konstrueerida matemaatiliste funktsioonide põhjal. Selleks peame kasutusele võtma järgmised funktsiooniklassid:
Viimane klass langeb kokku Turingi arvutatavate funktsioonide klassiga (st funktsioonidega, mille arvutamiseks saab koostada Turingi masina algoritmi).
Algoritmi defineerimine rekursiivsete funktsioonide kaudu on sisuliselt lambda-arvutuse aluseks ja sellele tugineb ka lähenemine funktsionaalne programmeerimine.
Primitiivsete rekursiivsete funktsioonide klass sisaldab põhifunktsioonid ja kõik põhifunktsioonidest operaatorite abil saadud funktsioonid asendused Ja primitiivne rekursioon.
Põhifunktsioonid hõlmavad järgmist:
Ülejäänud klassi funktsioonide konstrueerimiseks kasutatakse järgmisi operaatoreid:
Osaliselt rekursiivsete funktsioonide klass sisaldab primitiivseid rekursiivseid funktsioone ja lisaks kõiki funktsioone, mis saadakse primitiivsetest rekursiivsetest funktsioonidest, kasutades argumentide minimeerimise operaatorit:
Argumentide minimeerimise operaator
Olgu \(f\) \(n\) muutujate \(x_i \in \mathbb(N)\) funktsioon. Seejärel on argumendi minimeerimisoperaatori rakendamisel funktsioonile \(f\) argumendi \(n-1\) funktsioon \(h\), mis on määratletud järgmiselt:
\[ h(x_1,\ldots,x_(n-1)) = \min y, \] Kus \ See tähendab, et \(h\) tagastab funktsiooni \(f\) viimase argumendi minimaalse väärtuse, mille juures \(f\) väärtus on võrdne nulliga.
Kuigi primitiivsed rekursiivsed funktsioonid on alati arvutatavad, ei pruugita osaliselt rekursiivseid funktsioone mõne argumendiväärtuse jaoks määratleda.
Täpsemalt tuleks osaliselt rekursiivseid funktsioone nimetada "osaliselt määratletud rekursiivseteks funktsioonideks", kuna need on määratletud ainult osa argumentide võimalikest väärtustest.
Üldiselt on rekursiivsed funktsioonid kõigi osaliselt rekursiivsete funktsioonide alamklass, mis on määratletud mis tahes argumentide väärtuste jaoks. Ülesanne määrata, kas antud osaliselt rekursiivne funktsioon on üldiselt rekursiivne, on algoritmiliselt otsustamatu. See viib meid arvutatavuse teooria ja peatumisprobleemi teema juurde.
Meie kujutlusvõime võimaldab üldiselt lahendada lahendamatuid probleeme, st probleeme, millele pole võimalik algoritmi luua.
Arvutavuse teooria uurib selliseid probleeme.
Algoritmiliselt lahendamatute probleemide näited on väljalülitamise probleem Ja viirutatavuse tuvastamise probleem. Vaatame neid üksikasjalikumalt.
Peatamisülesanne Arvestades algoritmi A kirjeldust ja sisendandmeid \(x\), on vaja välja selgitada, kas algoritm \(A\) peatub sisendandmetel \(x\) .
Peatusprobleem on algoritmiliselt lahendamatu. Tõestame seda.
\(\Delta\)Olgu universaalne algoritm, mis lahendab peatumisprobleemi. Vaatleme siis algoritmide klassi, mis töötleb algoritmi kirjeldustekste.
Universaalse peatamisülesande lahendamise algoritmi olemasolu tõttu on olemas algoritm, mis määrab, kas nimetatud klassi algoritm peatub oma teksti peale või mitte. Tähistame sellist algoritmi \(B\) .
Koostame algoritmi \(C\), mille sisendandmeteks on algoritmi \(A\) tekst, mis töötleb oma teksti:
Kui proovime rakendada \(C\) algoritmi \(C\) algoritmile, jõuame ilmse vastuoluni: kui \(C\) peatub oma teksti juures, siis ta ei saa peatuda ja vastupidi. Seetõttu pole algoritmi \(B\) . \(\mitte \Delta\)
Peatusprobleemi üldisem sõnastus on tuletatavuse määramise probleem.
Viirutatavuse tuvastamise probleem
Olgu määratletud teatud tähestik, selle tähestiku sõnad (valemid) ja selle tähestiku sõnade formaalsete teisenduste süsteem (st on konstrueeritud loogiline arvutus)
Kas mis tahes kahe sõna \(R\) ja \(S\) korral on antud loogilises arvutuses deduktiivne ahel, mis viib \(R\)-st \(S\)-ni?
1936. aastal tõestas Alonzo Church Churchi teoreemi.
Churchi teoreem Tuletavuse tuvastamise probleem on algoritmiliselt lahendamatu.
Church kasutas selle tõestamiseks lambda-arvutuse formalismi. Aastal 1937 tõestas Turing iseseisvalt sama teoreemi, kasutades Turingi masina formalismi.
Kuna kõik algoritmide definitsioonid on üksteisega samaväärsed, on olemas mõistete süsteem, mis ei ole seotud konkreetse algoritmi definitsiooniga ja toimib kontseptsiooniga arvutatav funktsioon.
Arvutusfunktsioon on funktsioon, mille jaoks saab kirjutada algoritmi.
On probleeme, mille puhul ei saa algoritmi kasutades kirjeldada sisend- ja väljundandmete suhet. Sellised funktsioonid on arvutamatu.
Kasutage funktsiooni \(h(n)\) jaoks \(\forall n \in \mathbb(N)\) määratletud funktsioon järgmiselt:
\[ h(n) = \begin(cases) 1, & \text(if in )\pi\text( on jada täpselt )n\text( 9-k) \\ 0, & \text(muidu )\end(juhtumid)\]
Selle funktsiooni jaoks saame väärtuse \(1\), kuid väärtuse \(0\) saamiseks peame kontrollima arvu \(\pi\) lõpmatut kümnendlaiendit, mis pole ilmselt piiratud aja jooksul võimalik . Seetõttu pole see funktsioon arvutatav.
Turingi masin on järgmiste objektide kogum
Tühja lahtri sümboliks on välistähestiku täht a 0 .
Olekute hulgas on esialgne q 1, milles masin hakkab tööle, ja lõpp- (või seiskamisseisund) q 0, mille korral masin peatub.
Juhtseade saab liikuda mööda linti vasakule ja paremale, lugeda ja kirjutada lindi lahtritesse tähemärke A. Juhtseade töötab käskude järgi, millel on järgmine kuju
q i a j > a p X q k
Salvestamine tähendab järgmist: kui juhtseade on olekus q i ja vaadeldavas lahtris on kirjutatud täht a j, siis (1) kirjutatakse lahtrisse j asemel p, (2) masin jätkab järgmise ülevaatusega. äsja vaadatud lahtri parempoolsesse lahtrisse, kui X = P, või järgmise vasakpoolse lahtri vaatamiseks, kui X = L, või jätkab sama lindi lahtri vaatamist, kui X = C, (3) juhtseade läheb olekusse q k.
Kuna masina töö on kokkuleppeliselt täielikult määratud selle olekuga q antud hetkel ja sel hetkel vaadeldava lahtri sisuga a, siis iga võimaliku konfiguratsiooni q i a j jaoks on täpselt üks reegel. Puuduvad reeglid ainult lõpliku oleku kohta, mil auto peatub. Seetõttu ei sisalda Turingi masina programm välise tähestikuga A=(a0, a1, …, an) ja sisemise Q=(q1, q2,…, qm) rohkem kui m (n+ 1) käsku.
Sõna tähestikus A või tähestikus Q või tähestikus A Q on mis tahes vastava tähestiku tähtede jada. K-nda konfiguratsiooni all peame silmas masinlindi kujutist, millele k-nda sammu alguses kogutud teave (või k-nda sammu alguses lindile kirjutatud tähestiku A sõna) , mis näitab, millist lahtrit selles etapis vaadatakse ja millises seisukorras auto on. Ainult lõplikud konfiguratsioonid on mõttekad, s.t. need, milles kõik lindi lahtrid, välja arvatud võib-olla lõplik arv, on tühjad. Konfiguratsiooni nimetatakse lõplikuks, kui olek, milles masin asub, on lõplik.
Kui valime esialgseks Turingi masina mittelõpliku konfiguratsiooni, siis on masina tööks algse konfiguratsiooni järjestikune (samm-sammult) teisendamine vastavalt masina programmile kuni lõpliku konfiguratsioonini. Pärast seda loetakse Turingi masina töö lõppenuks ja töö tulemuseks saavutatud lõplik konfiguratsioon.
Ütleme, et mittetühja sõna b tähestikus A (a 0) = (a 1, ..., a n) tajub masin standardasendis, kui see on kirjutatud lindi järjestikustesse lahtritesse, kõik teised lahtrid on tühjad ja masin vaatab kõige vasakpoolsemat või parempoolset lahtrit nendest, kuhu on kirjutatud sõna b. Standardpositsiooni nimetatakse esialgseks (lõpuliseks), kui masin, mis tajub sõna standardasendis, on algolekus q 1 (vastavalt peatumisolekus q 0).
Kui sõna b töötlemine viib Turingi masina lõppolekusse, siis öeldakse, et see on rakendatav b-le, vastasel juhul ei ole see rakendatav b-le (masin töötab lõputult)
Vaatame näidet:
Antud Turingi masin, mille väline tähestik on A = (0, 1) (siin on 0 tühja lahtri sümbol), sisemiste olekute tähestik Q = (q 0, q 1, q 2) ja järgmise funktsionaaldiagrammiga (programm):
q 1 0 > 1 L q 2;
q 1 1 > 0 С q 2;
q 2 0 > 0 П q 0 ;
q 2 1 > 1 С q 1;
Seda programmi saab kirjutada tabeli abil
Esimeses etapis rakendatakse käsku: q 1 0 > 1 L q 2 (juhtseade on olekus q1 ja jälgitavasse lahtrisse kirjutatakse täht 0, 0 asemel kirjutatakse lahtrisse 1, pea liigub vasakule, juhtseade läheb olekusse q2), mille tulemusena luuakse masinas järgmine konfiguratsioon:
Lõpuks, pärast käsu q 2 0 > 0 П q 0 täitmist luuakse konfiguratsioon
See konfiguratsioon on lõplik, kuna masin on seisatud olekus q 0 .
Seega töötleb masin algse sõna 110 sõnaks 101.
Saadud seadistuste jada saab kirjutada lühemalt (jälgitava lahtri sisu kirjutatakse paremale sellest olekust, milles masin parasjagu on):
11q 1 0 => 1 q 2 11 => 1 q 1 11 => 1 q 2 01 => 10 q 0 1
Turingi masin pole midagi muud kui teatud reegel (algoritm) tähestiku A Q sõnade teisendamiseks, s.o. konfiguratsioonid. Seega tuleb Turingi masina defineerimiseks määrata selle väline ja sisemine tähestik, programm ning näidata, millised sümbolid tähistavad tühja lahtrit ja lõppseisu.
Poisid, paneme saidile oma hinge. Tänan sind selle eest
et avastad selle ilu. Aitäh inspiratsiooni ja hanenaha eest.
Liituge meiega Facebook Ja Kokkupuutel
Matemaatikud ütlevad seda kõike kaasaegne maailm ehitatud valemitele. Kõik uskumatud tehingud, mida miljardid arvutid ja nutitelefonid iga päev teevad, põhinevad ainult neil. Matemaatik oli Alan Turing, kes andis ühe olulisema panuse arvutusmasinate loomisesse, mees, kelle elutee oli raske ja traagiline.
Me oleme sees veebisait Austame Alan Turingi teeneid ja usume, et kõik peaksid teadma selle mehe ajalugu, ilma kelleta oleks kaasaegne maailm olnud täiesti teistsugune.
Alan Matheson Turing sündis Londoni kliinikus 23. juunil 1912. aastal. Temast sai iidsetest aadliperekondadest pärit Julius ja Ethel Turingi pere teine poeg. Alani isa oli riigiametnik ning osana oma teenistusest tema ja ta naine enamus veetis aega Indias. Et anda poisile võimalus Inglismaal õppida, jätsid nad ta ja oma vanema poja Johni pensionil koloneli ja tema naise hoolde.
Juba esimestest eluaastatest oli selge, et Alan on äärmiselt andekas laps. 6. eluaastaks oli ta õppinud iseseisvalt lugema ja palus oma eestkostjatel anda talle teaduslikke raamatuid ning 11. eluaastaks tegi ta keemilisi katseid, püüdes näiteks merevetikatest joodi eraldada. Ühel päeval, kui Alan oma vanematega aega veetis, sai ta teeks metsikut mett: poiss jälgis mitme mesilase lennutrajektoori, leidis ristumiskoha, kust avastati nende pesa.
14-aastaselt astus Alan mainekasse kooli, kus õppisid aristokraatlikest peredest pärit poisid. Tema edu oli aga väga kahtlane: enamik humanitaaraineid teda ei huvitanud ja klassiajakirja vaadates on näha, et peaaegu kõigis ainetes oli ta klassi viimane õpilane. Peale matemaatika – siin oli Alan peaaegu alati esikohal.
Ta tegeles ka spordiga. Seega meeldis tulevasele suurele matemaatikule sõudmine ja jooksmine. Muide, jooksmine jäi talle kogu eluks: ta läbis maratonidistantse ja kavatses osaleda 1948. aasta olümpial, kuid jalavigastus takistas seda. Tema tulemused olid väga head: aeg, mille jooksul ta läbis 42 km 195 m, oli vaid 11 minutit madalam kui olümpiavõitja näitas.
Tema erakordseid matemaatilisi võimeid tõendab kõige paremini tõsiasi, et õpingute ajal mõistis ta iseseisvalt Einsteini relatiivsusteooriat ja suutis tuvastada probleeme, millest autor ise väga varjatult räägib.
Christopher Morcom.
Koolis kohtus Alan Christopher Morcomiga, noormehega, kes oli võib-olla isegi andekam kui ta ise. "Temaga võrreldes tundusid kõik teised nii tavalised," kirjutas Turing. Noored veetsid palju aega koos, vesteldes teadusest ja tehes erinevaid katseid – Alan leidis lõpuks hingesugulase ja vabanes aastatepikkusest üksindustundest. Nad kandideerisid koos Cambridge'i, kuid erinevalt Christopherist Alanit vastu ei võetud ja ta otsustas uuesti proovida koos sõbraga õppida.
Kuid plaanid ei olnud määratud täituma: Christopher Morcom suri ootamatult tuberkuloosi. Alani jaoks oli see tugev löök; ta sukeldus pikaks depressiooniks, kuid leidis jõudu Cambridge'i sisenemiseks. Alan oli veendunud, et peab tegutsema, et kindlasti teha kõik avastused, mis Christopher oleks tema sõnul pidanud tegema. Juba ülikoolis õppides palus ta proua Morcomilt oma poja fotot, mille ta seejärel oma lauale asetas. "Nüüd seisab ta mu laual ja julgustab mind kõvasti tööd tegema," kirjutas Alan oma surnud sõbra emale.
Just Morcomi surm ajendas Turingit mõtlema inimmõistuse olemusele ja selle "ühendamisele" millekski kehatuks ja seega surematuks. Meenutab mulle arvutit, kas pole?
Rekonstrueeritud "Pomm".
2 aastat pärast Cambridge'i ülikooli lõpetamist, 1936. aastal, avaldas Turing oma kuulsaima teose "Arvutatavatest numbritest koos lahendatavuse probleemiga", mis kirjeldas arvuti prototüübi "Turingi masina" kontseptsiooni. Rääkimine lihtsate sõnadega, lõi ta abstraktse arvutusmasina, mis suudab lahendada kõik tehisintellektile kättesaadavad probleemid - peate lihtsalt määrama konkreetse programmi. Nii lihtsalt kui võimalik: see, et tänapäeval saame kasutada sama kiipi näiteks nutitelefonis ja külmkapis, on samuti Turingi teene.
Alan Turingi mõistuse võimsuse kujutlemiseks tasub mõelda sellele, et ta ehitas peaaegu kogu tänapäevaste arvutite, sealhulgas kõige võimsamate, tööpõhimõtte täielikult oma peas.
Ka 1936. aastal kutsus Princetoni ülikooli (USA) professor John von Neumann, kelle loomingut Alan veel tudengina õppis ja kelle nimi on arvutite loomisega lahutamatult seotud, noore teadlase praktikale. Muide, hoolimata sellest, et von Neumanni peetakse traditsiooniliselt kaasaegsete elektrooniliste arvutite isaks, tunnistas ta ise, et nende põhikontseptsioon kuulus Alan Turingile.
Turing töötas Princetonis 2 aastat ja sai doktorikraadi, kuid kui talle pakuti iseseisvat kohta, keeldus ta ja naasis Inglismaale oma alma mater'i. Aasta oli siis 1938. Aasta hiljem, 1. septembril 1939, algas Teine maailmasõda.
Alan Turingi monument Bletchley pargis.
"Ma ei taha öelda, et võitsime sõja tänu Turingile, kuid võtan endale vabaduse öelda, et ilma temata oleksime võinud selle kaotada."
I. Goode, Alan Turingi kolleeg
Kolm päeva pärast sõja algust asus Alan Turing tööle Briti luure salaüksusesse Bletchley Park. Turingi juhitud teadlaste rühma jõupingutustega murti kuus kuud hiljem lahti Enigma kood, krüpteerimismasin, mida Saksa väejuhatus kasutas salajaste sõnumite edastamiseks.
1941. aastal tegi Alan oma Bletchley Parki kolleegile Joan Clarke'ile abieluettepaneku, kuid mõne aja pärast tunnistas ta naisele oma homoseksuaalsust ja noored katkestasid pulma.
Üldiselt peeti Turingit oma kolleegide seas ekstsentrikuks. Iga aasta juunis haigestus ta heinapalavikusse ja sõitis rattaga tööle gaasimaskiga. Jalgratta kett kukkus pidevalt maha, kuid selle asemel, et seda parandada, leidis Turing originaalne lahendus: ta arvutas välja pöörete arvu, mille järel see juhtus, ja enne, kui kett oli kukkumas, peatus ja reguleeris seda. Lisaks ei austanud ta kolleege kordagi tervitamisega, pidades seda ajaraiskamiseks ning pani oma kruusi käeraudadega radiaatori külge, et seda ära ei varastataks.
1942. aastal naasis Turing USA-sse, kus muu hulgas töötas ta Roosevelti ja Churchilli vaheliste sõnumite edastamise šifri kallal. 1943. aastal naasis ta Bletchley Parki, kuid avastas, et tema äraolekul oli osakonna üle võtnud teine inimene. Turing jäi konsultandiks, kuid kõik tema mõtted olid nüüd hõivatud masina ehitamisega, mis oleks võimeline inimest asendama – ehk teisisõnu kaasaegne keel, arvuti.
1945. aastal ilmus USA-s von Neumanni tollal pooleli jäänud teos, mis kirjeldas arvuti disaini koos mällu salvestatud programmiga. Veidi hiljem avaldas Alan Turing sarnase, kuid palju üksikasjalikuma teose - muide, Turingi enda ideid kasutati von Neumanni materjalis. Hoolimata asjaolust, et "arvuti" ehitamine oli tehniliselt täiesti võimalik, ei tehtud seda kunagi Bletchley Parki salastatusega seotud viivituste tõttu.
Maja, kus Alan Turing veetis oma viimased aastad.
1950. aastal avaldas Turing arvutiajaloo ühe olulisema uurimuse Computing Machines and Minds, kus ta rääkis tehisintellekt. Seal pakkus ta välja eksperimendi, mille käigus inimene pidi suhtlema “targa masina” ja elava inimesega ning seejärel tegema kindlaks, kes on kes. Muide, selle katse põhjal ja loodi midagi, mida teavad tänapäeval iga Interneti-kasutaja: Captcha on sama "kaitsja", mis palub teil kinnitada, et te pole robot.
Turingi "pliiats" kuulub ka esimesse arvutimaleprogrammi, mille ta kirjutas juba enne arvutite endi tulekut. Selle rakendamiseks viis ta läbi eksperimendi, kus ta ise jäljendas selle tegevust, tehes iga poole tunni järel ühe liigutuse - selle tulemusel võitis “arvuti” ühe mängu ja kaotas ühe.
Pealegi võib just Turingit pidada arvutimuusika loojaks. 1951. aastal suutis tema loodud masin genereerida 3 meloodiat, sealhulgas kuulsa Glenn Milleri "In the Mood". See aga unustati täielikult kuni aastani 2016, mil taasloodi 65 aastat vana salvestis.Alan sai valida vangistuse ja hormoonravi – sisuliselt keemilise kastreerimise – vahel. Ta valis viimase.
Lisaks hormoonsüstidest põhjustatud tervisekahjustustele (mille tagajärjel muutus teadlase psüühika ebastabiilseks ja tekkisid erinevad haigused) oli menetluse tagajärjeks töökaotus. Ja enne seda sai mitte eriti seltskondlikust teadlasest tõeline erak ja püüdis suurema osa ajast kodus veeta.
Alan Turingi monument Manchesteris.
8. juuni hommikul 1954 leiti Alan Turing oma voodist surnuna. Neiu avastas ta. Surma põhjuseks oli tsüaniidimürgitus. Öökapil oli hammustatud õun ja kuigi seda ei uuritud, arvatakse, et selle mürgitas Turing ise.
Turingi kohta käiva biograafilise raamatu autor Andrew Hodges, millel põhines film The Imitation Game with Benedict Cumberbatch, jõudis järeldusele, et Alan mängis stseeni Disney Lumivalgekesest, tema lemmikmultikast. Muideks, On olemas teooria, et Apple'i logo ilmus just Turingi surma põhjustanud õuna tõttu.
Siiski on arvamus, et see ei olnud enesetapp. Alates noorusest mängis Turing enda leiutatud mängu “Kõrbesaar”, mille eesmärk oli “kaevandada” erinevatest toodetest keemilisi elemente. Turing oli kemikaale käsitledes väga hooletu, nii et paljud, sealhulgas tema ema Sarah, uskusid ja usuvad siiani, et tema surm oli õnnetus. Ema sõnul suhtus teadlane aasta tagasi lõppenud teraapiasse teatava huumoriga ja oli üldiselt sees hea tuju. On veel üks versioon: Turing teeskles tahtlikult juhuslikku surma, et mitte oma ema häirida.
Ühel või teisel viisil katkes 20. sajandi ühe suurima teadlase elu, kui ta polnud veel 42-aastanegi. 2009. aastal avaldas Briti peaminister avaliku vabanduse Alan Turingi tagakiusamise pärast ning 2013. aastal andis kuninganna Elizabeth II talle postuumselt armu.
Ütleme nii, et ammu... Aga tegelikult loodi enne Turingi masina loomist masinad erinevate toimingute tegemiseks. Näiteks peate võtma logaritmi, noh, ehitame masina, mis loeb arvu ja võtab logaritmi. Või peate näiteks liitma kaks numbrit – siin on masin kahe numbri lisamiseks. Ja isegi praegu on selliseid masinaid, näiteks kalkulaatorid. Mis nad teha saavad? Liitmine, lahutamine, korrutamine ja konstrueerimine – võtke isegi koosinus või siinus. Selgub, et need lollid masinad ei osanud ega oskagi teha muud peale nendesse salvestatud toimingute.
Seega oleks väga huvitav luua masin, mis ei loeks numbreid ega sümboleid, vaid algoritmi ning täidaks selle ehk looks programmeeritava masina. Seda tegi Turing (ma ütlen, et lisaks Turingi omadele on palju selliseid abstraktsioone). Ja ta mõtles välja sellise masina mudeli. Selgus, et keeruliste algoritmide täitmiseks on vaja ainult kelku, lõputut linti ja võimalust muuta lindile kirjutatud väärtusi ja liikuda mööda seda. Selgub, et sellest abstraktsioonist saab tegelikult teha päris masina, ainsaks piiranguks on see, et me ei saa anda masinale lõputut linti, küll aga saame teha väga pika lindi;)
Taganeda. Tegelikult pole vaja öelda, kuidas Turingi masin töötab, nagu ma juba ütlesin, on see väga lihtne leida. Seetõttu eeldame, et teate juba, kuidas see töötab.
Noh, Turingi masin täidab mõningaid lihtsaid algoritme, see on vaieldamatu. Aga kuidas on lood keerukatega? Ja näiteks kuidas korraldaksite tsüklit kasutades MT-d? Või kuidas hargnemist aru saada? Selgub, et on teoreeme, mis tõestavad, et MT suudab sooritada silmuseid ja harusid, mis ütleb meile, et väga lihtsa mehhanismiga on võimalik koostada programme lihtsatest plokkidest nagu harud ja tsüklid, mis tähendab, et kõike, mida saab programmeerida, saab olema programmeeritud. Ja siin peaks teoreetiliselt olema seletus, et on ka arvutamatuid funktsioone ja seega ka lahendamatuid probleeme ja neid probleeme ei saa MT abil lahendada. Siin on, kuidas.
Kuid keegi pole Turingi masinast lahedamat välja mõelnud, nii et kõik programmeerimiskeeled, mida me praegu kasutame, ei suuda programmeerida rohkem kui Turingi masin. Siit pärineb Turingi täielikkuse mõiste, mis tähendab, et keel (või mis tahes muu) on Turingi täielik, kui sellesse saab kirjutada kõik Turingi masinal töötavad algoritmid. Ja saate tõestada, et keel on Turingi täielik, kirjutades sellesse Turingi masina emulaatori. Need on pirukad.
Matemaatilisest vaatenurgast on postitus jama, kuid on selge, miks meil oli Turingi masinat vaja. Tegelikult on selle masina algoritmide kirjutamine huvitav mõistatus. Usun neid, kes ütlevad, et pärast exp(x) programmeerimist Turingi masinal sai ta tõesti aru, mis on algoritm. Ma pole seda veel proovinud, kuid see on huvitav probleem.
Pärast 1920. aastaid väljend Arvutusmasin viitab mis tahes masinatele, mis töötasid inimene-arvuti, eriti need, mis on välja töötatud kooskõlas tõhusad meetodid Church-Turingi väitekiri. See väitekiri on sõnastatud järgmiselt: “Iga algoritmi saab määrata vastava Turingi masina või osaliselt rekursiivse definitsiooni kujul ning arvutatavate funktsioonide klass langeb kokku osaliselt rekursiivsete funktsioonide klassiga ja Turingi masinatel arvutatavate funktsioonide klassiga. .” Teisel viisil defineeritakse Church-Turingi teesi hüpoteesina mehaaniliste arvutusseadmete, näiteks elektrooniliste arvutite olemuse kohta. Kõiki võimalikke arvutusi saab teha arvutis, eeldusel, et sellel on piisavalt aega ja salvestusruumi.
Lõpmatustega arvutustega töötavaid mehhanisme hakati nimetama analoogtüübiks. Väärtused sellistes mehhanismides esitati pidevate arvväärtustena, näiteks võlli pöördenurk või erinevus elektriline potentsiaal.
Erinevalt analoogmasinatest oli digitaalsetel masinatel võimalus esitada arvväärtuse olekut ja salvestada iga numbrit eraldi. Digitaalsed masinad kasutasid enne muutmäluseadme leiutamist erinevaid protsessoreid või releesid.
Nimi Arvutusmasin alates 1940. aastatest hakati seda asendama mõistega arvuti. Need arvutid suutsid teha arvutusi, mida ametnikud olid varem teinud. Kuna väärtused peatusid sõltuvalt füüsilised omadused(nagu analoogmasinatel) suutis digitaalsel riistvaral põhinev loogiline arvuti teha kõike, mida kirjeldada annab puhtalt mehaaniline süsteem .
Turingi masinad kavandati formaalselt matemaatiliselt määratlema, mida saab arvutada, arvestades arvutusvõimsuse piiranguid. Kui Turingi masin suudab ülesande täita, loetakse ülesanne Turingi arvutatavaks. Turing keskendus peamiselt masina kujundamisele, mis suudaks määrata, mida saab arvutada. Turing jõudis järeldusele, et seni, kuni eksisteerib Turingi masin, mis suudab arvule ligikaudse arvu arvutada, on see väärtus loendatav. Lisaks saab Turingi masin tõlgendada loogilisi operaatoreid, nagu AND, VÕI, XOR, NOT ja If-Then-Else, et teha kindlaks, kas
