GIKGO

C-ohjelma

Ohjelma muotoiltuna tyyliin indent -kr 
1: char l['RP'] = "GIKGOPAMU@", *I, *O, _;
2: main()
3: {
4:     for (I = O = 99 + l; 
5:          _= l[_ / 2 & 30 | *(*I++ = _ % 2 | 48, puts(O), I -= _ & 2) & 1];
6:          I < O && --O);
7: }
1:char l['RP']
Varaa merkkitaulukolle l tilaa monimerkkivakion 'RP' (tekijän nimikirjaimet) verran. Tarkka arvo rippuu hieman järjestelmästä, mutta on kuitenkin enemmän kuin tarvittu noin 12300 merkkiä.
1:= "GIKGOPAMU@",
Alusta tulukko l merkkijonolla, joka koodaa viiden tilan ja kahden symbolin Turingin koneen: 
1:0 1-2-left    2:0 1-3-left    3:0 1-4-left    4:0 1-1-right   5:0 1-halt
1:1 1-3-right   2:1 1-2-left    3:1 0-5-right   4:1 1-4-right   5:1 0-1-right
jossa merkkipari koodaa tilan syötteellä 0 / 1: kirjoita nauhalle bittiä 0 vastaava symboli (0 tai 1), bitti 1: nauhan siirtosuunta (1=vasemmalle), bitti 2..5 seuraava tila-1, bitti 6 == 1 (64 == ascii '@') jotta koodit ovat printattavia. Siis G = 1-2-left, I = 1-3-right. jne. Halt-tila koodataan null-koodilla, joka löytyy asetettujen tilojen perästä, siis U = 1-6(-right) == 1-halt. Loppu taulukkoa käytetään Turingin koneen nauhalle, joka tulee samalla alustettua tyhjäksi.
1:*I, *O, _;
I osoittaa luku-kirjoituspään paikan, O kirjoitetun nauha-alueen alun tulostamista varten ja _ Turingin koneen tilan. Koska _ määritellään päätasolla, se alustetaan nollaksi.
4:for (I = O = 99 + l;
Alusta lukupää ja tulostusoisoitin (riittävän kauas) nauhalle ja aloita Turingin koneen emulointi tilasta 1 lukupää tyhjällä merkillä.
5:_= l[_ / 2 & 30 | *(*I++ = _ % 2 | 48, puts(O), I -= _ & 2) & 1];
Tällä lausekkeella tehdään varsinainen emulaatio:
_= l[...];
Hae seuraavan tilan koodi, jos se on 0, pysähdy
_ / 2 & 30
Seuraavan tilan koodiparin indeksi.
| *(...) & 1
plus seuraavan tilan symboli luettuna nauhalta == seuraavan koodin indeksi.
*I++ = _ % 2 | 48,
Kirjoita nauhalle '0' tai '1' tilasta riippuen ja siirrä lukupäätä oletuksena oikealle.
puts(O),
Tulosta tähän mennessä kirjoitettu osa nauhasta.
I -= _ & 2
Siirrä lukupäätä vasemmalle tilasta riippuen, palauta uusi lukupään paikka.
6:I < O && --O);
Siirrä myös tulostusosoitinta, jos lukupää on siirtynyt sen ohi vasemmalle.

Ohjelma siis emuloi erään "Turingin koneen" ajamista tulostaen "nauhan" sisällön joka askelella. Mutta mitä se tekee?

Turingin kone

Turingin kone on yksinkertainen teoreettinen malli algoritmiselle laskennalle. Turingin kone koostuu tilamuuttujasta, loputtomasta nauhasta, jolle voidaan kirjoittaa symboleita yksi kerrallaan, työkohdan osoittimesta ja joukosta sääntöjä symbolien käsittelemiseksi. Säännöt määrittävät äärelliselle määrälle tiloja, millä symbolilla nauhalla työn alla oleva symboli pitää korvata, mihin suuntaan nauhalla siirtyä ja mikä on seuraava tila. Kone, joka päätyy äärellisessä määrässä askelia alkutilasta halt-tilaan, on pysähtyvä Turingin kone.

Kahden tilan ja kahden mahdollisen symbolin ('0' ja '1') Turingin kone: 

1:0 1-2-left    2:0 1-1-right
1:1 1-2-right   2:1 1-halt
jonka emulaattorin koodilla ilmaistaan "GEAI", pysähtyy 6 askelella ja jättää nauhalle 4 ykköstä kun se käynnistetään aluksi tyhjällä ('0'-symbolia täynnä olevalla) nauhalla tilasta 1. Askel askeleelta: 
Nauha  Askelia  Tila
  [0]     0     1:0 1-2-left
