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. 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
3. 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)
4. #### 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)

This is only a small proof of this sucx... hem... beautiful and useful subject
5. You've been reading CRYPTONOMICON, haven't you?
6. #### no...

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