Sanotaanpa, kauan sitten... Mutta itse asiassa ennen Turingin koneen luomista luotiin koneita suorittamaan erilaisia ​​toimintoja. Esimerkiksi sinun on otettava logaritmi, no, niitataanpa kone, joka lukee luvun ja ottaa logaritmin. Tai esimerkiksi sinun täytyy lisätä kaksi numeroa - tässä on kone kahden numeron lisäämiseen. Kyllä, ja nyt on olemassa sellaisia ​​​​koneita, esimerkiksi laskimia. Mitä he voivat tehdä? Lisää, vähennä, kerro ja muokkaa – ota vaikka kosini tai sini. Osoittautuu, että nämä typerät koneet, lukuun ottamatta niihin tallennettuja toimia, eivät pystyneet eivätkä voi suorittaa mitään.

Joten olisi erittäin mielenkiintoista luoda kone, joka ei lukisi numeroita tai symboleja, vaan algoritmin ja suorittaisi sen, eli luo ohjelmoitavan koneen. Näin Turing teki (väitän, että tällaisia ​​abstraktioita on monia Turingin lisäksi). Ja hän keksi tällaisen koneen mallin. Kävi ilmi, että monimutkaisten algoritmien suorittamiseen tarvitset vain välilevyn, loputtoman nauhan ja mahdollisuuden muuttaa nauhalle kirjoitettuja arvoja ja liikkua sitä pitkin. Osoittautuu, että tämä abstraktio voidaan itse asiassa muuttaa todelliseksi koneeksi, ainoa asia sillä rajoituksella, että emme voi tarjota koneelle loputonta nauhaa, mutta voimme tehdä erittäin pitkän nauhan;)

Vetäytyä. Itse asiassa Turingin koneen toimintaa ei tarvitse kertoa, kuten sanoin, se löytyy erittäin helposti. Siksi oletamme, että tiedät jo, kuinka se toimii.

No, Turingin kone suorittaa joitain yksinkertaisia ​​algoritmeja, tämä on kiistatonta. Mutta entä monimutkaiset? Ja esimerkiksi kuinka järjestää sykli MT:n avulla? Tai miten haaroittuminen selviää? Osoittautuu, että on olemassa lauseita, jotka osoittavat, että MT voi suorittaa silmukoita ja haaroja, mikä kertoo meille, että hyvin yksinkertaisella mekanismilla voit koota ohjelmia yksinkertaisista lohkoista, kuten haaroista ja silmukoista, mikä tarkoittaa, että voit ohjelmoida kaiken mitä voidaan ohjelmoitu. Ja tässä teoriassa pitäisi olla selitys, että on olemassa myös ei-laskettavia funktioita ja siten ratkaisemattomia ongelmia, joita ei voida ratkaista MT:n avulla. Näin

Mutta kukaan ei ole keksinyt mitään hienompaa kuin Turingin kone, joten kaikki tällä hetkellä käyttämämme ohjelmointikielet voivat ohjelmoida vain Turingin konetta. Tästä tuli Turingin täydellisyyden käsite, mikä tarkoittaa, että kieli (tai jokin muu) on Turing-valmis, jos se pystyy kirjoittamaan kaikki Turingin koneella toimivat algoritmit. Ja voit todistaa, että kieli on Turing-valmis kirjoittamalla siihen Turingin koneemulaattorin. Nämä ovat piirakat.

Matematiikan näkökulmasta postaus on paskapuhetta, mutta on selvää, mitä varten tarvitsimme Turingin koneen. No, itse asiassa algoritmien kirjoittaminen tälle koneelle on mielenkiintoinen pulma. Uskon niitä, jotka sanovat, että ohjelmoituaan exp(x):n Turingin koneella hän todella ymmärsi mikä algoritmi on. En ole vielä kokeillut, mutta se on mielenkiintoinen haaste.

Turingin kone on kokoelma seuraavia objekteja

• 1) ulkoinen aakkoset A=(a 0 , a 1 , …, a n );
• 2) sisäinen aakkoset Q=(q 1 , q 2 ,…, q m ) - joukko tiloja;
• 3) joukko ohjausmerkkejä (P, L, S)
• 4) molempiin suuntiin päättymätön nauha, joka on jaettu soluihin, joista jokainen voi sisältää vain yhden merkin aakkosesta A milloin tahansa erillisenä aikana;
• 5) ohjauslaite, joka voi olla jossakin monista tiloista

Tyhjän solun symboli on ulkoisen aakkoston kirjain 0 .

Tiloista erotetaan alku q 1, jossa kone alkaa toimia, ja loppu (tai pysäytystila) q 0, jolloin kone pysähtyy.

Ohjauslaite voi liikkua nauhalla vasemmalle ja oikealle, lukea ja kirjoittaa nauhan soluihin aakkosten kirjaimia A. Ohjauslaite toimii komentojen mukaan, jotka ovat seuraavan muotoisia

q i a j > a p X q k

Tallennus tarkoittaa seuraavaa: jos ohjauslaite on tilassa q i ja katseltavaan soluun kirjoitetaan kirjain a j, niin (1) soluun kirjoitetaan p j:n sijaan, (2) kone siirtyy tarkastelemaan seuraava oikea solu juuri katsotusta solusta, jos X=P, tai katsoaksesi seuraavaa vasenta solua, jos X=L, tai jatkaaksesi saman nauhasolun katselua, jos X=C, (3) ohjauslaite tulee tila q k.

Koska koneen toiminta ehdon mukaan määräytyy täysin sen tilan q tietyllä hetkellä ja sillä hetkellä katsottavan solun sisällön a perusteella, on kullekin mahdolliselle konfiguraatiolle q i a j täsmälleen yksi sääntö. Ei ole olemassa sääntöjä vain lopputilalle, jossa kone pysähtyy. Siksi Turingin koneohjelma, jossa on ulkoinen aakkosto A=(a0, a1, …, an) ja sisäinen aakkosto Q=(q1, q2,…, qm), sisältää enintään m (n+ 1) käskyä.

