NWI-IBC003
Computability
Course infoSchedule
Course moduleNWI-IBC003
Credits (ECTS)3
CategoryBA (Bachelor)
Language of instructionEnglish
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
Examiner
dr. F. Wiedijk
Other course modules lecturer
Academic year2019
Period
KW2  (04/11/2019 to 02/02/2020)
Starting block
KW2
Course mode
full-time
RemarksAs of 2019, this course is taught in English.
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.
Level

Presumed foreknowledge
Talen en automaten.
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.
Specifics

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

Home study

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

Tests
Exam
Test weight1
Test typeExam
OpportunitiesBlock KW2, Block KW3