British Museum-algoritmus

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

Newell, Shaw és Simon ezt az eljárást a British Museum algoritmusának nevezték,

"... mivel számukra úgy tűnt, hogy az algoritmus használatának értelme annyi, mint majmok írógép elé ültetése annak érdekében, hogy a British Museum összes könyvét reprodukálják."

Például elméletileg megtalálhatja a legkisebb programot, amely a következő módon old meg egy adott problémát: hozzon létre egy lehetséges forráskódot, amelynek hossza egy karakter. Ellenőrizze, hogy megoldja-e a problémát. Ha nem, akkor generálja és ellenőrizze a két karakterből, három karakterből álló programot, stb. 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 állíthatók be annak bemutatására, hogy az optimalizálás, a tétel bizonyítása, a 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 keresés