Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
April 28th, 2003, 04:52 AM
 Mary22
Junior Member

Join Date: Apr 2003
Posts: 1
Time spent in forums: < 1 sec
Reputation 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
April 28th, 2003, 05:26 AM
 anu_sh
Junior Member

Join Date: Apr 2003
Posts: 3
Time spent in forums: < 1 sec
Reputation 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
April 28th, 2003, 01:51 PM
 infamous41md
not a fan of fascism (n00b)

Join Date: Feb 2003
Location: ct
Posts: 2,756
Time spent in forums: 2 Days 11 h 4 m 29 sec
Reputation Power: 94
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
April 28th, 2003, 05:39 PM
 M3xican
Junior Member

Join Date: Apr 2003
Location: Italy -> Naples
Posts: 9
Time spent in forums: < 1 sec
Reputation Power: 0
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
April 29th, 2003, 12:26 AM
 rfc791
unix hermit

Join Date: Apr 2003
Location: http://www.rfc791.org
Posts: 18
Time spent in forums: < 1 sec
Reputation Power: 0
You've been reading CRYPTONOMICON, haven't you?

#6
April 30th, 2003, 05:12 PM
 M3xican
Junior Member

Join Date: Apr 2003
Location: Italy -> Naples
Posts: 9
Time spent in forums: < 1 sec
Reputation Power: 0
no...

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

 Viewing: Dev Shed Forums > Programming Languages - More > Software Design > Algorthm help required