legrövidebb leíró hossz

Kapcsolódó fogalmak: 
Kolmogorov-komplexitás
Rövid szöveges bemutatás: 
A Kolmogorov-komplexitás valahogy ki szeretné fejezni a feladatok egyszerűségét. Azonban az egyszerűség illetve az egyszerűsítési lehetőségek nagyban függnek az információ reprezentációjától és az információk eltárolási sorrendjétől. Ahhoz, hogy ezt kiküszöböljék azt javasolátk, hogy az egyszerű legyen az a program hossz, amely egy általános Turing gépen megfelelően adja vissza az adatokat. Csakhogy ennek a hossznak a meghatározása megoldhatatlan problémához vezet. Ennek becslésére szolgál a legrövidebb leíró hossz. A módszert Jorma Rissanen alkotta meg 1978-ban. A módszer lényege az, hogyha bármiféle szabályosság megtalálható a leíró mintába, akkor ez a szabály alkalmas a rövidítésre. Alkalmazzunk szimbólumokat és tegyük meg a rövidítéseket és ezt folytassuk addig, amíg van rövidíthető szabályosság. Csak létező szimbólumokat használhatunk, újat nem alkothatunk. A mellékelt weboldalon bővebb leírást találhat.