System Performance Degrade over time

Status
Not open for further replies.
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".
 
Damn, yet another abrupt left turn the thread took... You two are some of the most insightful thinkers I have met on this or any other forum... Hell, even amongst real people (and not in a forum) you guys still take the cake.

Since you seem to be interezsted in this sort of thing, which I am too (just dont know as much as either of you), I am going to suggest and scientist to you that you shuld read up on. michio Kaku, he is the inventor of the super-string theory (RIDICULOUSLY intereseting). I have a book of his called 'Visions' that talks about superstring and biotech, computer revolution, and the quantum revolution. In the quantum revolution and computer revolution sections, it totally gets into non-deterministic and quantum computing, as well as turing machines. If you have not yet read the book, I STRONGLY urge you to read it. Only would a mind like you two's (and obviously mine) would find it interesting and entertaining.

http://www.amazon.com/exec/obidos/t...102-1287236-7775367?v=glance&s=books&n=507846

$11 at Amazon, mere pennies compared to the amount of knowledge in that book. It is slightly old, circa 1998, so some of his computer info is a little outdated, but all the theorys are there and still stand strong. Again, strongly recommend it.
 
I'll check it out. I've always been interested in books like that. Last one in that vein that I read was "Three roads to quantum gravity." It was pretty interesting.

If you are at all interested in computational theory and nondeterminism, google up "NP Completeness" and read about the pretty interesting phenomenon that some problems, if solved, would mean that almost all computer problems would be solved. Also take a look at the "Halting Problem".
 
TheHeadFL said:
If you are at all interested in computational theory and nondeterminism, google up "NP Completeness" and read about the pretty interesting phenomenon that some problems, if solved, would mean that almost all computer problems would be solved. Also take a look at the "Halting Problem".

The ultimate computer problem, lol. Thats cool, I'm going to check that out. Look up Michio Kaku and Super String, also check Wikipedia as they have everything. Or howstuffworks.com. I found out how marijuana works from that site. If I can find out how pot works at that website, you can find out how anything works.

Kaku also has another book, 'Hyperspace', that is all about super string and wormholes and stuff. The good thing about him is that, even though he is a theoretical physicist, who are known for their incomprehendable way of writing, he does a pretty good job at laying it down in laymens terms. The thing that makes it so overwhelming is the amount of contect, which is ridiulously large. It is one of those books that I can only read a little bit at a time, and I have to have somethign easier nearby that I can go to. I've read a few books like that.

On a different note, philosophy. If you dig this stuff, i imagine you would find alot of the same things interesting that I find interesting, and one majorly interesting thing for me is Philosophy. There is a series of books, pop-culture and philsophy, where they have philisophists writing big essays on a certain aspect of, say, a movie for example. I use to have The Matrix and Philosophy, which was a very difficult read, but really good. A few other ones are The Lord of the Rings and Philosophy, Seinfeld an Philosophy, The Simpsons and Philosophy, and a few others. I am waiting for a Fight Club and Philosophy.
 
Philosophy always kinda made my head hurt. I took a class on Ethics in Science and Technology which was all philosophy... tough stuff to read.
 
Status
Not open for further replies.
Back
Top Bottom