Aakkosten A tai aakkosten Q tai aakkosten A Q sana on mikä tahansa vastaavan aakkoston kirjainsarja. K:nnen konfiguraation alla tarkoitamme koneen nauhan kuvaa, jossa on siihen kehittynyt tieto k:nnen vaiheen alkuun mennessä (tai nauhalle kirjoitettua aakkosten A sanaa k. vaihe), joka kertoo mitä solua tässä vaiheessa tarkastellaan Ja missä kunnossa auto on? Vain äärellisissä konfiguraatioissa on järkeä, ts. ne, joissa kaikki nauhan solut, mahdollisesti äärellistä lukua lukuun ottamatta, ovat tyhjiä. Kokoonpanon sanotaan olevan lopullinen, jos koneen tila on lopullinen.

Jos jokin Turingin koneen ei-lopullinen konfiguraatio valitaan alkuperäiseksi, niin koneen tehtävänä on peräkkäin (askel askeleelta) muuttaa alkuperäinen konfiguraatio koneohjelman mukaan, kunnes lopullinen konfiguraatio on saavutettu. Tämän jälkeen Turingin koneen työ katsotaan valmistuneeksi ja työn tuloksena on saavutettu lopullinen konfiguraatio.

Sanotaan, että aakkosissa A (а 0 ) = (a 1 , ..., a n ) olevan ei-tyhjän sanan b kone havaitsee vakioasennossa, jos se kirjoitetaan nauhan peräkkäisiin soluihin, kaikki muut solut ovat tyhjiä ja kone skannaa vasemman tai oikeanpuoleisimman solun soluista, joissa sana b on kirjoitettu. Vakiosijaintia kutsutaan alku (lopullinen), jos kone, joka havaitsee sanan vakioasennossa, on alkutilassa q 1 (vastaavasti pysäytystilassa q 0).

Jos sanan b käsittely vie Turingin koneen lopulliseen tilaan, niin sen sanotaan pätevän b:hen, muuten se ei päde sanaan b (kone toimii loputtomasti)

Harkitse esimerkkiä:

Annettu Turingin kone, jossa on ulkoinen aakkoset A \u003d (0, 1) (tässä 0 on tyhjän solun symboli), sisäisten tilojen aakkoset Q \u003d (q 0, q 1, q 2 ) ja seuraavat toiminnallinen kaavio (ohjelma):

q 1 0 > 1 L q 2;

q 1 1 > 0 С q 2;

q 2 0 > 0 П q 0;

q 2 1 > 1 C q 1;

Tämä ohjelma voidaan kirjoittaa taulukon avulla

Ensimmäisessä vaiheessa komento toimii: q 1 0 > 1 Л q 2 (ohjauslaite on q1-tilassa ja valvottavaan soluun kirjoitetaan kirjain 0, soluun kirjoitetaan 1 0:n sijaan, pää siirretään vasemmalle, ohjauslaite siirtyy q2-tilaan), in Tämän seurauksena koneeseen luodaan seuraava konfiguraatio:

Lopuksi komennon q 2 0 > 0 P q 0 suorittamisen jälkeen luodaan konfiguraatio

Tämä konfiguraatio on lopullinen, koska kone on pysäytystilassa q 0 .

Näin ollen kone käsittelee alkuperäisen sanan 110 sanaksi 101.

Tuloksena oleva konfiguraatiosarja voidaan kirjoittaa lyhyemmällä tavalla (valvotun solun sisältö kirjoitetaan sen tilan oikealle puolelle, jossa kone tällä hetkellä sijaitsee):

11q 1 0 => 1 q 2 11 => 1 q 1 11 => 1 q 2 01 => 10 q 0 1

Turingin kone ei ole muuta kuin jokin sääntö (algoritmi) aakkosten A Q sanojen muuntamiseksi, ts. kokoonpanot. Näin ollen Turingin koneen määrittelemiseksi on määriteltävä sen ulkoinen ja sisäinen aakkoset, ohjelma ja osoitettava, mikä symboleista ilmaisee tyhjää solua ja lopullista tilaa.

Turingin kone on yksi 1900-luvun kiehtovimmista ja jännittävimmistä älyllisistä löydöistä. Se on yksinkertainen ja hyödyllinen abstrakti laskentamalli (tietokone ja digitaalinen), joka on riittävän yleinen minkä tahansa tietokonetehtävän toteuttamiseen. Yksinkertaisen kuvauksensa ja matemaattisen analyysinsä ansiosta se muodostaa teoreettisen tietojenkäsittelytieteen perustan. Tämä tutkimus on johtanut digitaalisten tietokoneiden ja laskennan syvempään ymmärtämiseen, mukaan lukien oivallukseen, että on joitakin laskennallisia ongelmia, joita ei voida ratkaista yleisten käyttäjien tietokoneilla.

Alan Turing pyrki kuvaamaan primitiivisimmän mallin mekaanisesta laitteesta, jolla olisi samat perusominaisuudet kuin tietokoneella. Turing kuvasi koneen ensimmäisen kerran vuonna 1936 "On Computable Numbers with an Application to the Decidability Problem", joka ilmestyi Proceedings of the London Mathematical Society -julkaisussa.

Turingin kone on tietokonelaite, joka koostuu luku-/kirjoituspäästä (tai "skannerista"), jonka läpi kulkee paperiteippi. Nauha on jaettu neliöihin, joista jokaisessa on yksi symboli - "0" tai "1". Mekanismin tarkoitus on, että se toimii sekä sisään- ja poistumiskeinona että työmuistina laskennan välivaiheiden tulosten tallentamiseen. Mistä laite koostuu Jokainen tällainen kone koostuu kahdesta osasta: Rajoittamaton teippi. Se on ääretön molempiin suuntiin ja on jaettu soluihin. Kone on ohjattu ohjelma, skanneripää tietojen lukemiseen ja kirjoittamiseen. Se voi olla jossakin monista tiloista milloin tahansa.

Jokainen kone linkittää kaksi äärellistä datasarjaa: syöttösymbolien aakkoset A = (a0, a1, ..., am) ja tilojen aakkosten Q = (q0, q1, ..., qp). Tilaa q0 kutsutaan passiiviseksi. Uskotaan, että laite lopettaa toimintansa osuessaan siihen. Tilaa q1 kutsutaan alkutilaksi - kone aloittaa laskelmansa ollessaan siinä alussa. Syötesana sijoitetaan nauhalle yksi kirjain peräkkäin kuhunkin kohtaan. Sen molemmilla puolilla on vain tyhjiä soluja.

Kuinka mekanismi toimii

