Na afloop van de cursus kunnen de studenten:
- Turing machines lezen en schrijven zowel als transitiediagram als als vijf-tupel
- Turing machines (standaard, multi-tape, non-deterministische, numerieke) ontwerpen bij een geven functie of taal
- de begrippen recursieve en recursief opsombare taal hanteren
- de universele Turing machine, het halting probleem en het blank tape probleem beschrijven
- van eenvoudig problemen herkennen of en laten zien dat ze beslisbaar of onbeslisbaar zijn
- functies schrijven als compositie van andere functies
- functies definiëren met primitieve recursie
- laten zien dat een gegeven functie primitief recursief of mu-recursief is
- de relatie leggen tussen Turing machines, mu-recursieve functies en recursief opsombare talen
|
|
Dit is een introductiecursus tot de theorie van de berekenbaarheid uit de theoretische informatica. Daarin wordt wiskundig onderzocht wat een computer wel en niet kan. In de cursus komen hiervoor twee berekeningsmodellen aan bod: Turing machines en mu-recursieve functies.
De begrippen van universaliteit (dat er in essentie maar één wiskundig model van berekenbaarheid is, en dat een enkele machine dit model kan implementeren) en van onbeslisbaarheid (dat er taken zijn die een computer niet kan uitvoeren) vormen de kern van de cursus.
Zowel de onbeslisbaarheid van het halting probleem (dat een computer niet kan berekenen of een programma ooit zal stoppen) komt aan bod, als hoe men laat zien dat andere problemen ook onbeslisbaar zijn.
|
|