Joitain huomioita tapauksesta 1
-------------------------------

1. Ensin on päätettävä, onko ongelma luonteeltaan laskennallinen vai
ei. Esim. ongelmat ``Uskookohan opettaja Joulupukkiin?'', ``Mitä
Dostojevski olisi ajattellut Jeltsinistä?'' ovat luonteeltaan
ei-laskennallisia). Otetaan tarkasteluun vain laskennalliset ongelmat
ts. sellaiset, jotka voisi ainakin periaatteessa ratkaista
tietokoneella.

2. Tehtävänä siis arvioida ongelman ratkeavuutta ja vaikeustasoa ENNEN kuin
se on ratkaistu. -> tarvitaan jokin keino mallintaa ongelmia
- Algoritmit? Edellyttäisi ongelman ratkaisemista!
- Turingin koneet? Abstraktimpi kuin algroitmi, helpompi keksiä, mutta on jo 
jonkinlainen ratkaisu.  
-> Formaalit kielet mallintavat itse ongelmaa (niitä voisi kutsua ongelman 
deklaratiiviseksi kuvaukseksi)

3. Formaalien kielten idea 
---------------------------
- jokaista laskennallista ongelmaa vastaa (ainakin yksi)
päätösongelma. Esim. ongelmaa ``Laske kahden kertolaskun tulo'' vastaa
päätösongelma ``Onko m*n=p?''.
- jokaista päätösongelmaa vastaa formaali kieli, esim. ongelma
``m*n=p?'' voidaan koodata merkkijonona ``x#y#z#'', missä x=luvun m
binääriesitys, y=luvun n bin.esitys ja z=luvun p bin.esitys. Nyt
voidaan määritellä kieli A siten että Merkkijono x#y#z kuuluu
kieleen A täsmälleen silloin kun m*n=p.
- formaalit kielet voidaan jakaa vaikeusluokkiin Chomskyn hierarkian mukaan:
* äärellinen kieli (helpoin)
* säännöllinen kieli 
* kontekstiton kieli
* kontekstillinen kieli
* rekursiivinen kieli (vaikein ratkeava ongelma)
* rekursiivisesti numeroituva kieli (ongelma on enää osittain ratkeava, 
siis ratkeamaton)
* ulkopuolella ei-rekursiivisesti numeroituvat kielet (täysin ratkeamattomat 
ongelmat)
- formaalit kielet kertovat jo jotain aika- ja tilavaativuuksista, kuten 
saamme myöhemmin tietää
- tarkka aika- ja tilavaativuusanalyysi edellyttää formaalin kielen 
tunnistavaa konetta (automaattia), jota voidaan analysoida - siis abstraktia 
ratkaisua ongelmaan.