Hoorcollege
Overzicht
Onderwerpen
Vier vragen over berekening: wat is de definitie van berekening? Als we het eens zijn over een definitie: Wanneer is het principieel onmogelijk iets uit te rekenen? Hoe complex is een computationeel probleem? Wat is een goed algoritme voor een problem?
Klassieke berekenbaarheid.
Onconventionele vormen van berekening.
Kennen
De betekenis van de term conventionele berekenbaarheidstheorie: berekenbaar =Def Turing-berekenbaar.
20e eeuw tot nu: alle voorgestelde berekenings-mechanismen blijken even sterk als de Turing-machine.
De betekenis van de term on-conventionele modellen van berekening.
De betekenis van de term complexiteitstheorie.
De betekenis van de term algoritmiek.
Het verschil tussen een intensionele definitie en een extensionele definitie.
Bekendheid met het Entscheidungs-problem (Hilbert, 1928).
De drie definities van berekening uit de vorige eeuw (Turing-machines, λ-calculus, en recursieve functies), en wie daar achter zaten (resp. Turing, Church, en Gödel).
Recursieve functietheorie: de drie basis-functies, en de drie operator-functies.
Recursieve functietheorie: het verschil tussen primitief recursief en (gewoon) recursief.
De notie partiële functie.
Recursieve functietheorie: de klasse van recursieve functies = de klasse van algemeen recursieve functies = de klasse van partieel recursieve functies. (Verschillende namen voor hetzelfde.)
Turing's antwoord op het Entscheidungs-problem: “On computable numbers, with an application to the Entscheidungsproblem” (1936-38): het stop-probleem kan door geen enkele Turing-machine worden uitgerekend (“beslist”).
Het antwoord van de wetenschappelijke gemeenschap (eerstens Kleene, Church en Turing) op het Entscheidungs-problem: er zijn vragen, w.o. het stop-probleem, die principieel nooit kunnen worden uitgerekend. Deze problemen heten onbeslisbaar.
Het verschil tussen op biologische organismen geënte berekening, en op biologische organismen geïnspireerde berekening.
De notie hyperberekenbaarheid als extensie van de conventionele Turing-machine.
Quantumrekenen: de aard van een signaal (superpositie tussen 0 en 1), en het gegeven dat er nieuwe soorten logische poorten zijn (namen hoef je niet te kennen).
De Bloch bol als representatie van de toestand van een qubit, en de betekenis van de hoek θ daarin.
Veel problemen in AI behoren tot de complexiteitsklasse van NP-volledige problemen. Voorbeelden: het vervulbaarheidsprobleem (SAT), het handelsreizigerprobleem (TSP), en het rugzakprobleem (KNAPSACK).
Het idee om een echt biologisch organisme, zoals de slijmzam, in te zetten op computationele problemen, zoals path finding en het handelsreizigerprobleem.
Kunnen
Elementaire manipulaties met Turing-machines, w.o. het schrijven van elementaire programma's, het voorspellen van de volgende move van een TM, en het geven van een executielog.
Elementaire manipulaties met λ-expressies in de λ-calculus.
Elementaire manipulaties met functies in de recursieve functietheorie.
Uitleggen waarom de klasse van recursieve functies soms aangeduid wordt met de klasse van partieel recursieve functies. (Uitleg: zodra minimalisatie is toegestaan kunnen functies partieel gedefinieerd zijn.)
Een gegeven eenvoudige functie opbouwen uit basisfuncties, functie-compositie en primitieve recursie.
Van een eenvoudige 2-plaatsige functie f(x,y) de minimalisatie μyf(x,y) geven.
Enkele vormen van on-conventionele berekening noemen en duiden.
Materiaal
Slides Overzicht.
Werkcollegedictaat.