Dimitri Watel

MODELS OF COMPUTATION

Other teacher(s) : Renaud Rioboo

In this course, we define formally what is a program, a fonction, what does "compute" mean in a formal and mathematical way? We then deduce which computational problem can be solved by a program and which cannot. We also explain the equivalence between different way of thinking a computation and between difference models of computation (Turing machine, partial recursive functions, lambda-calulus).

Courses with annotations

Definitions (Annotations : 2018) (Board : 2018)
Calculability and recursive fonctions (Annotations : 2018) (Board : 2018)
Complexity classes (Annotations : 2018, 2019) (Board : 2018)
Reductions and completeness (Annotations : 2018, 2019) (Board : 2018, 2019)

Turing machines of the course:

Turing machine editor
Incrementer (deterministic) (.png, .tm)
Find a path with 3 nodes in a graph (deterministic)(.png, .tm)
Find a path with 3 nodes in a graph (non deterministic)(.png, .tm)
Cut a pizza (non deterministic)( .png(1), .png(2), .png(3), .png(4), .png(5), .png(6), .tm)

Change language : Français English