Ugrás a tartalomhoz

algorithmically random sequence

A Wikiszótárból, a nyitott szótárból

Angol


Főnév

algorithmically random sequence (tsz. algorithmically random sequences)

  1. (informatika) Egy algorithmically random sequence, vagy magyarul algoritmikusan véletlen sorozat, olyan végtelen bit- vagy karaktersorozat, amely nem tömöríthető rövidebb algoritmussal — azaz nincs rövidebb leírása, mint önmaga. Ez a fogalom a komplexitáselmélet és a számítógépes véletlenség határterületén áll, és szorosan kapcsolódik a Kolmogorov-komplexitáshoz.


🧠 Fő gondolat

Egy sorozat akkor algoritmikusan véletlen, ha nincs olyan program, amely kevesebb bitből áll, mint a sorozat, és képes lenne azt legenerálni.

Ez azt jelenti, hogy:

  • A sorozat nem tartalmaz ismétlődő mintázatokat, amelyek alapján le lehetne írni.
  • Bármely előfixuma (pl. első 100 bit) maximális információtartalommal bír, azaz incompressible.


📊 Kolmogorov-komplexitás

  • A Kolmogorov-komplexitás egy adott objektum (pl. egy bitstring) legrövidebb leírásának hosszát méri egy univerzális Turing-gép segítségével.
  • Példa:
    • "010101010101": röviden leírható mint ismétlődő "01" → nem véletlen
    • "0110011110001010..." (nincs ismétlődés vagy szabály): lehet, hogy véletlen


📈 Martin-Löf randomness

A legismertebb formális definíció az infinite binary sequences véletlenségére:

Egy végtelen bináris sorozat Martin-Löf véletlen, ha nem esik bele semelyik olyan hatékonyan meghatározható nulla valószínűségű eseménybe, amit egy algoritmikus teszttel el lehet különíteni.

Ez a definíció statikus és algoritmikus szempontból is védi a véletlenséget.


🔍 Tulajdonságai

  • Nem determinisztikusan előállítható (nem írható le determinisztikus programmal rövidebben)
  • Minden részlete „véletlennek tűnik”
  • Minden gyakorisági és statisztikai teszten megfelel (pl. 0 és 1 aránya ~ 50%)


📚 Kapcsolódó területek

  • Kvantummechanika: valóságos fizikai véletlenség
  • Kriptográfia: véletlenszám-generálás biztonsága
  • Elméleti informatika: Turing-gépek, leíró komplexitás
  • Statisztikai tesztek: NIST randomness tesztek (bár ezek csak korlátos hosszra értelmezhetők)


⚠️ Megjegyzés

  • Az algoritmikus véletlenség nem azonos a pszeudovéletlenséggel: utóbbi kiszámítható algoritmus által, de úgy tűnik véletlennek.
  • Végtelen algoritmikusan véletlen sorozat nem generálható determinisztikusan.


✅ Összefoglalás

Egy algorithmically random sequence olyan végtelen bináris sorozat, amely semmilyen rövid algoritmussal nem tömöríthető – azaz önmagában hordozza az összes információt, amit képvisel. Ez a fogalom mély matematikai és filozófiai jelentőséggel bír, és szoros kapcsolatban áll a Kolmogorov-komplexitással, a véletlenség elméletével, valamint a kriptoanalízis és elméleti számítástechnika kulcskérdéseivel.


További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=algorithmically_random_sequence&oldid=3497504”