What makes algorithms non-deterministic?
Hi! In the article deterministic algorithm we say, that threads can cause race conditions, which is a non-deterministic behavior. Or is it a misunderstanding? I'm no native speaker... :-) I have a liltle problem with that claim and in de:WP they couldnt solve my problem: I cannot believe, that a bunch of concurrent, deterministic algorithms transform into a non-deterministic algorithm (in the sense of the formal definition given in the article). E. g.: In a deterministic computing machine M the concurrent algorithms A1 and A2 each load data object O to register X, increment X, write X to O and halt; in my understanding this cannot ever produce more than one sequence of states (e. g. M starts up with 2 identical cores, which each use the same clock and memory without any caching or locking, so that they will behave as if there was only one core, if there wasnt the extra boredom+heat - esp. after the halt instruction). But nobody wants to believe me... *sob* :-) Could somebody explain me, where my example becomes non-deterministic? Is it possibly a homonym thing? Thx. Bye. --Homer Landskirty (talk) 21:00, 15 December 2012 (UTC)
- The "What makes algorithms non-deterministic?" section of that article is specifically talking about real computers, stuck here in the muddy real world with us. They don't behave like your mathematically perfect deterministic computing machine. If you were to simulate a cycle-perfect machine, with everything (including interrupts and so forth) simulated deterministically, then algorithms within it would behave deterministically. But real computers, where timing is determined by analog events like the rotation of disks, the magnetic fields and air cushions beneath flying drive heads, the action of interference on bus lines, and a thousand other things, means interrupts which drive the OS don't behave perfectly deterministically, so threats aren't scheduled deterministically, and so a multithreaded algorithm will be affected. -- Finlay McWalterჷTalk 21:11, 15 December 2012 (UTC)
- oh - ok - so there is a deterministic algorithm in the sense of theoretical informatics (e. g. with that funny turing machine, which has infinite memory... *lol*) and a real world deterministic algorithm concept (where random events r somehow compensated as good as possible... e. g. timing seems to b always indeterministic here, because there is no way to tell the exact time in real world... this allows race conditions to show up...)... --Homer Landskirty (talk) 22:11, 15 December 2012 (UTC)
- In a theoretical context a nondeterministic algorithm is one where you assume a probabilistic distribution on its source of random bits and prove rigorously that the algorithm succeeds with some probability very close to 100%. In the real world the distinction is somewhat arbitrary—it comes down to whether you consider the source of (alleged) randomness to be part of the input or not. -- BenRG (talk) 22:23, 16 December 2012 (UTC)
- oh - i thought about that today... without satisfying results: e. g. the program ssh-keygen asks for user input in the beginning and now i wonder if the algorithm is non-deterministic or not... the article says, that Fermat primality test is an example for a non-deterministic algorithm, although it just checks if an equation holds with different values for a... i think i will not try anymore to understand what they mean... :-) "functional programming" looks like a C program to me, too... sometimes... :-) it's a little bit like in that cartoon Calvin and Hobbes, when the father tells Calvin, that an outer point on a LP disc moves faster than an inner point, although they both do the same rounds per minute... *giggle* but it feels good, that i m not the only one who has problems with it... :-) --Homer Landskirty (talk) 23:01, 16 December 2012 (UTC)
- The Linux ssh-keygen opens /dev/urandom and reads 32 bytes from it. That's randomness collected from real world sources like network and disk delays (hmm, I'd have thought it would use /dev/random, which is a better source still). -- Finlay McWalterჷTalk 23:20, 16 December 2012 (UTC)
- the data from /dev/*random could still b seen as input to an deterministic algorithm... --Homer Landskirty (talk) 06:57, 17 December 2012 (UTC)
- Actually, when I think about it, theoretical nondeterminism often means angelic nondeterminism, where one magically chooses the path that causes the algorithm to terminate as quickly as possible (for example, a nondeterministic factoring algorithm starts by correctly guessing a factor). That sort of nondeterminism is the N in NP. It's not directly related to randomness, since there may be only one best choice. What I described above would be called a probabilistic algorithm. I never thought about it, but this doesn't match the real-world use of "nondeterministic" very well at all... -- BenRG (talk) 00:35, 17 December 2012 (UTC)
- maybe that's where my disturbance come from... we heard something about "demonic non-determinism", too... *giggle* it guesses wrong until it would have to do the same error twice... --Homer Landskirty (talk) 06:57, 17 December 2012 (UTC)