QED

In het aprilnummer van PC-Active staat een artikel van mij over DNA-computers en probabilistische priemtesten. Wat beide onderwerpen met elkaar gemeen hebben is dat het voorbeelden zijn van wiskundige bewijsmethodes die geen zekerheid bieden, maar wel met een hele grote waarschijnlijkheid een oplossing geven. Ik bespreek er de Miller-Rabin test om te bepalen of een getal een priemgetal is en een procedure om een Hamiltoniaans pad in een gerichte grafe te vinden met behulp van een DNA-computer.

Ik bespreek in het artikel ook de filosofische aspecten van deze probabilistische methodes. De methodes zijn heel betrouwbaar, omdat de kans op een fout willekeurig klein kan gemaakt worden. De wiskundige Ronald Graham gaf zelfs toe dat hij meer vertrouwen had in resultaten van Rabins probabilistische priemtest dan in resultaten van lange en ingewikkelde traditionele bewijsmethodes. Toch aanvaarden wiskundigen deze probabilistische methode niet als bewijs dat het getal in kwestie een priemgetal is. Er bestaan bijvoorbeeld lijsten van de grootste bekende priemgetallen, en een getal wordt pas op die lijst gezet als er een deductief bewijs van het priemgetal gevonden is. In cryptografische toepassingen worden deze getallen wel als priemgetallen aanvaard, maar in de wiskunde niet. De tests kunnen wel gebruikt worden om kandidaat-priemgetallen te selecteren waarvan men dan met deductieve methodes probeert te bewijzen dat het om een priemgetal gaat.