Stop Microsoft

Miscellaneous => Programming & Networking => Topic started by: worker201 on 25 August 2005, 03:00

Title: dictionaryism
Post by: worker201 on 25 August 2005, 03:00

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

- Turing machine
- np-complete

Title: Re: dictionaryism
Post by: Kintaro on 25 August 2005, 04:48

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

Title: Re: dictionaryism
Post by: worker201 on 25 August 2005, 23:17

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.

Title: Re: dictionaryism
Post by: Pathos on 26 August 2005, 09:56

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.

Title: Re: dictionaryism
Post by: Pathos on 26 August 2005, 10:07

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

Title: Re: dictionaryism
Post by: Kintaro on 26 August 2005, 18:42

Quote from: 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.

It's not my fault your stupid, stupid.

Title: Re: dictionaryism
Post by: TheQuirk on 28 August 2005, 01:58

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

Title: Re: dictionaryism
Post by: Pathos on 28 August 2005, 12:36

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

Title: Re: dictionaryism
Post by: Kintaro on 1 September 2005, 20:16

(its because TheQuirk IS A RED)

Title: Re: dictionaryism
Post by: TheQuirk on 2 September 2005, 00:38

Quote from: Pathos

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.

Title: Re: dictionaryism
Post by: KernelPanic on 2 September 2005, 00:46

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

Title: Re: dictionaryism
Post by: Orethrius on 2 September 2005, 00:51

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

Title: Re: dictionaryism
Post by: Pathos on 6 September 2005, 14:37

...Richard Simmons...

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

Title: Re: dictionaryism
Post by: Orethrius on 6 September 2005, 16:25

Quote from: Pathos

...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?  :D

Title: Re: dictionaryism
Post by: Calum on 6 September 2005, 22:16

Quote from: KernelPanic

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

now i understand! a Turing machine is a lathe!

Title: Re: dictionaryism
Post by: MarathoN on 6 September 2005, 23:19

:D I wasn't sure what it was, but now that I know, that's funny.  ;)