Miscellaneous > Programming & Networking

dictionaryism

(1/4) > >>

worker201:
Can anyone explain these terms in "for Dummies" language?

- Turing machine
- np-complete

Kintaro:
http://en.wikipedia.org/wiki/Turing_machine
http://en.wikipedia.org/wiki/Np-complete

worker201:
Jackass, I can find Wikipedia and read it.  In fact, I already read it.  I asked for a "dummies" version - language much simpler than Wikipedia.

Pathos:
The Turing machine is a abstract machine designed by Alan Turing. The whole idea is that it is the simplist possible machine that can compute ANYTHING that can possibly be computed given enough time (and the right information).

Some things (what does 2+3 equal) can be computed. Some can't (red is a better colour than blue). Alan Turing decided that the only way to identify what can and cannot be computed was to design this machine.

If a Turing Machine can be designed to compute something then that something is computable. If you can prove that something cannot be computed using a Turing Machine then that Something can never be computed by any computer no matter how much power/memory.

It is abstract because it only desribes how a Turing should work not how you would design it in reality.

Pathos:
NP is the set of problems take a polynomial time to compute.

Often this means for each item of data in the problem it will have to be used with EVERY other item to solve it. In this case adding a single piece of data to the problem will mean you will have to use this data with every other item all over again.

The problem is that just adding a couple more items to the problem multiplies the time it takes to solve. Thus if a problem is NP it is very easy to find problems that can take years to solve with very little data.

NP problems are bad because it can take so long to solve them and in some cases it probably never be possible to solve them using current computer theory (eg not quantum computers).

Navigation

[0] Message Index

[#] Next page