Turingin koneella on perustavanlaatuinen ero tietokoneisiin verrattuna - sen tallennuslaitteessa on ääretön nauha, kun taas digitaalisissa laitteissa tällaisessa laitteessa on tietyn pituinen nauha. Kukin tehtäväluokka ratkaistaan ​​vain yhdellä rakennetulla Turingin koneella. Erityyppisiin tehtäviin kuuluu uuden algoritmin kirjoittaminen. Ohjauslaite voi yhdessä tilassa liikkua mihin tahansa suuntaan nauhaa pitkin. Se kirjoittaa soluihin ja lukee niistä viimeisten aakkosten merkit. Siirron aikana varataan tyhjä elementti, joka täyttää ne paikat, jotka eivät sisällä syöttötietoja. Turingin koneen algoritmi määrittelee ohjauslaitteen siirtymäsäännöt. He asettavat seuraavat parametrit kirjoitus-lukupäälle: kirjoita uusi merkki soluun, siirtyy uuteen tilaan, siirry vasemmalle tai oikealle nauhaa pitkin.

Liikkeen ominaisuudet

Turingin koneella, kuten muillakin laskentajärjestelmillä, on omat ominaisuutensa, ja ne ovat samanlaisia ​​kuin algoritmien ominaisuudet: Diskreettisyys. Digitaalinen kone siirtyy seuraavaan vaiheeseen n+1 vasta, kun edellinen on suoritettu. Jokainen suoritettu vaihe määrittää, mikä n+1 on. Selkeys. Laite suorittaa vain yhden toiminnon samalle solulle. Se syöttää merkin aakkosista ja tekee yhden liikkeen: vasemmalle tai oikealle. Päättäväisyys. Jokainen mekanismin asento vastaa tietyn järjestelmän ainoaa muunnelmaa, ja jokaisessa vaiheessa toiminnot ja niiden suoritusjärjestys ovat yksiselitteisiä. Tehokkuus. Jokaisen vaiheen tarkan tuloksen määrittää Turingin kone. Ohjelma suorittaa algoritmin ja siirtyy äärellisessä määrässä vaiheita tilaan q0. Massahahmo. Jokainen laite on määritelty aakkoston sallittujen sanojen päälle. Turingin koneen funktiot Algoritmeja ratkaistaessa on usein tarpeen toteuttaa funktio. Riippuen mahdollisuudesta kirjoittaa ketju laskentaa varten, funktiota kutsutaan algoritmisesti ratkaistavaksi tai ratkaisemattomaksi. Luonnollisten tai rationaalilukujen joukona, sanoja äärellisissä aakkosissa N koneelle, tarkastellaan joukon B sekvenssiä - sanat binäärikoodiaakkoston B=(0.1) puitteissa. Lisäksi laskennan tulos ottaa huomioon "määrittelemättömän" arvon, joka syntyy, kun algoritmi "jäätyy". Toiminnon toteuttamiseksi on tärkeää, että äärellisissä aakkosissa on muodollinen kieli ja että oikeiden kuvausten tunnistamisen ongelma on ratkaistavissa.

Laitteen ohjelmisto

Turing-mekanismin ohjelmat on järjestetty taulukoihin, joissa ensimmäinen rivi ja sarake sisältävät ulkoisen aakkoston symbolit ja automaatin mahdollisten sisäisten tilojen arvot - sisäiset aakkoset. Taulukkotiedot ovat komentoja, jotka Turingin kone hyväksyy. Ongelmanratkaisu etenee näin: sen yläpuolella olevan solun pään lukema kirjain ja automaatin pään sisäinen tila määrää, mitkä komennot on suoritettava. Tarkemmin sanottuna tällainen komento sijaitsee taulukossa olevien ulkoisten aakkosten ja sisäisen symbolien leikkauskohdassa.

Komponentit laskelmia varten

Turingin koneen rakentamiseksi yhden tietyn ongelman ratkaisemiseksi on tarpeen määritellä sille seuraavat parametrit. ulkoinen aakkoset. Tämä on jokin äärellinen symbolijoukko, joka on merkitty merkillä A, jonka osatekijöitä kutsutaan kirjaimilla. Yhden niistä - a0 - on oltava tyhjä. Esimerkiksi binääriluvuilla työskentelevän Turing-laitteen aakkoset näyttävät tältä: A = (0, 1, a0). Nauhalle tallennettua jatkuvaa kirjainten-symbolien ketjua kutsutaan sanaksi. Automaatti on laite, joka toimii ilman ihmisen väliintuloa. Turingin koneessa sillä on useita eri tiloja ongelmien ratkaisemiseksi ja se siirtyy tietyissä olosuhteissa paikasta toiseen. Tällaisten kuljetustilojen joukko on sisäinen aakkoset. Hänellä on kirjainmerkintä muotoa Q=(q1, q2...). Yhden näistä paikoista - q1 - on oltava ensimmäinen, eli se, joka käynnistää ohjelman. Toinen vaadittu elementti on tila q0, joka on lopullinen tila, eli se, joka lopettaa ohjelman ja siirtää laitteen pysäytysasentoon.

Hyppypöytä.

Tämä komponentti on algoritmi laitevaunun toiminnalle, joka riippuu koneen nykyisestä tilasta ja luettavan merkin arvosta.

Algoritmi automaatille

Turing-laitteen kuljetusta käytön aikana ohjataan ohjelmalla, joka suorittaa jokaisen vaiheen aikana seuraavan toimintosarjan: Ulkoisen aakkoston merkin kirjoittaminen paikkaan, mukaan lukien tyhjä, siinä olevan elementin korvaaminen, mukaan lukien tyhjä. Siirrä yksi askel-solu vasemmalle tai oikealle. Muuta sisäistä tilaasi. Näin ollen kirjoitettaessa ohjelmia jokaiselle merkkiparille tai paikalle on tarpeen kuvata tarkasti kolme parametria: ai - elementti valitusta aakkosesta A, vaunun siirron suunta ("←" vasemmalle, "→" oikea, "piste" - ei liikettä) ja qk - laitteen uusi tila Esimerkiksi komennon 1 "←" q2 arvo on "korvaa merkki 1:llä, siirrä vaunun päätä vasemmalle yksi askelsolu ja hyppää tilaan q2".

Ratkaisemme usein erilaisia ​​​​monimutkaisia ​​​​ongelmia: arkipäiväisiä, matemaattisia jne. Jotkut ovat helppoja ratkaista, jotkut vaativat paljon ajattelua, ja joihinkin emme koskaan löydä ratkaisua.

