Berekenbaarheid

Inleiding

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.

Leerdoelen

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

Onderwerpen

  • Turing machines
  • equivalentie van Turing machine modellen
  • multi-tape Turing machines
  • non-determinisme
  • Turing machines voor numerieke berekeningen
  • de universele Turing machine en het halting probleem
  • de Church-Turing these
  • beslisbaarheid en onbeslisbaarheid
  • probleemreductie
  • primitief recursieve functies
  • begrensde operatoren
  • begrensde en onbegrensde minimalisatie
  • mu-recursieve functies
  • de Ackermann functie

Werkvormen

  • 16 uur hoorcollege
  • 16 uur werkcollege
  • 52 uur zelfstudie

Toelichting werkvormen

Het college bestaat uit drie blokjes:
  • Turing machines
  • numerieke berekeningen en beslisbaarheid
  • mu-recursieve functies
Iedere bijeenkomst bestaat uit een uur werkcollege gevolgd door een uur hoorcollege, afgezien van de laatste bijeenkomst van een blokje: die bestaat uit een uur responsiecollege gevolgd door een uur deeltoets.

Toetsvorm

Er zijn drie niet verplichte deeltoetsen en er is een eindtentamen. De deeltoetsen tellen alleen mee als het gemiddelde hoger is dan het tentamencijfer. Voor de precieze berekening van het eindcijfer zie de website.

Vereiste voorkennis

Talen en automaten.

Literatuur

Thomas A. Sudkamp, Languages and Machines, Addison Wesley, derde editie, ISBN 0321322215. Dit is hetzelfde boek dat gebruikt wordt bij de cursus Talen en automaten.

Website


Vakcode
NWI-IBC003
Studiepunten
3 ec
Periode
eerste kwartaal

Docent

Opgenomen in

  • Bachelor Informatica