Laskettavuuden teoria

This course has also been lectured in English under the name Recursion Theory.

Asema opetuksessa:

5 opintoviikon laudatur-erikoiskurssi, joka soveltuu matemaattisen logiikan linjalle.

Luennot kevätlukukaudella 2004:

Luentoajat: ti klo 10-12 ja ke klo 10-12 matematiikan laitoksen salissa SII, 4. kerroksessa. Ensimmäinen luento on tiistaina 20.1.2004.

Laskuharjoitukset:

To 10-12 salissa SII. Ensimmäiset harjoitukset torstaina 29.1.2004. Lista harjoituksista.

Sisältö:

Kurssin lähtökohtana on "mekaanisesti laskettavan" funktion intuitiivisen käsitteen analysointi. Tarkastelemme mm. seuraavanlaisia kysymyksiä:

Millaisilla matemaattisesti täsmällisillä käsitteillä voidaan mallintaa tietokoneen ja ohjelman toimintaa?
Mitä voisimme periaatteessa laskea, jos meillä olisi rajattomasti tietokoneresursseja käytettävissämme?
Mitä ohjelma voi saada selville toisesta ohjelmasta tai itsestään?
Mitä voi tapahtua, jos tietokoneohjelma tulostaa toisen tietokoneohjelman, joka sitten suoritetaan?
Kuinka voimme vertailla erilaisten ongelmien tietokoneella ratkaisemisen "vaikeutta", jos molemmat ovat ratkeavia tai molemmat ratkeamattomia?

Suorittaminen:

Kurssi suoritetaan loppukokeella, jollainen järjestetään yleisenä laitostenttipäivänä toukokuussa, tarvittaessa myös kesällä ja syksyllä. (Tarkat päivämäärät ilmoitetaan myöhemmin.) Edellinen loppukoe, 21.1.2003: PostScript, PDF.

Materiaali:

Luentomateriaalista pidetään laitoksen 5. kerroksessa kansiota. Lisämateriaaliksi sopivat seuraavat kirjat:

N. J. Cutland: Computability (Cambridge University Press, Cambridge 1980)
Hartley Rogers: Theory of Recursive Functions and Effective Computability (MIT Press, Amazon.com paperback hinta $29.50).

Kurssipalaute:

Luennoijalle voi lähettää nimetöntä palautetta koko kurssin ajan osoitteesta http://www.math.helsinki.fi/kurssit/kysely/jatkuva.html löytyvällä Web-lomakkeella. Toki palautetta voi antaa suoraankin.

Logiikan opetus - Loogikkoryhmän kotisivu - Matematiikan laitos