Yleisessä tapauksessa ongelman ratkaisumenetelmä (jos sellainen on) voidaan kuvata käyttämällä äärellistä määrää perustoimintoja.

Esimerkiksi toisen asteen yhtälön ratkaiseminen:

1. Muunna yhtälö kanoniseen muotoon \(a x^2 + b x + c = 0\)
2. Jos \(a=0\) , niin tämä lineaarinen yhtälö ratkaisulla \(x=\frac(-c)(b)\) . Ongelma ratkaistu. Muussa tapauksessa siirry vaiheeseen 3.
3. Laske diskriminantti \(D=b^2-4 a c\)
4. Laske yhtälöratkaisut \(x_(1,2) = \frac(-b\pm\sqrt(D))(2 a)\). Ongelma ratkaistu.

Voimme ottaa käyttöön seuraavan intuitiivisen käsityksen algoritmista:

Algoritmi on joukko ohjeita, jotka kuvaavat toimenpiteen, jolla suorittaja saavuttaa ongelman ratkaisun tuloksen rajallisella määrällä toimintoja mille tahansa lähtötietojoukolle.

Tämä ei tietenkään ole tiukka määritelmä, mutta se kuvaa algoritmin käsitteen olemusta.

Algoritmit kootaan tietyn perusteella esiintyjä, ja siksi sen on oltava kielellä, jota esiintyjä ymmärtää.

Algoritmin toteuttaja voi olla henkilö tai se voi olla tietokone tai jokin muu automaatti, esimerkiksi kangaspuut.

Seuraavat algoritmien ominaisuudet erotetaan:

Algoritmin diskreettisyyden tulisi olla tietty sarja erillisiä, hyvin määriteltyjä vaiheita (toimintoja). Jokaisen näistä toimista on oltava ajallisesti rajallinen. Määrittävyys algoritmin jokaisessa vaiheessa, seuraava vaihe määräytyy yksiselitteisesti järjestelmän nykyisen tilan mukaan. Tämän seurauksena samoilla lähtötiedoilla algoritmi palauttaa aina samat tulokset riippumatta siitä, kuinka monta kertaa se suoritetaan. Ymmärrettävyys Algoritmi tulee muotoilla esittäjän ymmärtämällä kielellä. Jos me puhumme tietokoneesta algoritmin tulee käyttää vain niitä komentoja, jotka tietokone tuntee ja joiden toimintojen tulos on tiukasti määritelty. Äärillisyys Algoritmin on suoritettava loppuun äärellinen määrä vaiheita. Algoritmin massamerkin tulee olla sovellettavissa erilaisiin syöttötietosarjoihin. Toisin sanoen algoritmin tulee olla ratkaisuun sopiva luokkaa tehtäviä. Palaten toisen asteen yhtälön esimerkkiin, algoritmi soveltuu ratkaisemiseen kaikki toisen asteen yhtälöitä, ei vain yhtä tai useampaa. Algoritmin on päätyttävä tiettyyn tulokseen. Sanotaan, että ratkaisemalla ongelman tai selvittämällä ratkaisujen puuttuminen. Jos algoritmi ei johda tulokseen, ei ole selvää, miksi sitä ylipäänsä tarvitaan.

Jokainen tapa ratkaista ongelma ei ole algoritmi. Oletetaan, että algoritmi ei tarkoita vaihtoehtoa. Esimerkiksi useimmat reseptejä ne eivät ole algoritmeja, koska ne käyttävät lauseita, kuten "lisää suolaa maun mukaan". Tämän seurauksena determinismin vaatimusta rikotaan.

Jokaiselle ongelmalle, johon on ratkaisu, ei ole olemassa myös ratkaisualgoritmi. Esimerkiksi kuvantunnistuksen ongelma on edelleen suurelta osin ratkaisematta, eikä todellakaan tiukan algoritmin avulla. Hermoverkkojen käyttö antaa kuitenkin varsin hyviä tuloksia.

Yleensä algoritmille on joukkoja hyväksyttäväksi syötetiedot. Olisi outoa yrittää soveltaa yhtälönratkaisualgoritmia illallisen keittämiseen tai päinvastoin.

Lisäksi toimeenpanijan mahdollisten toimien joukko on myös rajoitettu, koska jos jokin toiminta olisi sallittua, niin niiden joukossa tulisi olla myös "hylättyjä".

Algoritmin tiukka määritelmä

Yllä annettu algoritmin määritelmä ei ole tiukka. Tämä aiheuttaa joitain vaikeuksia. Erityisesti tällaisella määritelmällä on mahdotonta todistaa tarkasti, onko tietty ongelmaluokka ratkaistavissa algoritmilla.

Osoittautuu, että siellä on luokka algoritmisesti ratkaisemattomia ongelmia- ongelmat, joiden ratkaisemiseksi on mahdotonta luoda algoritmia. Mutta jotta algoritmin päättämättömyys voidaan tiukasti todistaa, on ensin oltava tiukka määritelmä algoritmille.

1900-luvun 20-30-luvulla useat matemaatikot työskentelivät algoritmin tiukan määrittelyn ongelman parissa, erityisesti Alan Turing, Emil Leon Post, Andrey Andreevich Markov, Andrey Nikolaevich Kolmogorov, Alonzo Church ja muut. Heidän työnsä johti lopulta algoritmien teorian, laskettavuusteorian ja erilaisten laskennan lähestymistapojen ja muuten ohjelmoinnin syntymiseen ja kehittymiseen. Yksi heidän työnsä tuloksista oli useiden algoritmien tiukkojen määritelmien syntyminen, jotka esiteltiin eri tavoin, mutta jotka vastaavat toisiaan.

Pysähdymme Turingin määritelmään yksityiskohtaisesti ja käymme läpi vastaavat Postin, Churchin ja Markovin määritelmät.

Turingin kone

Esitelläkseen algoritmin muodollisen määritelmän Turing keksi ja kuvasi abstraktin tietokoneen, jota kutsutaan Turingin tietokoneeksi tai yksinkertaisesti Turingin koneeksi.

Alan Turing (1912-1954)

Englantilainen matemaatikko, loogikko, kryptografi, kenties maailman ensimmäinen "hakkeri", seisoi tietojenkäsittelytieteen ja tekoälyteorian alkuperässä. Hän antoi merkittävän panoksen liittoutuneiden joukkojen voittoon toisessa maailmansodassa.

Turingin koneen syötteenä käytetään sanat, koottu joidenkin kanssa aakkoset, eli sarja hahmoja.

