Trust me as a computer scientist that nondeterminism is not just multi-tasking. I realize that there may be an overlap in terms of the jargon used, but realize that nondeterminism has nothing to do even with anything mainframes or any other multi-tasking system does.
I will submit to the fact that you are probably right in that philosophy defines determinism to be something else. But, in the field of computer science, determinism really is an abstract concept that isn't easily explained, so maybe thats where I've failed. Like I say, trust me when I say that the only thing the two have in common is that they use the same terminology. It is not a matter of semantics, its a matter of substance here.
While I plead ignorance on the philosophy bit, to give a little bit better of an explanation of determinism/nondeterminism (as it applies to computer science).
Alright, when I say, "non-deterministic machine", I mean something totally unlike any computer that exists in the entire world today. In fact, there isn't even a single computer in the entire planet earth that is currently non-deterministic. It isn't even known whether or not it is possible to create it.
All computers (even multi-tasking ones and mainframes) in existence today are deterministic. They all process data in a linear fashion, one branch at a time.
Problems in computation can be separated into two discrete sets: P and NP. P = Polynomial (Deterministic), and NP = Nondeterministic Polynomial.
If a problem is in P, that means that there exists a *solution* to the problem that can be computed in "polynomial time". This just means that it can be computed in n^x, where x is some integer, and n^x is n to some power x. So, many algorithms are n^2 (quadratic time), n^3 (cubic time), etc. In fact, n^1000000 is still considered a "polynomial time" solution for a problem. Without getting too technical, something is generally considered "computable on a deterministic computer in finite time" if it has a polynomial solution.
Problems that are in NP have polynomial solutions ONLY on a nondeterministic machine. That is, while they may be solved in n^x steps on a nondetermistic machine, they require some infinite (undefined) number of steps on a deterministic machine. A good example would be a problem that requires n! (n factorial) steps to complete on a linear deterministic machine, yet may only require n^2 steps on a nondeterministic machine.
So, getting back to the original point, non-deterministic just refers to a machine that can compute any solution to exponential, factorial, or otherwise non-polynomial time deterministic solutions in polynomial time.
The best example of this might be how encryption works. RSA encryption involves two very large prime numbers p and q. RSA encryption involves a problem that is in NP, and that is how it maintains security. Files are encrypted by (p-1)(q-1). This number is nearly impossible to factor back to p and q, without knowing p or q. That is to say, prime number factorization for very large numbers is a problem that is in NP. A solution to this problem requires an infinite amount of computing time.
However, given either p or q, unraveling the math becomes trivial. In fact, the solution can be found in constant (n^0) time, which is very fast indeed. That is to say, if I give you (p-1)(q-1) you may spend the rest of your natural life trying to find p and q if they are large enough, however given p or q, you can verify the results in mere seconds on even the most basic calculator.
A nondeterministic computer could factor (p-1)(q-1) to obtain p and q in polynomial time. This would mean that all encryption that is based on problems that exist in NP would be rendered obsolete. Its just a really fast way of solving complicated problems.
I hope any of that made sense... I just don't want to make it sound like any of it has to do with awareness or any such thing, it really doesn't. Its just part of "computational theory".
I will submit to the fact that you are probably right in that philosophy defines determinism to be something else. But, in the field of computer science, determinism really is an abstract concept that isn't easily explained, so maybe thats where I've failed. Like I say, trust me when I say that the only thing the two have in common is that they use the same terminology. It is not a matter of semantics, its a matter of substance here.
While I plead ignorance on the philosophy bit, to give a little bit better of an explanation of determinism/nondeterminism (as it applies to computer science).
Alright, when I say, "non-deterministic machine", I mean something totally unlike any computer that exists in the entire world today. In fact, there isn't even a single computer in the entire planet earth that is currently non-deterministic. It isn't even known whether or not it is possible to create it.
All computers (even multi-tasking ones and mainframes) in existence today are deterministic. They all process data in a linear fashion, one branch at a time.
Problems in computation can be separated into two discrete sets: P and NP. P = Polynomial (Deterministic), and NP = Nondeterministic Polynomial.
If a problem is in P, that means that there exists a *solution* to the problem that can be computed in "polynomial time". This just means that it can be computed in n^x, where x is some integer, and n^x is n to some power x. So, many algorithms are n^2 (quadratic time), n^3 (cubic time), etc. In fact, n^1000000 is still considered a "polynomial time" solution for a problem. Without getting too technical, something is generally considered "computable on a deterministic computer in finite time" if it has a polynomial solution.
Problems that are in NP have polynomial solutions ONLY on a nondeterministic machine. That is, while they may be solved in n^x steps on a nondetermistic machine, they require some infinite (undefined) number of steps on a deterministic machine. A good example would be a problem that requires n! (n factorial) steps to complete on a linear deterministic machine, yet may only require n^2 steps on a nondeterministic machine.
So, getting back to the original point, non-deterministic just refers to a machine that can compute any solution to exponential, factorial, or otherwise non-polynomial time deterministic solutions in polynomial time.
The best example of this might be how encryption works. RSA encryption involves two very large prime numbers p and q. RSA encryption involves a problem that is in NP, and that is how it maintains security. Files are encrypted by (p-1)(q-1). This number is nearly impossible to factor back to p and q, without knowing p or q. That is to say, prime number factorization for very large numbers is a problem that is in NP. A solution to this problem requires an infinite amount of computing time.
However, given either p or q, unraveling the math becomes trivial. In fact, the solution can be found in constant (n^0) time, which is very fast indeed. That is to say, if I give you (p-1)(q-1) you may spend the rest of your natural life trying to find p and q if they are large enough, however given p or q, you can verify the results in mere seconds on even the most basic calculator.
A nondeterministic computer could factor (p-1)(q-1) to obtain p and q in polynomial time. This would mean that all encryption that is based on problems that exist in NP would be rendered obsolete. Its just a really fast way of solving complicated problems.
I hope any of that made sense... I just don't want to make it sound like any of it has to do with awareness or any such thing, it really doesn't. Its just part of "computational theory".