MIU-järjestelmän esimerkkitehtäväksi lipsahti hieman vaikeampi tehtävä kuin oli tarkoitus. Eli älkää huoliko, jos se ei ratkennut! Tehtävä ei nimittäin ole ratkeava (mikä oli kirjan Gödel, Escher, Bach tarkoituskin).

Tämä ei siis havainnollistanut vain formaaleja kieliä, vaan myös toista vielä tärkeämpää aihetta: Kuinka löytää todistuksen tai huomata, ettei sellaista ole? Tämä on itse asiassa sama, kuin osoittaa, että sana kuuluu tai ei kuulu kieleen. Kurssin aikana tulemme opimaan erilaisia ratkaisuja tähän ns. jäsennysongelmaan, riippuen kielen vaikeudesta. Selostan kuitenkin nyt ihan yleistajuisesti, miksi MU ei voi seurata MI:stä.

Järjestelmä koostui säännöistä
xI -> xIU
Mx -> Mxx
xIIIy -> xUy
xUUy -> xy

MU:ta ei kuitenkaan voi johtaa näillä säännöillä (MU ei ole järjestelmän teoreema eli todistuva lause). Ongelmana on se, ettei I-kirjaimesta päästä eroon järjestelmän säännöillä, ellei alkuperäisessä aksioomassa ole I:tä 3:lla jaollinen määrä.

Sääntö 4 hävittää aina parillisen määrän U:ta. Jotta yksi U jäisi jäljelle, on U:ta oltava pariton määrä. Merkitään U:n määrää 2n+1:llä. Tämä on voitu saada kahdella tavalla:

1) I:n kolmikerroista säännöllä 3. Tällöin on täytynyt olla 3*(2n+1)=6n+3 I:tä. I:tä voi tuottaa vain säännöllä 2, mutta se kaksikertaistaa aina ''hännät''. Paritonta määrää I:tä ei ole voinut tuottaa sillä.

2) Yksi U on saatu säännöllä 1. Lisäksi voi olla parillinen määrä U:ta eli 2n U:ta. Nämä on voitu saada I:stä vain säännöllä 3 eli I:tä on täytynyt olla 3*2n=6n kpl. Tätäkään ei ole voinut tuottaa säännöllä 2, ellei aluksi ole ollut 3:lla jaollista määrää I:tä.

Kirjassa Gödel, Escher, Bach luvussa IX (s. 260 alkaen) on oikein kaunis todistus Gödel-lukuja (MIU-lukuja) apuna käyttäen.

Lipsahduksen takia opimme toivon mukaan kaikki hieman enemmän. Ja - etette taas epäilisi huijausta - ensi viikon harjoitustehtävä on ratkeava. Voitte vaikka tehdä ohjelman, joka etsii ratkaisun!