Turingin koneen tulos on myös sanoja.

Sanaa, johon algoritmia sovelletaan, kutsutaan syöttö. Sana, joka syntyy työstä viikonloppu.

Sanajoukkoa, johon algoritmia sovelletaan, kutsutaan algoritmin laajuus.

Tarkkaan ottaen on mahdotonta todistaa, että mikä tahansa esine voidaan esittää jossain aakkostossa muodostettujen sanojen muodossa - tätä varten tarvitsisimme kohteen tiukan määritelmän. Voidaan kuitenkin varmistaa, että mikä tahansa satunnaisesti valittu algoritmi, joka toimii objekteissa, voidaan muuntaa niin, että se toimii sanoilla muuttamatta algoritmin olemusta.

Turingin koneen kuvaus

Turingin koneen kokoonpano sisältää molempiin suuntiin rajoittamattoman, soluihin jaetun nauhan ja ohjauslaitteen (ns. luku/kirjoituspää tai yksinkertaisesti kone), joka voi olla jossakin monista osavaltioista. Ohjauslaitteen mahdollisten tilojen määrä on äärellinen ja tarkasti annettu.

Ohjauslaite voi liikkua nauhaa pitkin vasemmalle ja oikealle, lukea ja kirjoittaa soluihin joidenkin äärellisten aakkosten merkkejä. Erityinen tyhjä merkki, jota merkitään \(a_0\) tai \(\Lambda\) , joka täyttää kaikki nauhan solut lukuun ottamatta niitä (äärellinen luku), joille syötetiedot on kirjoitettu.

Ohjauslaite toimii siirtymäsääntöjen mukaisesti, jotka edustavat tämän Turingin koneen toteuttamaa algoritmia. Jokainen siirtymäsääntö ohjaa konetta nykyisestä tilasta ja nykyisessä solussa havaitusta symbolista riippuen kirjoittamaan uusi symboli tähän soluun, siirtymään uuteen tilaan ja siirtämään yhden solun vasemmalle tai oikealle. Jotkut Turingin koneen tilat voidaan merkitä terminaaleiksi, ja siirtyminen mihin tahansa niistä tarkoittaa työn loppua, algoritmin pysähtymistä.

Vaikka Turingin kone on abstrakti käsite, on riittävän helppoa kuvitella sellainen kone (vaikkakin rajallisella nauhalla), ja on jopa tämän kaltaisia ​​esittelykoneita:

Turingin koneen algoritmi on kätevä esittää taulukon muodossa: taulukon sarakkeet vastaavat nauhalla olevaa (havaittua) merkkiä, rivit vastaavat automaatin nykyistä tilaa ja solut tallentavat komento, joka automaatin on suoritettava.

Komennolla voi puolestaan ​​olla seuraava rakenne:

\[ a_k \vasen\lsulku \alku(matriisi) L \\ N \\ R \end(matriisi)\oikea\rsulku q_m \]

Ensin tulee aakkosten merkki, joka tulee kirjoittaa nykyiseen soluun \(a_k\) , sitten automaattin liike vasemmalle (L), oikealle (R) tai ei minnekään (pysy paikallaan, N) ilmoitettu. Lopussa ilmoitetaan uusi tila, johon automaattin \(q_m\) pitäisi mennä.

Taulukon solu määräytyy selvästi nykyisen merkin \(a_i\) ja automaatin nykyisen tilan \(q_j\) perusteella.

Sovitaan, että työn alussa Turingin kone on mukana alkutila, merkitty \(q_1\) , ja siirryttäessä kohtaan pysäytystila\(q_0\) algoritmi on valmis ja kone pysähtyy.

Esimerkki

Kirjoitamme algoritmin Turingin koneelle, joka lisää syöttösanaan, joka on desimaaliluku, 1.

Sitten, kuvailevasti, algoritmi voidaan muotoilla seuraavasti:

1. Siirry oikealle ja etsi syöttösanan alku
2. Siirry oikealle ja etsi syöttösanan loppu
3. Lisää yksi syöttösanan nykyiseen bittiin. Jos on numero 0-8, poistu. Muussa tapauksessa kirjoita 0, siirry vasemmalle ja palaa vaiheeseen 3.

Kirjoitamme tämän algoritmin taulukon muodossa. Aakkoset koostuvat numeroista 0-9 ja "tyhjästä merkistä" \(\Lambda\) . Tarvitsemme myös automaatin 4 tilaa, pysäytystila laskettuna, jotka vastaavat algoritmin kuvauksen vaiheita.

Olemme samaa mieltä siitä, että alkutila \(1\) on hakusanan alun haku, \(2\) on syöttösanan lopun haku, \(3\) on 1:n lisäys.

\(_(q_j)\kenoviiva^(a_i)\)	Λ	0	1	2	3	4	5	6	7	8	9
1	ΛP1	0H2	1H2	2H2	3H2	4H2	5H2	6H2	7H2	8H2	9H2
2	ΛL3	0P2	1P2	2P2	3P2	4P2	5P2	6P2	7P2	8P2	9P2
3	1H0	1H0	2H0	3H0	4H0	5H0	6H0	7H0	8H0	9H0	0L3

Katsotaanpa, kuinka tämä algoritmi toimii esimerkin avulla. Ensimmäinen rivi vastaa nauhaa, toinen osoittaa koneen sijainnin ja sen nykyisen tilan.

	1	9	9
1

Tilassa 1 automaatti on tyhjän solun yläpuolella. Vastaava komento taulukosta “ΛP1”, eli jätä solu tyhjäksi, siirry oikealle ja pysy tilassa 1:

	1	9	9
	1

Nyt automaatti havaitsee arvon "1". Vastaava komento on "1H2", eli jätä "1" soluun, älä liiku ja siirry tilaan "2":

	1	9	9
	2

Tilassa "2" kone havaitsee arvon "1". Vastaava komento on "1P2", eli poistu "1", siirry oikealle ja pysy tilassa "2":

Tilanne toistuu:

Nyt tilassa 3 ja tarkkailemalla symbolia "9" automaatti suorittaa komennon "0L3":

	1	9	0
		3

Tilanne toistuu:

Tila "0" – pysäytystila. Algoritmi on valmis.

Muodollinen kuvaus

Matemaattisesti Turingin konetta voidaan kuvata seuraavasti:

Turingin kone (MT)

