cursus Inleiding Adaptieve Systemen Opleiding Kunstmatige Intelligentie 2020-21

Hoorcollege

Berekenbaarheid

Kennen

  • Definities van: berekenbare functie, opsombare verzameling, beslisbare verzameling.
  • Beslisbaar ⇔ opsombaar.
  • Definitie van semi-beslisbare verzameling; semi-beslisbaar ⇔ opsombaar.
  • Definitie van complementair opsombare verzameling.
  • De stelling van Emil Post (“opsombaar + complementair opsombaar ⇔ beslisbaar”.)
  • Engelse terminologie: computable function, recursive set, decidable set, recursively enumerable set, co-recursively enumerable set.
  • Flake's diagram (p. 47 TCBoN).
  • De kans dat een willekeurige deelverzameling van ℕ beslisbaar is, is nul.
  • De kans dat een willekeurige functie ℕ → ℕ berekenbaar is, is nul.
  • ℕ, ℤ, ℚ, 𝔸, C, D en ℝ, in het bijzonder 𝔸, C en D.
  • De hiërarchie ℕ ⊆ ℤ ⊆ ℚ ⊆ 𝔸 ⊆ C ⊆ D ⊆ ℝ. De adjectieven “geheel”, “negatief”, “gebroken” (ook wel: “rationaal”, van “ratio”), “irrationaal”, “algebraïsch”, “transcendent”, “(on-)berekenbaar”, “(on-)definieerbaar”, en “reëel”.
  • Kunnen

  • Inzien dat beslisbaarheid opsombaarheid impliceert, maar niet andersom.
  • Verzamelingstheoretische vragen over opsombaarheid (“X en Y zijn opsombaar, zijn X∩Y, X∪Y, X−Y, Xc = ℕ − X opsombaar?”) kunnen beantwoorden, of kunnen aangeven waarom ze niet a priori beantwoord kunnen worden.
  • Uitleggen waarom de notie “complementair opsombaar” zin heeft, i.e., iets nieuws toevoegt.
  • De stelling van Emil Post bewijzen.
  • De equivalentie semi-beslisbaar ⇔ opsombaar bewijzen.
  • Met een aftelbaarheidsargument (of anders) laten zien dat bijna alle deelverzamelingen van ℕ niet opsombaar, en dus niet beslisbaar zijn.
    Herinner: “bijna alle” = “alle, op eindig veel na” (als de omvattende set aftelbaar oneindig is) of “alle op aftelbaar oneindig veel na” (als de omvattende set overaftelbaar oneindig is). Dus, ja, bijna alle mensen hebben drie oren.
  • Met een aftelbaarheidsargument (of anders) laten zien dat bijna alle functies van ℕ → ℕ niet berekenbaar zijn.
  • Een onberekenbaar getal aanwijzen, d.w.z., een expliciete constructie van een onberekenbaar getal geven.
  • Een onberekenbare functie aanwijzen, d.w.z., een expliciete constructie van een onberekenbare functie geven.
  • Aangeven dat de inclusies in ℕ ⊆ ℤ ⊆ ℚ ⊆ 𝔸 ⊆ C ⊆ D ⊆ ℝ eigenlijk strict zijn. Dit is niet meer dan bijvoorbeeld kunnen zeggen dat niet alle reëele getallen definieerbaar zijn. In dat geval hoeft geen element uit ℝ − D te kunnen worden aangewezen.(*) Wel wordt verwacht dat je een element uit 𝔸 − ℚ of D − C kan omschrijven.
  • (*)Een element uit D omschrijven kan min of meer per definitie niet. De speelruimte zit in het voorvoegsel “min of meer” 🙂.

    Materiaal

  • Slides Berekenbaarheid.
  • TCBoN H2 & H3.
  • Werkcollegedictaat.

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