Berekenbaarheidstheorie

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.

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.

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.

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.

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."

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."

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."

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!"

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."

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."