se on muotojärjestelmä \(\(A, a_0, Q, q_1, q_0, T, \tau\)\), missä

• \(A\) on äärellinen joukko MT-aakkosten symboleja
• \(a_0 \in A\) – aakkosten tyhjä merkki
• \(Q\) – äärellinen joukko MT-tiloja
• \(q_1 \in Q\) – MT:n alkutila
• \(q_0 \in Q\) – MT:n lopullinen tila (pysäytystila)
• \(T = \(L, P, H\)\) on MT:n siirtymien joukko
• \(\tau\) – MT-ohjelma, eli funktio, joka määrittää kartoituksen \(\tau: A\times Q\backslash \(q_0\) \rightarrow A\times T \times Q\)

Algoritmien teorian avain on Turingin väitöskirja.

Löyhästi ilmaistuna Turingin teesi esitetään seuraavasti:

Turingin väitöskirja Jokaiselle algoritmisesti ratkaistavalle ongelmalle on olemassa Turingin kone, joka ratkaisee tämän ongelman. muuten mille tahansa algoritmille on olemassa vastaava Turingin kone.

Turingin opinnäytetyö antaa meille mahdollisuuden puhua algoritmeista melko yksinkertaisella matemaattisella laitteistolla. Lisäksi Turingin kone itse on yleiskäyttöinen käyttölaite, ja sellaisen kuvitteellisen koneen luomisen mahdollisuudesta tuli tilaisuus puhua universaalin laskentatekniikan luomisesta.

Vaihtoehtoiset algoritmimääritelmät

Turingin koneen lisäksi on olemassa useita itsenäisiä määritelmiä, jotka vastaavat Turingin määritelmää.

Erityisesti määritelmä Postikoneen kautta, Churchin lambda-laskennan kautta, normaali Markov-algoritmi.

Harkitse näitä menetelmiä.

Postikone

Vuosi Turingin jälkeen amerikkalainen matemaatikko Emil Leon Post ehdotti itsenäisesti toista abstraktia yleistietokonetta, joka on jossain määrin yksinkertaistettu Turingin tietokonetta.

Postiautomaatti toimii kaksinumeroinen aakkosilla, ja automaatin sisäinen tila korvataan ohjelmalinja.

Muuten Postikone on samanlainen kuin Turingin kone: siellä on automaatti ja ääretön nauha soluineen.

Postikone voi suorittaa seuraavat komennot:

1. Kirjoita 1, siirry ohjelman i:nnelle riville
2. Kirjoita 0, siirry ohjelman i:nnelle riville
3. Vaihto vasemmalle, siirry ohjelman i:nnelle riville
4. Vaihto oikealle, siirry ohjelman i:nnelle riville
5. Ehdollinen haara: jos havaittu solu on 0, siirry ohjelman i:nnelle riville, muussa tapauksessa siirry ohjelman j:nnelle riville.
6. Lopettaa.

Postikoneessa on myös useita kiellettyjä komentoja:

1. Kirjoita soluun 1, kun siellä on jo 1.
2. Kirjoitetaan soluun 0, kun siellä on jo 0.

Tällaiset tapahtumat johtavat kolariin.

Seuraavaa merkintää voidaan käyttää ohjelmien kirjoittamiseen postikoneelle:

1. ∨ i - kirjoita 1, siirry ohjelman i:nnelle riville
2. × i – kirjoita 0, siirry ohjelman i:nnelle riville
3. ← i - siirry vasemmalle, siirry ohjelman i:nnelle riville
4. → i - siirry oikealle, siirry ohjelman i:nnelle riville
5. ? i; j- ehdollinen haara: jos havaitussa solussa on 0, siirry ohjelman i:nnelle riville, muussa tapauksessa siirry ohjelman j:nnelle riville.
6. ! - lopettaa.

Esimerkki ohjelmasta:

1. → 2 2. ? yksi; 3 3. × 4 4. ← 5 5. !

Tämä ohjelma poistaa ensimmäisen tarran (1) automaatin aloitusaseman oikealta puolelta ja pysäyttää automaatin sen vasemmalla puolella olevassa solussa.

Yleisesti ottaen Postikone on edelläkävijä välttämätöntä ohjelmointikielet, kuten C, Fortran jne.

Postikone vastaa Turingin konetta. Toisin sanoen mille tahansa Turingin koneohjelmalle voidaan kirjoittaa vastaava Post-koneohjelma ja päinvastoin.

Yksi tärkeä seuraus tästä vastaavuudesta on se mikä tahansa aakkosto voidaan pelkistää binäärikoodiksi.

Turingin opinnäytetyön tapaan on olemassa myös Postin väitöskirja.

Postin opinnäytetyö Jokainen algoritmi voidaan esittää Postikoneena.

Normaali Markov-algoritmi

Normaalit Markov-algoritmit on suunniteltu käytettäväksi eri aakkosten sanoissa.

Minkä tahansa normaalin algoritmin määritelmä koostuu kahdesta osasta:

1. aakkoset algoritmi
2. Kaavio algoritmi

Itse algoritmia sovelletaan sanat, eli merkkijonoja aakkoset.

Normaalialgoritmin kaavio on äärellinen järjestysjoukko ns korvauskaavat, joista jokainen voi olla yksinkertainen tai lopullinen. Yksinkertaiset korvauskaavat ovat muodon \(L\-D\) lausekkeita, joissa \(L\) ja \(D\) ovat kaksi mielivaltaista sanaa, jotka on muodostettu algoritmin aakkosista (kutsutaan vastaavasti vasen ja oikea osa korvauskaavasta). Vastaavasti lopulliset korvauskaavat ovat muotoa \(L\to\cdot D\) , jossa \(L\) ja \(D\) ovat kaksi mielivaltaista sanaa, jotka on muodostettu algoritmin aakkosista.

Oletetaan, että apumerkit \(\to\) ja \(\to\cdot\) eivät kuulu algoritmin aakkosiin.

Normaalin algoritmin soveltaminen mielivaltaiseen sanaan \(V\) on seuraava toimintosarja:

