NWI-WM120C
Computability Theory
Course infoSchedule
Course moduleNWI-WM120C
Credits (ECTS)6
CategoryMA (Master)
Language of instructionDutch
Offered byRadboud University; Faculty of Science; Wiskunde, Natuur- en Sterrenkunde;
Lecturer(s)
Coordinator		dr. S.A. Terwijn
Other course modules lecturer
Lecturer		dr. S.A. Terwijn
Other course modules lecturer
Contactperson for the course		dr. S.A. Terwijn
Other course modules lecturer
Examiner		dr. S.A. Terwijn
Other course modules lecturer
Academic year2018
Period
KW1-KW2  (03/09/2018 to 27/01/2019)
Starting block
KW1
Course mode
full-time
Remarks-
Registration using OSIRISYes
Course open to students from other facultiesNo
Pre-registrationNo
Waiting listNo
Placement procedure-
Aims
The student is familiar with The goal of the course is to make the student acquainted with the topics mentioned below, and
  • arithmetization
  • the equivalence of various definitions of the class of computable functions
  • reducibilities
  • the arithmetical hierarchy
  • relative computation and Turing-reductions
  • the recursion theorem
  • diagonalization
  • applications
  • miscellaneous advanced topics
Thus, the student is prepared for more advanced topics in computability theory and descriptive set theory.
Content
  • arithmetization
  • the equivalence of various definitions of the class of computable functions
  • reducibilities
  • the arithmetical hierarchy
  • relative computation and Turing-reductions
  • the recursion theorem
  • diagonalization
  • applications
  • miscellaneous advanced topics
Literature
S. A. Terwijn, Syllabus Computability Theory (2004), and other material from textbooks.

Teaching formats

• 28 hours lecture
• 14 hours problem session

Test information
Written exam or oral examination, depending on the number of participants.

Prerequisites
Basic knowledge of mathematical logic, as well as the mathematical maturity required for a master's course in mathematics.

Recommended materials
Book
S. A. Terwijn, Syllabus Computability Theory (2004), and other material from textbooks.
Costs:0.00

Instructional modes
Course

Lecture

Tutorial

Zelfstudie

Tests
Tentamen
Test weight1
OpportunitiesBlock KW2, Block KW3