Democratic Underground Latest Greatest Lobby Journals Search Options Help Login
Google

Hey computer super geniuses:

Printer-friendly format Printer-friendly format
Printer-friendly format Email this thread to a friend
Printer-friendly format Bookmark this thread
This topic is archived.
Home » Discuss » The DU Lounge Donate to DU
 
aePrime Donating Member (676 posts) Send PM | Profile | Ignore Thu Aug-25-05 06:25 PM
Original message
Hey computer super geniuses:
Show that determining if two Turing machines, M and N, are equivalent is undecidable.

For extra credit, prove either P = NP or P != NP.
Printer Friendly | Permalink |  | Top
Crazy Guggenheim Donating Member (1000+ posts) Send PM | Profile | Ignore Thu Aug-25-05 06:27 PM
Response to Original message
1. Not clearly stated. Put in some commas.
:popcorn: :popcorn: :popcorn:
Printer Friendly | Permalink |  | Top
 
DS1 Donating Member (1000+ posts) Send PM | Profile | Ignore Thu Aug-25-05 06:29 PM
Response to Original message
2. paging English Geniuses, need help with this thread STAT
Printer Friendly | Permalink |  | Top
 
aePrime Donating Member (676 posts) Send PM | Profile | Ignore Thu Aug-25-05 06:39 PM
Response to Reply #2
6. Two complaints...
and I can't see what the problem is. I must have done something wrong.
Printer Friendly | Permalink |  | Top
 
DS1 Donating Member (1000+ posts) Send PM | Profile | Ignore Thu Aug-25-05 06:41 PM
Response to Reply #6
9. then I don't understand the question
and should have heeded the title of the thread
Printer Friendly | Permalink |  | Top
 
Spinzonner Donating Member (1000+ posts) Send PM | Profile | Ignore Thu Aug-25-05 06:31 PM
Response to Original message
3. Not computer, Mathematics

and I thought the DU rules said there would be no math.
Printer Friendly | Permalink |  | Top
 
aePrime Donating Member (676 posts) Send PM | Profile | Ignore Thu Aug-25-05 06:33 PM
Response to Reply #3
4. Computation is mathematics.
Can't have computers without a lot of math!

Computer Science != programming.
Printer Friendly | Permalink |  | Top
 
FloridaPat Donating Member (1000+ posts) Send PM | Profile | Ignore Thu Aug-25-05 06:38 PM
Response to Reply #4
5. Computers only add and subtract the number 1. Everything else is
a variation of that.
Printer Friendly | Permalink |  | Top
 
Spinzonner Donating Member (1000+ posts) Send PM | Profile | Ignore Thu Aug-25-05 06:39 PM
Response to Reply #4
7. Computers = electronics

You can do lots of math without computers. They somehow managed for a couple of thousand years - at least.

Turing machines are conceptualized automata. You don't need actual machines to do the exercise.
Printer Friendly | Permalink |  | Top
 
Jamastiene Donating Member (1000+ posts) Send PM | Profile | Ignore Thu Aug-25-05 06:47 PM
Response to Reply #3
11. I'm with you. I do enough math homework in PreCalculus Algebra. My brain
can only handle so many numbers in one week.
Printer Friendly | Permalink |  | Top
 
LSK Donating Member (1000+ posts) Send PM | Profile | Ignore Thu Aug-25-05 06:41 PM
Response to Original message
8. answering extra credit only
Edited on Thu Aug-25-05 06:41 PM by LSK
P = NP only if N = 1

P != NP if N != 1

PArt 1 : :wtf:
Printer Friendly | Permalink |  | Top
 
aePrime Donating Member (676 posts) Send PM | Profile | Ignore Thu Aug-25-05 07:26 PM
Response to Reply #8
12. I've got to give you credit for trying
But I meant P and NP as in classes of problems.

Polynomial time problems and non-deterministic polynomial time problems. It was a trick question, because nobody's yet proven the P versus NP problem. It is one of the Clay Institute's Millennium problems.

http://www.claymath.org/millennium/P_vs_NP/
Printer Friendly | Permalink |  | Top
 
Crazy Guggenheim Donating Member (1000+ posts) Send PM | Profile | Ignore Thu Aug-25-05 07:29 PM
Response to Reply #12
13. You sure as hell fooled me .........
Edited on Thu Aug-25-05 07:33 PM by Crazy Guggenheim
Printer Friendly | Permalink |  | Top
 
ghostsofgiants Donating Member (1000+ posts) Send PM | Profile | Ignore Thu Aug-25-05 06:42 PM
Response to Original message
10. Turing Machine...I love their song "Swiss Grid"
Printer Friendly | Permalink |  | Top
 
DU AdBot (1000+ posts) Click to send private message to this author Click to view 
this author's profile Click to add 
this author to your buddy list Click to add 
this author to your Ignore list Thu Dec 26th 2024, 11:22 AM
Response to Original message
Advertisements [?]
 Top

Home » Discuss » The DU Lounge Donate to DU

Powered by DCForum+ Version 1.1 Copyright 1997-2002 DCScripts.com
Software has been extensively modified by the DU administrators


Important Notices: By participating on this discussion board, visitors agree to abide by the rules outlined on our Rules page. Messages posted on the Democratic Underground Discussion Forums are the opinions of the individuals who post them, and do not necessarily represent the opinions of Democratic Underground, LLC.

Home  |  Discussion Forums  |  Journals |  Store  |  Donate

About DU  |  Contact Us  |  Privacy Policy

Got a message for Democratic Underground? Click here to send us a message.

© 2001 - 2011 Democratic Underground, LLC