Nedeterminizem

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Nedeterminizem je paradigma, ki v nasprotuju z determinizmom priznava nedoločenost razultatov ob vseh znanih podatkih. Lahko bi rekli, da dopušča svobodno izbiro, na katero ne morem vplivati z začetnimi pogoji. S tem prinaša nedločenost rezultatov.

Nedeterministično računanje dobimo lahko npr. z uvedbo novega programskega konstrukta

x := izbira(a,b)

ki priredi spremenljivki eno od obeh vrednosti a oziroma b.

Ni težko videti, da bi lahko vse možne izbire pripravili že vnaprej v nekem dvojiškem nizu dolžine n, ki mu pravimo certifikat. Ob običajnem determinističnem računanju, ki vsebjuje največ n izbir, bi potem pregledovali zaporedoma certifikat in se ob vsaki izbiri odločali za prvo (če je vrednost certifikata 0) ali drugo (če je vrednost certifikata 1).

Na ta način lahko modeliramo nedeterministično računanje z običajnim determinističnim Turingovim strojem, ki mu dodamo na začetku še certifikat, v katerm je združen ves nedeterminizem.

Glej tudi

Osebna orodja