Module Import 04IN2020 - Jewels in Theory

Status: (discontinued) Published
Workload3 ECTS = 90 hrs
Credits, Weight3 ECTS, (n.s.)
Language of Instruction English
Semester (n.s.)
Duration1 Sem.
M/E Elective
Course No. Type Name MA/EL Workload Credits Contact Hours Selfstudy Group Size
04IN2020-1 Lecture Jewels in Theory (n.s.) 3 ECTS = 90 hrs - 2 hrs/week = 30 hrs 60 hrs (n.s.)
Learning Outcomes

To give a fealing for beautiful results and their proofs in Theoretical Computer Science.


(not specified)

04IN2020-1 - Jewels in Theory
  1. Computing by guessing: the theorem of Immermann and Szelepcsényi
  2. Concurrent computation: the theorem of Lipton on exponential space hardness of Petri nets
  3. Parallel computation: the small universal self-reproducing cellular automaton of Banks
  4. From Logic: Church's undecidability of predicate logic, Gödel's incompleteness of arithmetics, Büchi's decidability of S1S
Teaching Methods

(not specified)


Grundkenntnisse in Theoretischer Informatik

Examination Methods

je nach Teilnehmerzahl: Klausur oder mündliche Prüfung

Credit Requirements

(not specified)


(not specified)

04IN2020-1 - Jewels in Theory

Priese: Jewels in Theory, Skript im Internet

Use of this Module
Responsible / Organizational Unit
Priese, Lutz / Institute for Computer Science
Additional Information

(not specified)

Last change
Apr 24, 2018 by Frey, Johannes
Last Change Module
May 14, 2012 by Frey, Johannes