1. Olkoon \(V"\) algoritmin edellisessä vaiheessa saatu sana (tai alkuperäinen sana, jos nykyinen vaihe on ensimmäinen).
2. Jos korvauskaavojen joukossa ei ole ketään, jonka vasen osa sisältyisi \(V"\) , niin algoritmin työ katsotaan suoritetuksi ja sana \(V"\) katsotaan tulokseksi Tämä työ.
3. Muuten korvauskaavojen joukosta, joiden vasen osa sisältyy \(V"\) :een, valitaan ensimmäinen.
4. Kaikista mahdollisista sanan \(V"\) esityksistä muodossa \(RLS\) (jossa \(R\) on etuliite ja \(L\) on jälkiliite), valitaan yksi siten, että \(R) \) on lyhin , jonka jälkeen suoritetaan korvaus \(V"=RDS\).
5. Jos korvauskaava oli äärellinen, niin algoritmi päättyi tulokseen \(V"\) Muussa tapauksessa siirry vaiheeseen 1 (seuraava vaihe).

Mikä tahansa normaali algoritmi vastaa jotain Turingin konetta ja päinvastoin mikä tahansa Turingin kone vastaa jotakin normaalia algoritmia.

Tavallisesti kutsutaan Turingin teesin analogia normaaleille algoritmeille normalisointiperiaate.

Esimerkki

Tämä algoritmi muuntaa binääriluvut "yksittäisiksi" (joissa ei-negatiivisen kokonaisluvun N tietue on N:n sauvan merkkijono). Esimerkiksi binääriluku 101 muunnetaan viideksi tikuksi: |||||.

Aakkoset: ( 0, 1, | ) Säännöt:

1. 1 → 0|
2. |0 → 0||
3. 0 → (tyhjä merkkijono)

Lähderivi: 101 Toteutus:

1. 0|00|
2. 00||0|
3. 00|0|||
4. 000|||||
5. 00|||||
6. 0|||||
7. |||||

Rekursiiviset funktiot

Matemaattisten funktioiden pohjalta voidaan rakentaa Turingin konetta vastaava järjestelmä. Tätä varten meidän on esitettävä seuraavat funktioluokat:

• primitiiviset rekursiiviset funktiot
• yleiset rekursiiviset funktiot
• osittain rekursiiviset funktiot

Viimeinen luokka on sama kuin Turingin laskettavien funktioiden luokka (eli funktiot, jotka voidaan arvioida Turingin koneen algoritmilla).

Algoritmin määritelmä rekursiivisten funktioiden perusteella on olennaisesti lambda-laskennan taustalla, ja lähestymistapa perustuu siihen. toiminnallinen ohjelmointi.

Primitiiviset rekursiiviset funktiot

Primitiivisten rekursiivisten funktioiden luokka sisältää perustoiminnot ja kaikki perusfunktioista operaattoreiden avulla saadut toiminnot vaihdot ja primitiivinen rekursio.

Perusominaisuuksia ovat:

• Nollafunktio \(O()=0\) on funktio, jossa ei ole argumentteja ja joka palauttaa aina arvon \(0\) .
• Peräkkäisfunktio \(S(x)=x+1\) on funktio, joka määrittää minkä tahansa luonnollisen luvun \(x\) seuraava numero\(x+1\)
• Toiminnot \(I_n^m(x_1,\ldots,x_n) = x_m\), missä \(0

Muiden luokkafunktioiden rakentamiseen käytetään seuraavia operaattoreita:

• Korvaukset. Toiminnalle \(f\) \(m\) muuttujasta ja \(m\) funktiolle \(g_1,\ldots,g_m\) \(n\) muuttujasta, tulos korvaamalla \(g_k\) \(f\) on funktio \(h(x_1,\ldots,x_n) = f(g_1(x_1,\ldots,x_n),\ldots,g_m(x_1,\ldots,x_n))\)\(n\) muuttujista.
• primitiivinen rekursio. Olkoon \(f(x_1,\ldots,x_n)\) \(n\)-muuttujien funktio ja \(g(x_1,\ldots,x_(n+2))\) muuttujan \( n+ 2\) muuttujaa. Sitten tulos, kun primitiivistä rekursiooperaattoria käytetään funktioihin \(f\) ja \(g\), on muodon \(n+1\)-muuttujan funktio \(h\): \[ h(x_1,\ldots,x_n,0) = f(x_1,\ldots,x_n) \] \[ h(x_1,\ldots,x_n,y+1) = g(x_1,\ldots,x_n, y, h(x_1,\ldots,x_n,y)) \]

Osittain rekursiiviset funktiot

Osittain rekursiivisten funktioiden luokkaan kuuluvat primitiiviset rekursiiviset funktiot ja lisäksi kaikki funktiot, jotka saadaan primitiivisistä rekursiivisista argumenttien minimointioperaattorilla:

Argumenttien minimointioperaattori

Olkoon \(f\) \(n\)-muuttujien \(x_i \in \mathbb(N)\) funktio. Sitten tulos, kun argumentin minimointioperaattoria käytetään funktioon \(f\), on argumentin \(n-1\) funktio \(h\), joka määritellään seuraavasti:

\[ h(x_1,\ldots,x_(n-1)) = \min y, \] missä \ Eli \(h\) palauttaa funktion \(f\) viimeisen argumentin vähimmäisarvon, jonka \(f\) arvo on nolla.

Vaikka primitiiviset rekursiiviset funktiot ovat aina laskettavissa, osittain rekursiiviset funktiot voivat olla määrittelemättömiä joillekin argumenttiarvoille.

Tarkemmin sanottuna osittain rekursiivisia toimintoja tulisi kutsua "osittain määritellyiksi rekursiivisiksi funktioiksi", koska ne määritellään vain osalle argumenttien mahdollisista arvoista.

Yleiset rekursiiviset funktiot

Yleiset rekursiiviset funktiot ovat kaikkien osittain rekursiivisten funktioiden alaluokka, jotka on määritelty mille tahansa argumenttiarvolle. Ongelma sen määrittämisessä, onko tietty osittain rekursiivinen funktio yleinen rekursiivinen algoritmisesti ratkaisematon. Tästä päästäänkin aiheeseen laskettavuusteoria ja pysäytysongelma.

Lasketettavuusteoria ja pysäytysongelma

Mielikuvituksemme kokonaisuudessaan myöntää ratkaisemattomien ongelmien olemassaolon, eli ongelmien, joille on mahdotonta laatia algoritmia.

Laskettavuuden teoria käsittelee tällaisten ongelmien tutkimista.

Esimerkkejä algoritmisesti ratkaisemattomista ongelmista ovat lopeta ongelma ja johdettavuuden tunnistamisongelma. Tarkastellaanpa niitä tarkemmin.

Pysäytysongelma Algoritmin A kuvauksen ja syötteen \(x\) perusteella on selvitettävä, pysähtyykö algoritmi \(A\) syötteeseen \(x\) .

Pysäytysongelma on algoritmisesti ratkaisematon. Todistetaan se.

\(\Delta\)

Olkoon yleinen algoritmi, joka ratkaisee pysäytysongelman. Tarkastellaanpa sitten algoritmien luokkaa, joka käsittelee algoritmeja kuvaavia tekstejä.

Koska pysäytysongelman ratkaisemiseksi on olemassa universaali algoritmi, on olemassa algoritmi, joka määrittää, pysähtyykö mainitun luokan algoritmi omaan tekstiinsä vai ei. Merkitse tällainen algoritmi \(B\) .

Rakennetaan algoritmi \(C\) , jonka syötteenä on teksti algoritmista \(A\) , joka käsittelee oman tekstinsä:

1. Suorita algoritmi \(B\) \(A\) .
2. Jos \(B\)-algoritmi määrittää, että \(A\) pysähtyy tekstiinsä, siirry vaiheeseen 1. Muussa tapauksessa siirry vaiheeseen 3.
3. \(C\)-algoritmin loppu.

Yritetään soveltaa \(C\)-algoritmia \(C\)-algoritmiin, tulee ilmeinen ristiriita: jos \(C\) pysähtyy omaan tekstiinsä, se ei voi pysähtyä ja päinvastoin. Siksi \(B\)-algoritmia ei ole. \(\ei \Delta\)

Pysäytysongelman yleisempi muotoilu on johdettavuuden määrittämisen ongelma.

Johdattavuuden tunnistamisen ongelma

Määritetään tietty aakkosto, tämän aakkoston sanat (kaavat) ja muodollinen muunnosjärjestelmä tämän aakkoston sanojen yli (eli rakennetaan looginen lasku)

Onko kahdelle sanalle \(R\) ja \(S\) olemassa deduktiivinen ketju, joka johtaa \(R\) arvoon \(S\) annetussa loogisessa laskennassa?

Vuonna 1936 Alonzo Church osoitti Churchin lauseen.

Churchin teoreema Johdettavuuden tunnistamisen ongelma on algoritmisesti ratkaisematon.

Church käytti lambda-laskimen formalismia todistaakseen sen. Vuonna 1937 Turing osoitti hänestä riippumatta saman lauseen Turingin koneformalismilla.

Koska kaikki algoritmien määritelmät vastaavat toisiaan, on olemassa käsitejärjestelmä, joka ei liity tiettyyn algoritmin määritelmään ja toimii käsitteen kanssa. laskettava funktio.

Laskettava funktio on funktio, joka voidaan arvioida algoritmilla.

On ongelmia, joissa tulo- ja lähtötietojen suhdetta ei voida kuvata algoritmin avulla. Tällaisia ​​ominaisuuksia ovat laskematon.

Esimerkki ei-laskettavasta funktiosta

Ota funktio \(h(n)\), joka on määritetty funktiolle \(\forall n \in \mathbb(N)\) seuraavasti:

\[ h(n) = \begin(cases) 1, & \text(if )\pi\text( sisältää sekvenssin täsmälleen )n\teksti( 9.) \\ 0, & \teksti(muuten ) \end( tapaukset) \]

Voimme saada arvon \(1\) tälle funktiolle, mutta saadaksemme arvon \(0\) meidän on tarkistettava luvun \(\pi\) ääretön desimaalilaajennus, mikä on ilmeisesti mahdotonta äärellisessä aika. Tämä funktio ei siis ole laskettavissa.

1920-luvun jälkeinen ilmaisu Laskukone viittaa kaikkiin toimiviin koneisiin ihmisen tietokone, erityisesti ne, jotka on kehitetty Church-Turingin opinnäytetyön tehokkaiden menetelmien mukaisesti. Tämä opinnäytetyö on muotoiltu seuraavasti: "Mikä tahansa algoritmi voidaan antaa vastaavan Turingin koneen tai osittain rekursiivisen määritelmän muodossa, ja laskettavien funktioiden luokka on sama kuin osittain rekursiivisten funktioiden luokan ja Turingin koneilla laskettavien funktioiden luokan kanssa. ". Toisella tavalla Church-Turingin teesi määritellään hypoteesiksi mekaanisten laskentalaitteiden, kuten elektronisten tietokoneiden, luonteesta. Kaikki mahdolliset laskelmat voidaan tehdä tietokoneella, jos sillä on riittävästi aikaa ja tallennustilaa.

Mekanismit, jotka työskentelevät äärettömyyden laskennassa, tunnettiin analogisena tyyppinä. Tällaisten mekanismien arvot esitettiin jatkuvilla numeerisilla arvoilla, esimerkiksi akselin pyörimiskulmalla tai sähköpotentiaalin erolla.

Toisin kuin analogisilla koneilla, digitaalisilla koneilla oli kyky edustaa numeerisen arvon tilaa ja tallentaa jokainen numero erikseen. Digitaalisissa koneissa käytettiin erilaisia ​​prosessoreita tai releitä ennen hajasaantimuistilaitteen keksintöä.

Nimi Laskukone käsite alkoi syrjäyttää 1940-luvulta lähtien tietokone. Nämä tietokoneet pystyivät tekemään laskelmia, joita virkailijat tekivät ennen. Koska arvot eivät enää olleet riippuvaisia ​​fyysisistä ominaisuuksista (kuten analogisissa koneissa), digitaaliseen laitteistoon perustuva looginen tietokone on pystynyt tekemään mitä tahansa kuvattavaa. puhtaasti mekaaninen järjestelmä .

Turingin koneet suunniteltiin määrittelemään muodollisesti matemaattisesti, mitä voidaan laskea laskentakyvyn rajoissa. Jos Turingin kone pystyy suorittamaan tehtävän, niin tehtävän sanotaan olevan Turingin laskettavissa oleva. Turing keskittyi pääasiassa sellaisen koneen suunnitteluun, joka voisi määrittää, mitä voitaisiin laskea. Turing päätteli, että niin kauan kuin on olemassa Turingin kone, joka voisi laskea luvun approksimaatiota, tämä arvo on laskettavissa. Lisäksi Turingin kone voi tulkita loogisia operaattoreita, kuten AND, OR, XOR, NOT ja "jos-niin-else" määrittääkseen, onko