TI2320 (IN2505-II). Berekenbaarheidstheorie. De centrale vraag van dit college is "Welke berekeningen kunnen in principe op een computer worden uitgevoerd?" Deze vraag behoort tot het domein van de berekenbaarheidstheorie. Tijdens het college worden de belangrijke begrippen en technieken uit dit gebied geïntroduceerd: diagonalisatie, Turingmachines, niet-determinisme, opsombaarheid, beslisbaarheid, berekenbaarheid, reductie en recursiestelling.

Berekenbaarheidstheorie

Berekenbaarheidstheorie: recursiestelling

Berekenbaarheidstheorie: reduceerbaarheid (3)

Berekenbaarheidstheorie: reduceerbaarheid (2)

Berekenbaarheidstheorie: reduceerbaarheid (1)

TI2320 (IN2505-II). Berekenbaarheidstheorie. "Some decidability results concerning finite automata and context-free languages are discussed. An informal proof of the undecidability of the Halting Problem is presented. The acceptance problem is introduced and its undecidability is demonstrated. Here the notion of Universal Turing Machine is (implicitly) used: a Turing machine can execute programmes stored with their application data on its input tape."

Beslisbare problemen, het Stopprobleem en de onbelisbaarheid ervan, en Universele Turingmachines

TI2320 (IN2505-II). Berekenbaarheidstheorie. "This module captures some important preliminaries to the course. These include the notions of deterministic and non-deterministic finite state automata, regular languages, grammars, context-free grammars, context-free languages and Chomsky normal form."

Voorkennis - Automaten en Talen

TI2320 (IN2505-II). Berekenbaarheidstheorie. "Hotel Hilbert is a story of infinity and how to calculate with countable, infinite sets. Cantor's proof of the uncountability of the set of real numbers is presented using the famous technique of diagonalisation. Other examples of uncountable sets are given. The existence of languages that are not Turing recognisable is demonstrated."

Oneindigheid, Hotel Hilbert, en aftelbare en overaftelbare verzamelingen

TI2320 (IN2505-II). Berekenbaarheidstheorie. "Hilbert's Entscheidungsproblem is undecidable! The common belief that the intuitive notion of computability is adequately modelled by the formal notion of Turing machine (defined by Alan Turing) or by the lambda calculus (invented by Alonzo Church) is called the Church-Turing Thesis. Turing machines and problems can be coded as natural numbers (or otherwise): a programme is a natural number!"

Het Entscheidungsproblem, de Church-Turing these en het coderen van Turingmachines en problemen

TI2320 (IN2505-II). Berekenbaarheidstheorie. "Enumerability is introduced as an alternative to recognisability: the Turing machine as an enumerator instead of as a recogniser. The proof of equivalence of both notions uses the so-called technique of "dove tailing". A first, seemingly simple, undecidable language is presented: Hilbert's tenth problem."

Opsommers en het 10e probleem van Hilbert

TI2320 (IN2505-II). Berekenbaarheidstheorie. "The notions of decidability and recognisability for non-deterministic Turing machines are defined. König's Lemma is explained and its use is shown in the proof of the computational equivalence of non-deterministic Turing machines and ordinary Turing machines. It is argued how non-deterministic Turing machines for solving a specific problem can be constructed by breaking up the problem in first guessing a solution and then checking its validity."

Niet-deterministische Turingmachines en hun equivalentie met gewone Turingmachines

TI2320 (IN2505-II). Berekenbaarheidstheorie. "In this lecture the notion of Turing machine is introduced as a mathematical model of an algorithm. Furthermore, the notions of Turing-recognisable and decidable languages are defined."

hubhopper

Berekenbaarheidstheorie

hubhopper