Computability & Complexity - Lecture 3

Topics:

Closure properties of the class of primitive recursive functions:

• definition by cases
• bounded sum and product
• bounded minimization
• iteration.

Primitive recursive sets:

• characteristic function
• bounded existential and universal quantification.

Discrete Mathematics II - Lecture 4

Heutige Themen:

• Netzwerke
• Floyd-Warshall
• Dijkstra
• minimale Spannbäume
• Satz von Cayley.

Discrete Mathematics II - Lecture 3

Themen:

• Kriterien für die Planarität von Graphen
• Satz von Kuratowski
• Adjazenz- und Inzidenzmatrizen, Adjazenzlisten
• Tiefen- und Breitensuche.

Computability & Complexity - Lecture 2

Topics:.

• Peano schemes
• Fundamental lemma
• Primitive recursion
• Class of primitive recursive functions
• Each primitive recursive function is URM computable
• Closure properties: transformation of variables and parametrization.

Discrete Mathematics II - Lecture 2

Heutige Themen:

• Zusammenhangskomponenten
• Graph-Metrik
• Bäume
• Spannbäume
• bipartite Graphen
• planare Graphen
• Eulersche Polyederformel

Computability and Complexity - Lecture I

The first lecture held on Friday provided an introduction to register machines (URMs):

• states and state transformations
• syntax of URM programs
• semantics of URM programs.

Computability and Complexity

Preface 

Why do we need a formalization of the notion of algorithm or effective computation? In order to show that a specific problem is algorithmically solvable, it is sufficient to provide an algorithm that solves it in a sufficiently precise manner. However, in order to prove that a problem is in principle not solvable by an algorithm, a rigorous formalism is necessary that allows mathematical proofs. The need for such a formalism became apparent in the work of David Hilbert (1900) about the foundations of mathematics and Kurt Gödel (1931) about the incompleteness of elementary arithmetic.

The first investigations in the field were conducted by the logicians Alonzo Church, Stephen Kleene, Emil Post, and Alan Turing in the early 1930s. They provided the foundation of computability theory as a branch of theoretical computer science. The fundamental results established Turing computability as the correct formalization of the informal idea of effective calculation. The results led to Church’s thesis stating that ”everything computable is computable by a Turing machine”. The theory of computability has grown rapidly from its beginning. Its questions and methods are penetrating many other mathematical disciplines. Today, computability theory provides an important theoretical background for logicians and computer scientists.

Many mathematical problems are known to be undecidable such as the word problem for groups, the halting problem, and Hilbert’s tenth problem.

Contents - Computability:

• Register Machine
• Primitive Recursive Functions
• Partial Recursive Functions
• Ackermann's Function
• Acceptable Programming Systems
• Turing Machine
• Undecidability
• Word Problems

Discrete Mathematics II - Lecture 1

The first lecture held on Wednesday covered the following topics:

• basic definitions (graph, diagram, degree, degree sequence)
• hand-shaking lemma
• graph isomorphism
• subgraphs
• paths and cycles.

Discrete Mathematics II

The lecture takes place on Wednesday, 10:30 - 12:00 am, in building K - DE 15, room 0506, and will cover four topics:

• graph theory
• algorithmic graph theory
• combinatorial optimization
• linear optimization.