cursus Inleiding Adaptieve Systemen Opleiding Kunstmatige Intelligentie 2020-21

Hoorcollege

Beslisbaarheid

Kennen

  • De hoofdstelling van de rekenkunde (“de ontbinding van een getal in priemfactoren kan maar op één manier)”; Gödelnummering.
  • De praktische constatering dat alle programmeertalen even sterk zijn. Preciezer: evenveel kunnen in batch (dus evenveel kunnen van invoer naar uitvoer).
  • Uitzonderingen op deze constatering, bijvoorbeeld zodra (echte) asynchroniciteit, updates, of meer in het algemeen interactie met de buitenwereld is toegestaan.
  • Turing-volledigheid, Turing-equivalentie.
  • Turing-equivalente minimimalistische berekeningsmechanismen zoals de Turing-machine, Church's λ-calculus, recursieve functies, en de registermachine. Behalve de laatste hoeven deze slechts oppervlakkig te worden gekend. Zie ook TCBoN H3, Sec. 2 ev..
  • De notie “Turing tar-pit”, extreem minimalistische maar Turing-volledige talen zoals Brainfuck.
  • De Church-Turing these, te weten de afspraak dat de notie “berekenbaar” gedefinieerd wordt als wat alle berekeningsmechanismen (inclusief programmeertalen) in batch (dus in één keer, van invoer naar uitvoer) kunnen uitrekenen.
  • Het verschil tussen berekenbaar en onberekenbaar. Het verschil tussen beslisbaar en onbeslisbaar.
  • Het verschil tussen berekenbaarheid (kan wel of niet uitrekenen) en computationele complexiteit (kan makkelijk of moeilijk uitrekenen).
  • Er bestaan onbeslisbare vraagstukken (betegelingsprobleem, Turing's stopprobleem).
  • Beknopte Bio van Alan Turing.
  • Turing's stopprobleem (“bepaal of een gegeven programma met gegeven input stopt”), het invoerloze stopprobleem (“bepaal of een gegeven programma dat geen input nodig heeft stopt”)
  • De onbeslisbaarheid van Turing's stopprobleem.
  • Andere onbeslisbare problemen bt. programmatuur: het uniforme stoppprobleem; het printprobleem; het viruscheckerprobleem, het dead code probleem.
  • De notatie j/n, de notie ariteit of plaatsigheid.
  • De kracht van reductieargumenten kennen, en weten welke kant op moet worden gereduceerd.
  • Hyperberekenbaarheid, quantumcomputers.
  • Kunnen

  • Middels Gödelnummering een string kunnen coderen naar een positief geheel getal, en een positief geheel getal kunnen decoderen naar een string (of naar undef als een getal geen string codeert).
  • Drie elementaire maar, maar Turing-volledige, berekeningsmechanismen kunnen noemen, en kort kunnen beschrijven. Voorbeelden: de Turingmachine (Alan Turing), de registermachine, recursieve functies, lambda-calculus (Alonzo Church), Post tag systems (Emil Post).
  • Berekeningen in de registermachine kunnen uitvoeren.
  • Uitleggen dat de Church-Turing these geen stelling is maar een conventie (een afspraak).
  • Het diagonaalbewijs van de onbeslisbaarheid van Turing's stopprobleem kunnen reproduceren.
  • Een probleem (dat dicht aanligt tegen Turing's stopprobleem) onbeslisbaar kunen bewijzen door een probleem waarvan we al weten dat het onbeslisbaar is, naar dit eerste probleem te reduceren. Voorwaarden voor de reductie kunnen geven (kort gezegd moet het automatisch kunnen, dus het moet ook weer via een algoritme kunnen).
  • Uitleggen waarom een reductieargument überhaupt werkt bij het bewijzen van onbeslisbaarheid.
  • Materiaal

  • Slides Beslisbaarheid.
  • TCBoN H2 & H3.
  • Werkcollegedictaat, H2

  • Laatst gewijzigd op dinsdag 26 januari 2021, om 17:48 uur ——— translate to ru, ro, or en ——— commentaar welkom