Fiches de cours 2017-2018

PDF
 

Gödel and recursivity

MATH-483

Enseignant(s) :

Langue:

English

Remarque

Pas donné en 2017-18 - Cours donnés en alternance tous les deux ans

Summary

Gödel incompleteness theorems and mathematical foundations of computer science

Content

Gödel's theorems:
Peano and Robinson Arithmetics. Representable functions. Arithmetic of syntax. Incompleteness, and undecidability theorems.

 

Recursivity :
Turing Machines and variants. The Church-Turing Thesis. Universal Turing Machine. Undecidable problems (the halting and the Post-Correspondance problems). Reducibility. The arithmetical hierarchy. Relations to Turing machines. Turing degrees.

Keywords

Gödel, incompleteness theorems, Peano arithmetic, Robinson arithmetic, decidability, recursively enumarable, arithmetical hierarchy, Turing machine, Turing degrees, jump operator, primitive recursive functions, recursive functions, automata, pushdown automata, regular languages, context-free languages, recursive languages, halting problem, universal Turing machine, Church thesis.

Learning Prerequisites

Recommended courses

Mathematical logic (or equivalent). A good understanding of 1st order logic is required - in particular the relation between syntax and semantics.

Important concepts to start the course

1st order logic: syntax, semantics, proof theory, completeness theorem, compactness theorem, Löwenheim-Skolem theorem.

Learning Outcomes

By the end of the course, the student must be able to:

Teaching methods

Ex cathedra lecture and exercises

Assessment methods

Written: 3 hours

Supervision

Office hours Yes
Assistants Yes
Forum Yes

Resources

Bibliography

Set Theory:

Recursion Theory :

Proof theory :

Gödel's results :

Ressources en bibliothèque
Websites
Moodle Link

Dans les plans d'études

Semaine de référence

 LuMaMeJeVe
8-9     
9-10     
10-11     
11-12     
12-13     
13-14     
14-15     
15-16     
16-17     
17-18     
18-19     
19-20     
20-21     
21-22     
 
      Cours
      Exercice, TP
      Projet, autre

légende

  • Semestre d'automne
  • Session d'hiver
  • Semestre de printemps
  • Session d'été
  • Cours en français
  • Cours en anglais
  • Cours en allemand