#1
  1. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2003
    Posts
    1
    Rep Power
    0

    Algorthm help required


    Hi

    Can someone explain to me or point me in the right direction in answering the following question? Please dont just say Yes/No

    Can we always find an algorithm to solve a problem?


    any help is appreciated.
    thanks alot
  2. #2
  3. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2003
    Posts
    3
    Rep Power
    0
    You can't find an algorithm to solve a problem.
    Algorithm is to formulate solution of a past-problem
    for easing programming.
    But the moment you get solution of a problem
    It's no more a problem.
    More accurately, you don't have solution of any problem.
    Hope this clears ur question !
    Anupam
  4. #3
  5. not a fan of fascism (n00b)
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Feb 2003
    Location
    ct
    Posts
    2,756
    Rep Power
    95
    i interpreted this question as meaning, is every problem solvable? i dont know if that's u meant, but the obvious answer is no. an example? write an algorithm that can factor numbers as large as X * 10^100! (in a reasonable amount of time please). if u can do this you'll be a rich rich rich riiiiiiiich person,(or be kidnapped by the NSA)
  6. #4
  7. Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2003
    Location
    Italy -> Naples
    Posts
    9
    Rep Power
    0

    Lightbulb No, an example: HALT....


    An answer is not so simple... In fact ther's a subject that studies this question, it's theoretical computer science.

    However the right answer is no, cause we never can solve the HALT problem.
    HALT is (should be) a predicate that for every y (y is a number that identifies a program in an univocal way) can says if y stop or not on input x.
    Well, HALT(x,y) is not a computable predicate.

    Proof:
    Suppose that HALT(x,y) were computable, then we could construnct the program
    Code:
    [A]     IF HALT(X,X) GOTO A
    Let y0 thne number of the program so constructed, then we have:
    HALT(x,y0) <=> ~HALT(x,x)
    but if we set x=y0
    HALT(y0,y0) <=> ~HALT(y0,y0)
    that is a contradiction.

    This is only a small proof of this sucx... hem... beautiful and useful subject
  8. #5
  9. unix hermit
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2003
    Location
    http://www.rfc791.org
    Posts
    18
    Rep Power
    0
    You've been reading CRYPTONOMICON, haven't you?
  10. #6
  11. Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2003
    Location
    Italy -> Naples
    Posts
    9
    Rep Power
    0

    Smile no...


    No, I've not read CRYPTONOMICON, I've only done an examination of theoretical computer science (BLEAHHH...).

IMN logo majestic logo threadwatch logo seochat tools logo