dictionaryism

[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).

[Kintaro]

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.

It's not my fault your stupid, stupid.

[TheQuirk]

I searched Google for "turning machine" and thought it was really interesting stuff.

[Pathos]

Did you search for "Turning" or "Turing" machine???

[Kintaro]

(its because TheQuirk IS A RED)

[TheQuirk]

Did you search for "Turning" or "Turing" machine???

No, that was a typo. Had I searched for "turning," I would've noticed something was amiss from the first few results.

[KernelPanic]

I'd like to see you make a fruit bowl on a Turing machine.

[Orethrius]

Fair enough, get me Richard Simmons, a bowling ball, and a Turing machine.

[Pathos]

...Richard Simmons...

AAAHHHHHHHHH!!!! we hates him!! we hates him!!! It burns precious! It burns!!!

[Orethrius]

...Richard Simmons...

AAAHHHHHHHHH!!!! we hates him!! we hates him!!! It burns precious! It burns!!!

 He said he wanted me to make a fruit bowl on a Turing machine, what was I supposed to think?  

[Calum]

I'd like to see you make a fruit bowl on a Turing machine.

now i understand! a Turing machine is a lathe!