turing-täydellisyys

[Kumma nähdä tuleeko tämä ikinä perille]

Hyvin lyhyesti sanottuna Turing-täydellisellä kielellä pystyy tekemään kaikki mitä teknisellä laskulaitteella on ylipäätään tehtävissä. Jos kieli on Turing-täydellinen, sillä voidaan esim. koodata minkä tahansa kielen tulkki tai kääntäjä, ratkaista mikä tahansa laskennallinen tehtävä mikä ylipäätään on ratkaistavissa jne.

Monesti ihmisillä on kaikenlaisia harhaluuloja sen suhteen mitä eri kielillä voidaan tehdä. Usein luullaan, että esim. prologilla voidaan ratkaista erilaisia ongelmia kuin C:llä tai C:llä erilaisia kuin C :lla jne. Kuitenkin ratkeavat ongelmat ovat täsmälleen samat. (muita eroja voi toki olla, kuten kielen rakenteen sopivuus erilaisiin tilanteisiin - laskennallisissa ohjelmistoissa on esim. usein vektorit sisäisesti toteutettuna, jonka takia niillä on kätevää ratkaista erinäisiä tehtäväjoukkoja)

Voidaan osoittaa (toivottavasti nyt muistan tämän oikein, en löydä lähdettä tähän hätään), että itse asiassa äärimäisen yksinkertainen mekaanien laite voi laskea (teoriassa) kaiken - kone missä on kaksi muistipaikkaa ja kolme operaatiota, nimellisesti muistipaikkojen sisällön yhtäsuuruuden vertailu sekä muistipaikassa olevan luvun kasvatus ja vähennys, riittää käytännössä kaikkeen.

Onkin vaikeaa keksiä oikeaa ohjelmointikieltä, joka ei olisi turing täydellinen. Nyt kun mietin niin en keksi ensimmäistäkään sellaista, mutta erilaisia laskennan formalismeja kyllä on, joilla pystyy ratkaisemaan vain tietynlaisia ongelmia. Esimerkkinä äärelliset automaatit ja pinoautomaatit.

(Oikeastaan tarkalleen ottaen se, että esim. C:llä voi tehdä kaikki mitä mekaanisella laitteella ylipäätään voidaan tehdä, ei ole varsinainen fakta, vaan niin sanottu Church-Turing-oletus. Voi olla, että on olemassa jotain voimakkaampia formalismeja, mutta niitä ei ole löydetty eikä ole pystytty osoittamaan ettei sellaisia olisi.)

Tässä on se esimerkki:

Cobol on turing-täydellinen kieli. Sillä voi periaatteessa ohjelmoida mitä vaan, mitä millä tahansa tietokoneella ja/tai kielellä voi teoriassa toteuttaa. Käytännössä tietokoneiden ja ohjelmoijien rajallinen kapasiteetti antaa rajat, mutta se ei teoriaa koske.

Muistinkäyttö ja nopeus eivät liity tähän mitenkään. Eikä kielen helppokäyttöisyys. Teoriassa kun on rajattomasti aikaa ja muistia.

Säännölliset ilmaukset (regular expressions) ei ole turing-täydellinen kieli. Tosin sopivasti laajennettuna siitäkin saa sellaisen, mutta voidaan osoittaa, että perus-regexpeillä ei voi laskea jotain helposti määriteltäviä ja vaikkapa Cobol-kielellä toteutettavia tehtäviä.

Klassinen esimerkki alan matematiikassa on palindromien tunnistaminen. Säännöllisillä ilmauksilla ei voi tehdä sellaista ohjelmaa (automaattia), joka tunnistaisi kaikki palindromiset merkkijonot - ts. sellaiset, jotka ovat itsensä kanssa identtisiä, jos ne käännetään takaperin.

Jos jokin systeemi osaa tämän tehdä, se on laajempi kuin matemaattinen säännöllisten ilmausten järjestelmä. (Useimpien ohjelmointikielten regexp-kirjastot itse asiassa ovat sitä laajempia.) Turing-koneen ja säännöllisiä ilmauksia hyväksyvien äärellisten automaattien välissä on itse asiassa muitakin tasoja. Hae tietoa Chomskyn hierarkiasta, jos teoria kiinnostaa.

Lyhyesti siis: turing-täydellisyys on sitä, että koneella/ohjelmointikielellä voi tehdä kaiken sen, mitä millä tahansa muulla tällä hetkellä tunnetulla koneella/ohjelmointikielellä voi.

Käytäntö: monet asiat ovat helpompia niihin sopivalla kielellä. Nopeus ja muistinkulutus ovat käytännössä tärkeitä.

Näitä asioita ei sovi sotkea. Teoria on kyllä kiinnostavaa ja tärkeää, mutta se on asioiden yksinkertaistus oikean maailman näkökulmasta. Joku on joskus väittänyt, että on sama mitä kieltä käyttää, koska ne ovat turing-täydellisiä kaikki. Se on sama kuin sanoisi, että koska otsasi on naula-täydellinen, on ihan sama hakata nauloja seinään otsalla kuin vasaralla.

Asiat paikallaan, niin hyvä tulee :-)