British Museum-algoritmus

A British Museum-algoritmus egy általános problémamegoldó megközelítés egy megoldás megtalálására, az összes lehetőség egyenkénti vizsgálatával, a lehetséges legegyszerűbbtől kezdve. A kifejezés nem gyakorlati, hanem elméleti módszert jelent olyan esetekben, ahol a lehetőségek száma hatalmas.

Allen Newell, Cliff Shaw és Herbert Simon nevezte el ezt az eljárást British Museum-algoritmusnak, „... mivel számukra annyira tűnt értelmesnek, mintha majmokat ültettek volna írógépek elé, hogy azok a British Museum összes könyvét reprodukálják.”

Például elméletileg meg lehet találni vele a legkisebb programot egy adott probléma megoldására a következőképpen: hozzunk létre egy lehetséges forráskódot, amelynek hossza egy karakter. Ellenőrizzük, hogy ez megoldja-e a problémát; ha nem, akkor generáljunk és ellenőrizzünk két, három stb. karakterből álló programokat. Koncepcionálisan ez megtalálja a legkisebb programot, de a gyakorlatban általában elfogadhatatlan időt vesz igénybe (több, mint a program élettartama).

Hasonló érvek támaszthatók annak bemutatására, hogy egy optimalizálás, egy tétel bizonyítása, egy nyelv felismerése stb. lehetséges vagy lehetetlen.

Fordítás

Ez a szócikk részben vagy egészben a British Museum algorithm című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Kapcsolódó szócikkek

• Elágazás és korlátozás
• Szélességi bejárás