April 28th, 2003, 03:52 AM
Algorthm help required
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.
April 28th, 2003, 04:26 AM
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 !
April 28th, 2003, 12:51 PM
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)
April 28th, 2003, 04:39 PM
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.
Suppose that HALT(x,y) were computable, then we could construnct the program
Let y0 thne number of the program so constructed, then we have:
[A] IF HALT(X,X) GOTO A
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
April 28th, 2003, 11:26 PM
You've been reading CRYPTONOMICON, haven't you?
April 30th, 2003, 04:12 PM
No, I've not read CRYPTONOMICON, I've only done an examination of theoretical computer science (BLEAHHH...).