Algemeen Jacques Ellul Günther Anders Lewis Mumford Herbert Marcuse Andrew Feenberg Wiebe Bijker Algemeen Luddieten Wapentuig als voorbeeld Transport Radio en televisie Internet Artificiële intelligentie Algemeen Hypermedia en hypertext Informatieovervloed Privacy Spionage, inlichtingendiensten Cyberoorlog Hackers Algemeen Het schrift Boeken en tijdschriftenIncididunt nisi non nisi incididunt velit cillum magna commodo proident officia enim.
David HARELDavid Harel werkt als wiskundige aan het Weizmann Institute of Science, Rehovot, Israël. Hij schreef een boek over algoritmes.
In de 'Preamble' stelt hij:
"The goal of the book is to explain and illustrate one of the most important and fundamental facets of the world of computing - its inherent limitations."()"It concentrates on bad news that is proven, lasting, and robust, concerning problems that computers are simply not able to solve, regardless of our hardware, software, talents, or patience. And when we say 'proven', we mean really proven; that is, mathematically, and not just experimentally."(viii)
Hij verwijst naar AI ("endowing computers with human-like intelligence") en de onexacte en vage vragen en problemen daar.(ix-x)
Dit hoofdstuk start met een heel heldere en fundamentele uitleg van de essentie van computers: het omzetten van schakelaars van 'aan' naar 'uit' / van negatieve naar positieve elektrische ladingen (bits), het op nul zetten of uitlezen van ladingen, hoe ze er ook uitzien, wat ze ook doen.
Harel vergelijkt dit met koken. Het algoritme kan worden vergeleken met het recept. Een computerprogramma is "the precise representation of an algorithm, written in a special computer-readable formalism called a programming language."(4) De elementaire instructies van een algoritme moeten afgestemd worden op de mogelijkheden van de hardware.
Het algoritmische probleem is het probleem dat het algoritme moet oplossen. De beschrijving van een algoritme moet twee onderwerpen bevatten:
Een bepaalde invoer wordt een 'instance' (een voorkomend geval) van het probleem genoemd. Sommige problemen zijn rekenkundig van aard, sommige vereisen het herordenen van gegevens (bv. sorteren), sommige vereisen het ophalen van informatie (bv. het vinden van woorden), sommige zijn gericht op optimalizeren (bv. de kortste weg vinden naar ...) en sommige zijn beslisproblemen (ja/nee-problemen).
In het echte leven is het soms erg moeilijk om invoer en uitvoer te specificeren of te beschrijven. Daarom is in dit boek gekozen voor eenvoudige beslisproblemen, waarmee aangetoond zal worden dat computers zelfs bij dit soort eenvoudige problemen letterlijk voor een onmogelijke taak gesteld worden.
"An algorithmic problem is solved when an appropriate algorithm has been found. What is 'appropriate'? Well, the algorithm must provide correct outputs for all legal inputs: if the algorithm is executed, or run, on any one of the legal inputs defined in the problem, it must produce the output specified in the problem for that input. A solution algorithm that works well for some of the inputs is not good enough."(16/17)
Met andere woorden: Zelfs als het probleem inefficiënt wordt opgelost. Natuurlijk zou het mogelijk zijn om een algoritme te maken dat dit probleem efficiënter zou oplossen, maar dat is niet het punt.
Om een algoritme naar een computer te vertalen, moeten we een programmeertaal gebruiken die
"comes complete with rigid rules that prescribe the allowed form of a legal program, and also with rules, just as rigid, the prescribe its meaning. We can now phrase, or code our algorithms in the language, and they will be unambiguous not only to a human observer, but to the computer too."(21)
Het is erg moeilijk om een algoritme volkomen foutloos en zonder logische fouten te ontwerpen.
"Even if we were given unlimited amounts of pencil and paper, and an unlimited lifespan, there would be well-defined problems we could not solve. It is also important to stress that this is not just a fact about computing, by brain or by machine. It is a fact about knowing. In a strong sense, what we can compute is what we are able to figure out by careful step-by-step processes from what we already know. The limits of computation are the limits of knowledge."(28)
Algoritmische problemen met een eindige verzameling van toegestane invoer zijn oplosbaar. Maar de problemen met oneindige verzamelingen toegestane invoer zijn juist de interessante.
Voorbeeld 1: het tegel-probleem (p.30). Er is geen algoritme om dit probleem op te lossen, het probleem is niet berekenbaar resp. niet beslisbaar.
" 'OK', those proposing the two-line solution might say, 'so we can't solve the problem on this particular computer and with this particular language, bur we could solve it had we a more powerful computer and a more sophisticated language'. Isn't the issue merely a question of coming up with the right algorithmic idea, designing the corrsponding software, and running it on a sufficiently powerful piece of hardware? No, it isn't. Not at all."(35)
Dit zijn argumenten zoals ze ook door transhumanisten gebruikt worden. Nu kan het nog niet, maar straks wel, dus principieel kan het. Het punt is dat het juist principieel niet kan. En dat is wat Harel probeert duidelijk te maken.
(Wordt vervolgd.)