Inleiding Adap eve Systemen
HC1 - Oneindigheid
The Computa onal Beauty of Nature
• Uitgangspunt: de natuur is een samenstelsel van kleine deeltjes die zelfstandig heel
gemakkelijk zijn geprogrammeerd maar samen heel complex en interessant gedrag
vertonen
• Simple rules make complex systems
• We moeten ze bekijken, niet simuleren -> typisch KI: a ijken wat je kunt gebruiken
en de rest laten zoals het is
• Opzet van het college: elke keer een ander onderwerp
Oneindigheid
• Er zijn oneindig veel verschillende oneindigheden. “Aleph nul/één/twee/…/omega”
• Aleph zijn kardinale getallen: geven groo e van verzamelingen aan
• Alleen maar a elbare verzamelingen in deze cursus
• Een verzameling heet a elbaar als deze op een rij kan worden gezet
• Typische a elbare verzameling: N (natuurlijke getallen), Q (breuken)
• A elbare verzamelingen zijn alomtegenwoordig in de wiskunde en exclusief
vertegenwoordigd in de informa ca
• Discreet (alles wat a elbaar is) vs con nu (alles wat gelijkma g is met R)
• Maakt het mogelijk elementen 1 voor 1 te bekijken/bewerken
• A elbare rij is van a elbare verzameling: a elbare vereniging (U) is ook a elbaar
• Een verzameling A heet a elbaar als er een injec e f: A -> N bestaat. Elk element A
moet genummerd worden en dat nummer moet uniek zijn. Niet alle nummers uit N
hoeven worden gebruikt.
• Belangrijke voorbeelden van over-a elbare verzamelingen zijn: de reeële getallen R,
alle deelverzamelingen van N, de verzameling van alle eindige en oneindige bitstrings
Aleph
• Aleph 0 is de kleinste oneindigheid, namelijk hoeveel
natuurlijke getallen, even nummers, oneven nummers,
ra onele nummers er zijn.
• Labeling things in order is di erent than coun ng them ->
• Line 0 does not contribute to the number of lines, but it
does when labeling the order the lines
• The rst ordinal number is omega: the next label you’ll
need a er using up the in nite collec on of every single
coun ng number rst
• A er omega comes omega + 1, etc. It is not bigger than omega, it just comes a er.
• The order type of Aleph 0 is omega, as long as it is well ordered.
, • But what is then bigger than aleph 0? The power set of aleph 0. Set of all the
di erent subsets. Aka 2 to the power of aleph 0
• Aleph 1:
• Dat gaat zo door, aleph 2 is omega 2 etc….
Diagonaal-argument
• Bewering [0,1] is niet a elbaar (= niet op een rij te ze en)
• Over-a elbaar: ontkenning van a elbaarheid
• Gelijkmach gheid van twee verzamelingen: als een bi-jec e tussen deze twee
bestaat -> “even groot”
• (0,1) en R zijn gelijkmach g -> ronde haken betekenen dat 0 en 1 er niet bij horen.
• h ps://libraryo abel.info/ laat een oneindige bibliotheek zien met 3200 characters
• Er bestaan ook machtsverzamelingen: 2^A.
Berekenbaarheid
• Gödel nummering: het redeneren van teksten/boeken/programma’s kan je
reduceren over redeneren over getallen (niet per se heel e cient)
• Maakt gebruik van het feit van de wiskunde: priem-ontbinding is uniek (hoofdstelling
van de rekenkunde)
• Voorbeelden: 12 = 4 x 3 = 2^2 x 3^1 = (2, 1), 20 = 4 X 5 = 2^2 X 3^0 X 5^1 = (2, 0, 1)
• ASCII tabel (char <-> 7 bits): alle characters krijgen een uniek getal
• Met Gödel nummering kunnen we dus vragen over strings, i.h.b. computer
programma’s, vertaald worden naar vragen over getallen. Het is een manier om een
berekenbare bi-jec e te de niëren tussen N en Strings
• Priem-ontbinding is uniek: dus elk natuurlijk getal correspondeert met ten hoogste 1
string
• Church-Turing
• Alle programmeertalen zijn even krach g (bijv. in het geval van invoer en uitvoer).
• Het is niet zo dat alle programmeertalen even handig ( jd en geheugen) & sterk zijn
in toepassingen (bijv. interac viteit).
• Turing-volledigheid: als een no e van berekening B (bijv C#) minstens even krach g is
als andere berekening, is B Turing-volledig. Minstens even krach g -> niet krach ger.
• De register-machine:
• Bewering: de register-machine is even sterk als Java: beiden kanten op bewijzen.
• Je schrij Macro’s op: variabelen
• Basis van berekening-concepten; Turing-machine.
,HC2 - Beslisbaarheid, berekenbaarheid
De Turing machine is even sterk als bv Java. Je kan de Turing machine simuleren in Java. Ook
andersom. Idee: kom met een rekenvoorschri die berekeningen in een iets minder primi ef
berekeningsmodel, waarvan we al weren dat de Turing compleet is, omzet naar
berekeningen op een Turing machine.
These van Church-Turing
Aanname: wat wij intuï ef onder berekenbaarheid verstaan, wordt vertegenwoordigd door
de klasse van (proefondervindelijk even sterke) berekening-mechanismen op N^N.
- Deze klasse is heel groot. Bevat alle Turing-equivalente berekening-mechanismen
- Dit is een aanname/afspraak. Niet een stelling.
Berekenbaarheid
- Als je problemen hebt zijn er verschillende soorten: vraag-typen
- Vaag of subjec ef (wat is het lekkerst)
- Voldoende precies geformuleerd: kortste pad
- Meest belangrijke vraagstuk
- Welke vragen zijn wel en niet met de computer te beantwoorden?
- Bestaan er vraagstukken die computers principieel (aannemende dat alle
programmeertalen die we nu kennen samen de no e berekenbaarheid
representeren)niet kunnen oplossen? - Ja
- We houden ons bezig met de berekenbaarheidstheorie
Onbeslisbaarheid
- Carcassonne puzzel
- Er bestaat geen algoritme, er kan ook geen algoritme bestaan, en zal ook nooit zo zijn dat
voor alle niet-royeerbare Carcassonne-tegelsets kan bepalen of deze het vlak kunnen
vullen
- Turing maakte kennis met het Entscheidungsprolem: niet alle problemen kunnen
mechanisch worden opgelost -> Turing-machine (WW2)
Het stop-probleem is onbeslisbaar
, Stelling: Zij J een programmeertaal. Als J voldoende expressie is (Turing-compleet), dan kan
er geen programma h (element van) J bestaan dat voor elke programma/input-combina e
(j,i) (element van) J x I kan uitmaken of j met input i stopt.
- Merk op: h is 2-plaatsig en de j’s zijn 1-plaatsig (h moet dus 2 teruggeven en j 1)
- Bewijs (van het ongerijmde). Stel h bestaat wel. Dus: h(j, i) = 1 j(i) stopt.
- Mbv h/2 is makkelijk een programma te schrijven voor de onberekenbare q/1: 1(i): if
h(i, i) = 1, then loop forever.
- Tegenspraak: dus een hal ng func e h/2 kan niet bestaan.
Het invoer loze stop-probleem
Problemen al jd hetzelfde aanpakken: reduc e van het probleem dat je onbeslisbaar wil
bewijzen. Je neemt aan dat het probleem wel beslisbaar is, en bewijs de tegenspraak.
H/1 betekent 1 input
Begrippen in berekenbaarheidstheorie:
- Berekenbaar computable (func e)
- Opsombaar enumerable (verzameling)
- Complementair opsombaar
- Beslisbaar decidable (verzameling)
- Semi-beslisbaar
Een (mogelijk par ële) func e f: N -> N heet berekenbaar als er een computerprogramma
bestaat dat f kan berekenen voor precies alle getallen waarvoor f gede nieerd is.
Een verzameling getallen heet opsombaar/enumereerbaar als er een computerprogramma
bestaat dat alle elementen van X (vroeg of laat) afdrukt.
HC1 - Oneindigheid
The Computa onal Beauty of Nature
• Uitgangspunt: de natuur is een samenstelsel van kleine deeltjes die zelfstandig heel
gemakkelijk zijn geprogrammeerd maar samen heel complex en interessant gedrag
vertonen
• Simple rules make complex systems
• We moeten ze bekijken, niet simuleren -> typisch KI: a ijken wat je kunt gebruiken
en de rest laten zoals het is
• Opzet van het college: elke keer een ander onderwerp
Oneindigheid
• Er zijn oneindig veel verschillende oneindigheden. “Aleph nul/één/twee/…/omega”
• Aleph zijn kardinale getallen: geven groo e van verzamelingen aan
• Alleen maar a elbare verzamelingen in deze cursus
• Een verzameling heet a elbaar als deze op een rij kan worden gezet
• Typische a elbare verzameling: N (natuurlijke getallen), Q (breuken)
• A elbare verzamelingen zijn alomtegenwoordig in de wiskunde en exclusief
vertegenwoordigd in de informa ca
• Discreet (alles wat a elbaar is) vs con nu (alles wat gelijkma g is met R)
• Maakt het mogelijk elementen 1 voor 1 te bekijken/bewerken
• A elbare rij is van a elbare verzameling: a elbare vereniging (U) is ook a elbaar
• Een verzameling A heet a elbaar als er een injec e f: A -> N bestaat. Elk element A
moet genummerd worden en dat nummer moet uniek zijn. Niet alle nummers uit N
hoeven worden gebruikt.
• Belangrijke voorbeelden van over-a elbare verzamelingen zijn: de reeële getallen R,
alle deelverzamelingen van N, de verzameling van alle eindige en oneindige bitstrings
Aleph
• Aleph 0 is de kleinste oneindigheid, namelijk hoeveel
natuurlijke getallen, even nummers, oneven nummers,
ra onele nummers er zijn.
• Labeling things in order is di erent than coun ng them ->
• Line 0 does not contribute to the number of lines, but it
does when labeling the order the lines
• The rst ordinal number is omega: the next label you’ll
need a er using up the in nite collec on of every single
coun ng number rst
• A er omega comes omega + 1, etc. It is not bigger than omega, it just comes a er.
• The order type of Aleph 0 is omega, as long as it is well ordered.
, • But what is then bigger than aleph 0? The power set of aleph 0. Set of all the
di erent subsets. Aka 2 to the power of aleph 0
• Aleph 1:
• Dat gaat zo door, aleph 2 is omega 2 etc….
Diagonaal-argument
• Bewering [0,1] is niet a elbaar (= niet op een rij te ze en)
• Over-a elbaar: ontkenning van a elbaarheid
• Gelijkmach gheid van twee verzamelingen: als een bi-jec e tussen deze twee
bestaat -> “even groot”
• (0,1) en R zijn gelijkmach g -> ronde haken betekenen dat 0 en 1 er niet bij horen.
• h ps://libraryo abel.info/ laat een oneindige bibliotheek zien met 3200 characters
• Er bestaan ook machtsverzamelingen: 2^A.
Berekenbaarheid
• Gödel nummering: het redeneren van teksten/boeken/programma’s kan je
reduceren over redeneren over getallen (niet per se heel e cient)
• Maakt gebruik van het feit van de wiskunde: priem-ontbinding is uniek (hoofdstelling
van de rekenkunde)
• Voorbeelden: 12 = 4 x 3 = 2^2 x 3^1 = (2, 1), 20 = 4 X 5 = 2^2 X 3^0 X 5^1 = (2, 0, 1)
• ASCII tabel (char <-> 7 bits): alle characters krijgen een uniek getal
• Met Gödel nummering kunnen we dus vragen over strings, i.h.b. computer
programma’s, vertaald worden naar vragen over getallen. Het is een manier om een
berekenbare bi-jec e te de niëren tussen N en Strings
• Priem-ontbinding is uniek: dus elk natuurlijk getal correspondeert met ten hoogste 1
string
• Church-Turing
• Alle programmeertalen zijn even krach g (bijv. in het geval van invoer en uitvoer).
• Het is niet zo dat alle programmeertalen even handig ( jd en geheugen) & sterk zijn
in toepassingen (bijv. interac viteit).
• Turing-volledigheid: als een no e van berekening B (bijv C#) minstens even krach g is
als andere berekening, is B Turing-volledig. Minstens even krach g -> niet krach ger.
• De register-machine:
• Bewering: de register-machine is even sterk als Java: beiden kanten op bewijzen.
• Je schrij Macro’s op: variabelen
• Basis van berekening-concepten; Turing-machine.
,HC2 - Beslisbaarheid, berekenbaarheid
De Turing machine is even sterk als bv Java. Je kan de Turing machine simuleren in Java. Ook
andersom. Idee: kom met een rekenvoorschri die berekeningen in een iets minder primi ef
berekeningsmodel, waarvan we al weren dat de Turing compleet is, omzet naar
berekeningen op een Turing machine.
These van Church-Turing
Aanname: wat wij intuï ef onder berekenbaarheid verstaan, wordt vertegenwoordigd door
de klasse van (proefondervindelijk even sterke) berekening-mechanismen op N^N.
- Deze klasse is heel groot. Bevat alle Turing-equivalente berekening-mechanismen
- Dit is een aanname/afspraak. Niet een stelling.
Berekenbaarheid
- Als je problemen hebt zijn er verschillende soorten: vraag-typen
- Vaag of subjec ef (wat is het lekkerst)
- Voldoende precies geformuleerd: kortste pad
- Meest belangrijke vraagstuk
- Welke vragen zijn wel en niet met de computer te beantwoorden?
- Bestaan er vraagstukken die computers principieel (aannemende dat alle
programmeertalen die we nu kennen samen de no e berekenbaarheid
representeren)niet kunnen oplossen? - Ja
- We houden ons bezig met de berekenbaarheidstheorie
Onbeslisbaarheid
- Carcassonne puzzel
- Er bestaat geen algoritme, er kan ook geen algoritme bestaan, en zal ook nooit zo zijn dat
voor alle niet-royeerbare Carcassonne-tegelsets kan bepalen of deze het vlak kunnen
vullen
- Turing maakte kennis met het Entscheidungsprolem: niet alle problemen kunnen
mechanisch worden opgelost -> Turing-machine (WW2)
Het stop-probleem is onbeslisbaar
, Stelling: Zij J een programmeertaal. Als J voldoende expressie is (Turing-compleet), dan kan
er geen programma h (element van) J bestaan dat voor elke programma/input-combina e
(j,i) (element van) J x I kan uitmaken of j met input i stopt.
- Merk op: h is 2-plaatsig en de j’s zijn 1-plaatsig (h moet dus 2 teruggeven en j 1)
- Bewijs (van het ongerijmde). Stel h bestaat wel. Dus: h(j, i) = 1 j(i) stopt.
- Mbv h/2 is makkelijk een programma te schrijven voor de onberekenbare q/1: 1(i): if
h(i, i) = 1, then loop forever.
- Tegenspraak: dus een hal ng func e h/2 kan niet bestaan.
Het invoer loze stop-probleem
Problemen al jd hetzelfde aanpakken: reduc e van het probleem dat je onbeslisbaar wil
bewijzen. Je neemt aan dat het probleem wel beslisbaar is, en bewijs de tegenspraak.
H/1 betekent 1 input
Begrippen in berekenbaarheidstheorie:
- Berekenbaar computable (func e)
- Opsombaar enumerable (verzameling)
- Complementair opsombaar
- Beslisbaar decidable (verzameling)
- Semi-beslisbaar
Een (mogelijk par ële) func e f: N -> N heet berekenbaar als er een computerprogramma
bestaat dat f kan berekenen voor precies alle getallen waarvoor f gede nieerd is.
Een verzameling getallen heet opsombaar/enumereerbaar als er een computerprogramma
bestaat dat alle elementen van X (vroeg of laat) afdrukt.
