suosikkikirjailijani (David Deutsch, Roger Penrose ja Douglas Hofstadter) paneutuvat kaikki laskennallisen teorian Church-Turing-tutkielmaan ja ennen kaikkea sen vahvimpaan tulkintaan: Turingin periaatteeseen. Tässä postitse aion ensin selittää Church-Turing Thesis maallikon termejä.
kun olin tekemässä tietojenkäsittelytieteen tutkintoani, opiskelin Turingin koneita ja Church-Turingin opinnäytetyötä laskennallisen teorian tunnilla. Silloin ajattelin, että se oli ajanhukkaa. Halusin vain ohjelmoida tietokoneita ja en voinut vähempää välittää tästä kauan sitten kuolleesta Turing-kaverista (eikä tästä Church-kaverista) enkä hänen typeristä teoreettisista koneistaan.
nyt kun ymmärrän Church-Turingin Teesin filosofiset seurannaisvaikutukset, Olisinpa kiinnittänyt huomiota tunnilla! Koska Church-Turingin teesi, jos se on totta, sisältää joitakin syvällisiä filosofisia seurannaisvaikutuksia, ja se saattaa myös kertoa meille jotain todellisuuden syvästä — ja erityisluonteesta.
äärellinen Automata
kaikki laskutoimituksen teoriaa käsittelevät tekstit ja luokat alkavat jollakin nimellä ”äärellinen Automata.”Perusidea niiden takana on melko helppo. Kuvittelet vain yksinkertaisen ”koneen”, joka pystyy tekemään valintoja ja liikkumaan valtioiden välillä. Tässä on esimerkki hyvin yksinkertaisesta, joka edustaa kolikolla toimivan kääntöportin ”logiikkaa”.
selkokielellä tämä kertoo, että jos yrittää työntää lukitun kääntöportin läpi,ei onnistu, jos ei ole ensin laittanut kolikkoa. Jos olet laittanut kolikon, mutta et ole ajanut läpi vielä, lisää kolikoita vain jättää sen lukitsemattomaan tilaan. Jos olet laittanut kolikon, voit työntää läpi. Sitten se lukittuu uudelleen seuraavalle henkilölle.
se oli luultavasti helpompi ymmärtää diagrammista kuin kuvauksesta.
äärelliset Automaatit kykenevät suorittamaan paljon monimutkaisempaa logiikkaa kuin tämä. Mutta tämän pitäisi antaa sinulle perustiedot siitä, miten finite automata toimii.
on huomattava, että äärellinen Automaatti, kuten yllä oleva, on puhtaasti teoreettinen, koska se on olemassa vain joukko kuplia ja viivoja paperilla. Se ei ole kuin olisi jokin pieni ”äärellinen automaatti kone” sisällä kääntöportti, joka tekee nämä päätökset. Tai ehkä minun pitäisi sen sijaan sanoa, että kääntöportti itsessään on äärellinen automaattikone.
jos todella haluaisimme, voisimme luultavasti rakentaa tosielämässä koneen, joka olisi äärellinen Automaatti.Mikään ei estä jotakuta rakentamasta sitä todelliseksi koneeksi tosielämässä ja asentamasta sitä sitten kääntöporttiin. Se ei ole halvin tapa tehdä se.
joten mikä tahansa äärellisen automaatin piirustukseksi tehty ”ohjelma” voidaan muuttaa tosielämän ”laskennaksi”, joka todella toimii. On tärkeää erottaa toisistaan laskennallinen kone, joka voi todella olla olemassa (kuten äärellinen Automaatti) ja kone, joka on vain hypoteettinen ja rikkoo fysiikan lakeja tulee tärkeä hetki.
tehokkaammat koneet
laskennallisen teorian luokan edetessä oppilaat tutustuvat yhä monimutkaisempiin ”koneisiin”, jotka ovat äärellistä Automataa tehokkaampia. Kuten kuvassa oikealla näkyy, seuraavaksi tehokkain on Pushdown Automata (PDA). PDA on oikeastaan vain DFA lisäämällä eräänlainen ”muisti”. Tämän muistin avulla PDA voi luoda ja suorittaa laskelmia (tai ohjelmia), joita DFA ei voi.
avainasia on vain se, että on olemassa tietyntyyppisiä ohjelmia, jotka voidaan kirjoittaa PDA: lle, jota ei voi kirjoittaa Deterministisellä äärellisellä automaatilla (DFA). Toisin sanoen kämmentietokoneet ovat ”tehokkaampia” kuin DFAs, koska ne voivat ilmaista ”ohjelmien” luokkia, joita DFAs ei voi.
joten DFAs: n ja kämmentietokoneen välillä on suhde ” laskentatehon suhteen.”Nimittäin se on mahdollista todistaa, että mikä tahansa ohjelma kirjoitettu DFA voidaan kirjoittaa myös PDA, mutta että päinvastainen ei ole totta.
todisteena on
todiste siitä, että PDA voi suorittaa mitä tahansa, mitä DFA voi tehdä, keksimällä järjestelmän, jolla DFA: n logiikka voidaan kartoittaa PDA: ksi. Koska PDA on vain DFA muisti, tämä ei ole vaikea tehdä — vain älä käytä ”muisti ominaisuus”.
mutta entä päinvastoin? Voimmeko todistaa, että on mahdotonta ottaa tietyntyyppisiä ”ohjelmia” kirjoitettu PDA ja kääntää ne DFA? Toisin sanoen, onko olemassa todisteita siitä, että Pushdown Automata ei voi kartoittaa rajallinen Automata? Vai oletammeko vain, että rajallinen Automata on tehottomampi kuin Pushdown Automata, koska emme tällä hetkellä tiedä tapaa kartoittaa kämmenmikro takaisin FDA: lle? Ehkä on olemassa tapa kartoittaa PDA FDAs ja ehkä kukaan ei ole keksinyt, miten tehdä se vielä? Eikö se ole edes mahdollista?
on mahdollista todistaa, että PDA voi suorittaa tietyntyyppisiä ohjelmia, joita DFA ei voi. Tapa, jolla tekisit sen, olisi löytää laskenta (ts. ohjelma), että voit todistaa, että DFA ei voi laskea ja sitten osoittaa, että PDA voi laskea sen.
koneen laskentateho
tämä seikka — että on olemassa tehokkaampia (PDA) ja vähemmän tehokkaita (DFA) logiikkakoneita — on sinänsä mielenkiintoinen.
mutta se johtaa filosofiseen kysymykseen: onko olemassa sellaista asiaa kuin ” tehokkain laskentakone?”
jos olisi tällainen ”tehokkain kone”, mistä tietäisimme, että jokin tietty ehdotettu kone sattuu olemaan ” tehokkain?”Vai onko käytettävissä vain erityyppisiä tietojenkäsittelykoneita ja sinun on valittava oikea tehtävään?
Turingin koneet
joten mikä kone on tehokkaampi kuin PDA?
historian mukaan samoihin aikoihin ehdotettiin kahta hyvin erityyppistä ”konetta”, jotka molemmat olivat todistettavasti tehokkaampia kuin kämmentietokoneet.
yksi oli Alan Turingin Turingin kone. Toinen ei ollut niinkään kone vaan Alonzo Churchin kehittämä nokkela notaatiosarja, joka palveli samaa tarkoitusta kuin koneen kehittäminen. Näistä kahdesta” koneesta ” Turingin kone on käsitteellisesti helpompi opettaa, joten yleensä juuri sitä konetta opetetaan laskennallisen teorian kurssilla.
Turingin koneet ovat hauskoja pieniä teoreettisia koneita, joissa on luku – / kirjoituspää ja (hypoteettinen) paperinauha, josta se voi lukea tai kirjoittaa. Sen perusteella, mitä Turingin kone lukee, se asettaa Turingin koneen toimintatilaan, joka suorittaa jonkinlaisen tehtävien yhdistelmän, joka koostuu joko luku – /kirjoituspään liikuttamisesta eteen-tai taaksepäin, lukemisesta uudesta asennosta nauhalle tai siten uuden aseman kirjoittamisesta nauhalle. Tältä näyttää Turingin kone:
Turingin Koneet ja nykyaikaiset tietokoneet
yksi kiinnostava seikka on se, että Turingin kone on pintaesiintymisestä huolimatta itse asiassa melko samanlainen kuin nykyaikainen tietokone. Modernissa tietokoneessa keskusyksikkö (CPU) vastaa Turingin koneen luku – /kirjoituspäätä. Muistipiirit (RAM tai ROM) muistuttavat hyvin paljon pitkän paperinauhan soluja, joista kääntökone voi lukea tai kirjoittaa. Nykyaikaiset tietokoneet näyttävät siis suunnilleen vastaavan Turingin konetta.
modernilla tietokoneella on yksi etu Turingin koneeseen verrattuna. Nykyaikaisen tietokoneen ei tarvitse siirtyä yhdestä ”muistinsa” solusta peräkkäisessä järjestyksessä niin kuin Turingin kone tekee.
se, että Turingin kone voi liikuttaa vain yhtä solua kerrallaan, tuntuu merkittävältä rajoitukselta, vai mitä? Näimme juuri, miten jotkut koneet ovat loogisesti ”tehokkaampia” kuin toiset: PDA voi suorittaa laskennallisia tehtäviä, joita FDA ei voi. Ehkä on siis olemassa Turingin koneita tehokkaampia koneita, jotka pystyvät suorittamaan tehtäviä, joihin Turingin koneet eivät pysty? Ja ehkä moderni tietokone — koska se pystyy hyppimään muistin ympäri sen sijaan, että sen pitäisi siirtyä solusta toiseen peräkkäin-voi ajaa joitakin ohjelmia, joita Turingin kone ei voi?
itse asiassa nykyisellä tietokoneella on todellisuudessa vähemmän ekspressiivistä voimaa kuin Turingin koneella, koska Turingin koneilla käsitettiin olevan äärettömän pitkä paperinauha (eli ääretön muisti), jossa tosielämän tietokoneena on aina äärellinen muisti. Kuitenkin, yleensä tämä tekee hyvin vähän eroa, mitä tyyppisiä laskelmia voi suorittaa, koska ihmiset eivät yleensä ole kiinnostuneita äärettömän pitkiä laskelmia, jotka antavat ulos äärettömän pitkiä tuloksia. Siksi sanon, että nykyaikaiset tietokoneet ja Turingin koneet ovat ”suurin piirtein” vastaavia. Itse asiassa, niin kauan kuin oletat jonkin mielivaltaisen mutta äärellisen muistin koon, ne ovat täsmälleen samanarvoisia sen suhteen, millaisia ohjelmia ne voivat suorittaa.
Church Turingin teesi: Turingin kone = Max looginen voima
mutta entä köyhä Alonzon kirkko? Hänen pieni ”koneraukkansa” unohtui, koska Turingin koneita on helpompi opettaa. Pystyykö hänen koneensa ehkä ilmaisemaan joitakin laskelmia /ohjelmia, joita Turingin kone ei pysty, tai päinvastoin?
eikö olisi loistava yhteensattuma, jos Alan Turing ja Alonzo Church vain sattuisivat luomaan kaksi täysin erityyppistä teoreettista laskentakonetta ja niin vain kävisi, että ne olisivat täsmälleen samanlaisia sen suhteen, millaisia laskutoimituksia ne voisivat suorittaa?
joten kuvitelkaa kaikkien hämmästys, kun Alan Turing pystyi esittämään todisteen siitä, että mikä tahansa Turingin koneelle kirjoitettu ohjelma voitiin kirjoittaa myös Kirkkokoneelle, ja myös todisteen siitä, että mikä tahansa kirkkokoneelle kirjoitettu ohjelma voitiin kirjoittaa myös Turingin koneelle.
itse asiassa on olemassa useita ehdotettuja teoreettisia laskennallisia koneita. Teoreetikot yrittivät esimerkiksi sallia Turingin koneella olevan useita nauhoja, joilla lukea/kirjoittaa. He jopa yrittivät sallia Turingin kone 2-ulotteinen ”arkki” lukea ja kirjoittaa. Teoreetikot kokeilivat kaikenlaisia parannuksia Turingin koneisiin (ja Kirkkokoneisiin).
ja tähän mennessä on pystytty tuottamaan jokaiselle niistä todiste siitä, että ne vastaavat yksinkertaista Turingin konetta.
tuo kuulostaa hurjalta sattumalta, eikö vain? Ja se olisi hurja sattuma, ellei ole ylärajaa sille, millaisia laskutoimituksia voidaan suorittaa.
jos tällainen yläraja on olemassa, niin ei olisi lainkaan sattumaa, että Turingin koneella ja Kirkkokoneella ja kaikilla muilla laskennallisilla koneilla on vain sattumalta sama laskentateho, koska itse asiassa syy siihen, miksi ne kaikki ovat ekvivalentteja, on se, että olemme saavuttaneet laskentatehon ylärajan.
mutta voimmeko todistaa, että ei ole olemassa mitään laskennallista konetta — sellaista, jota emme vain ole vielä löytäneet — jolla on kyky suorittaa laskutoimituksia, joita Turingin kone ei voi?
miten, tarkalleen, esittäisimme tällaisen todistuksen? Tosiasia on, että emme voi todistaa, ettei ole mitään Turingin konetta voimakkaampaa. Kuka tietää, ehkä on.
mutta fakta on, että emme löydä (tai keksi) mitään tällaisia koneita.
niinpä huomattavien ponnistelujen ja epäonnistumisten jälkeen Turingin koneiden voiman parantamiseksi lopulta Church-Turingin teesi hyväksyttiin, vaikkei sitä todistettukaan todeksi. Church-Turingin teesi sanoo jotain tällaista.:
ei ole mahdollista keksiä mitään laskentakonetta, joka pystyisi suorittamaan logiikkaohjelman, jota tavallinen Turingin kone ei pystyisi.
tai toisin sanoen:
Turingin Koneet ja niiden vastineet ovat tehokkaimpia mahdollisia laskentakonetyyppejä, eikä ole olemassa tehokkaampia koneita, joista emme vain tiedä vielä.
vuosien ja vuosien tutkimustyön jälkeen tämä opinnäytetyö pitää periaatteessa yhä paikkansa. Näemme myöhemmin, että there has been some of a modification to the Thesis with the introduction of theoretical quantum computers. Mutta periaatteessa teesi pitää yhä paikkansa tänäkin päivänä. Kukaan ei ole koskaan keksinyt tapaa päihittää Turingin koneita loogisessa ilmaisuvoimassa. Turing Machines on yhä hallitseva mestari.
joten nyt ymmärrät Church-Turingin Teesin. Church-Turingin teesi ei kuitenkaan varsinaisesti vastaa Turingin periaatetta. Joten tulevassa postitse aion kehittää, mitä ero on ja mitä se on filosofisia seuraamuksia ovat.
Toteaa
Turingin Periaatteen. Näin nimesi Roger Penrose, joka ei usko siihen (ainakaan nykymuodossa). Sen kehitti Turing-Deutsch-periaatteeksi David Deutsch, joka uskoo siihen, ainakin sen muodossa.) (Katso artikkeli Wikipediasta)