NWI-IBC003
Computability
Course infoSchedule
Course moduleNWI-IBC003
Credits (ECTS)3
CategoryBA (Bachelor)
Language of instructionDutch
Offered byRadboud University; Faculty of Science; Informatica en Informatiekunde;
Lecturer(s)
Coordinator
dr. F. Wiedijk
Other course modules lecturer
Lecturer
dr. F. Wiedijk
Other course modules lecturer
Contactperson for the course
dr. F. Wiedijk
Other course modules lecturer
Academic year2017
Period
KW1  (04/09/2017 to 12/11/2017)
Starting block
KW1
Course mode
full-time
Remarks-
Registration using OSIRISYes
Course open to students from other facultiesYes
Pre-registrationNo
Waiting listNo
Placement procedure-
Aims

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
Content
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.
Literature
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.

Teaching formats

• 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.

Topics
• 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

Test information
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.

Prerequisites
Talen en automaten.

Required materials
Book
Thomas A. Sudkamp, Languages and Machines, Addison Wesley, third edition

Instructional modes
Course occurrence

Lecture

General
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.

Tutorial

Zelfstudie

Tests
Tentamen
Test weight1
OpportunitiesBlock KW1, Block KW2