[0]1      1     2:0 1-1-right
 1[1]     2     1:1 1-2-right
 1 1[0]   3     2:0 1-1-right
 1 1 1[0] 4     1:0 1-2-left
 1 1[1]1  5     2:1 1-halt
 1 1[1]1  6     pysähtynyt
Voidaan todistaa, ettei mikään kahden tilan ja symbolin Turingin kone käynnistettynä tyhjällä nauhalla voi suorittaa sen enempää askelia tai kirjoittaa useampia ei-tyhjiä symboleita ja pysähtyä.

Turingin kone ei välttämättä pysähdy, esimerkiksi kahden tilan ja symbolin kone: 

1:0 1-2-right   2:0 1-1-left
1:1 1-1-left    2:1 1-2-right
koodi "ECCE", täyttää nauhaa loputtomiin kumpaakin suuntaan 1-symbolilla.

Pysähtymisongelma, pysähtyykö annettu Turingin kone, kun se käynnistetään annetulla nauhalla, on esimerkki ei-päätettävästä ongelmasta: voidaan todistaa ettei sen ratkaisemiseen ole yleistä algoritmia.

Busy beaver

Busy beaver on pysähtyvä Turingin kone, joka käynnistettynä aluksi tyhjällä nauhalla tekee paljon työtä; suorittaa mahdollisimman monta askelta tai kirjoittaa mahdolllisimman monta ei-tyhjää symbolia nauhalle.

Kolmen tilan ja kahden symbolin busy beaver Turingin koneet ovat: 

1:0 1-2-right   2:0 1-1-left    3:0 1-2-left
1:1 1-3-left    2:1 1-2-right   3:1 1-halt
koodi "EKCEGM", pysähtyy 13 askeleella kirjoittaen 6 ykköstä ja 
1:0 1-2-right   2:0 1-2-left    3:0 1-3-left
1:1 1-halt      2:1 0-3-right   3:1 1-1-left
"EMGHKC", joka kirjoittaa vain 5 ykköstä mutta suorittaa 21 askelta. 

1:0 1-2-right   2:0 1-1-left    3:0 1-halt      4:0 1-4-right
1:1 1-2-left    2:1 0-3-left    3:1 1-4-left    4:1 0-1-right
Neljän tilan kone, "EGCJQOM@", suorittaa 107 askelta jättäen nauhalle 13 ykköstä.

C-ohjelma emuloi viiden tilan busy beaver -kandidaattia: 

1:0 1-2-left    2:0 1-3-left    3:0 1-4-left    4:0 1-1-right   5:0 1-halt
1:1 1-3-right   2:1 1-2-left    3:1 0-5-right   4:1 1-4-right   5:1 0-1-right
"GIKGOPAMU@", joka 47176870 askeleen jälkeen pysähtyy, jättäen nauhalle noin 12300 symbolin rimpsun "11001001001001...00100100100100100101", jossa on 4098 ykköstä. Tulosta ei tietääkseni vielä ole todistettu parhaaksi mahdolliseksi.

Ei-pysähtyvää lukuunottamatta, edellisten Turingin koneiden toiminnan voi kokonaan emuloida vaihtamalla asianmukaisen koodimerkkijonon C-ohjelmaan. Mutta jos haluamme emuloida tähän saakka (kevät 2006) parhaan kuuden tilan busy beaver kandidaatin "EVHLOQRN@ICY": 

1:0 1-2-right   2:0 0-3-right   3:0 1-4-left    4:0 0-5-left    5:0 0-1-right   6:0 1-1-left
1:1 0-6-left    2:1 0-4-right   3:1 1-5-right   4:1 0-4-left    5:1 1-3-right   6:1 1-halt
emulaattoriohjelmaa pitää vähän muokata, koska kone emulaation edetessä ennen pitkää tarvitse hieman varaamaamme enemmän tilaa nauhalle. Kone kun pysähtyy 3.002*10^1730 askeleen jälkeen jättäen nauhalle 1.291*10^865 ykköstä...

Busy beaver -funktio S(n), joka kertoo kuinka monta askelta n tilan pysähtyvä Turingin kone voi tyhjällä nauhalla käynnistettynä korkeintaan suorittaa, on esimerkki ei-laskettavasta funktiosta. S(n) arvo kasvaa nopeammin kuin minkään laskettavissa olevan funktion. Arvo tunnetaan kahden symbolin Turingin koneille varmasti vain kun n < 5: 1, 6, 21, 107; S(5) >= 47176870 ja S(6) >= 3.002*10^1730 ...

Lisää aiheesta kolmannella kotimaisella Wikipedian Turing machine, Halting Problem ja Busy Beaver -artikkeleissa.

Takaisin

Pääsivulle