Some writers restrict the definition of algorithm to procedures that eventually finish.
In such a category Kleene 1952 places the "decision procedure or decision method or algorithm for the question" (Kleene p. 136). Others, including Kleene, include procedures that could run forever without stopping; such a procedure has been called a "computational method" (Knuth, Vol.1 p. 5) or "calculation procedure or algorithm" (Kleene); however, Kleene notes that such a method must eventually exhibit "some object" (Kleene).
Minksy makes the pertinent observation that if an algorithm hasn't terminated then we cannot answer the question "Will it terminate with the correct answer?":
"But if the length of the process is not known in advance, then 'trying' it may not be decisive, because if the process does go on forever -- then at no time will we ever be sure of the answer" (Minsky (1967)
Thus the answer is: undecidable. We can never know, nor can we do an analysis beforehand to find out. The analysis of algorithms for their likelihood of termination is called Termination analysis.
Download ebooks on http://www.frenchtheory.com/
See that post with different algorithms in metabole
See the journal French Metablog with today different posts
In such a category Kleene 1952 places the "decision procedure or decision method or algorithm for the question" (Kleene p. 136). Others, including Kleene, include procedures that could run forever without stopping; such a procedure has been called a "computational method" (Knuth, Vol.1 p. 5) or "calculation procedure or algorithm" (Kleene); however, Kleene notes that such a method must eventually exhibit "some object" (Kleene).
Minksy makes the pertinent observation that if an algorithm hasn't terminated then we cannot answer the question "Will it terminate with the correct answer?":
"But if the length of the process is not known in advance, then 'trying' it may not be decisive, because if the process does go on forever -- then at no time will we ever be sure of the answer" (Minsky (1967)
Thus the answer is: undecidable. We can never know, nor can we do an analysis beforehand to find out. The analysis of algorithms for their likelihood of termination is called Termination analysis.
Download ebooks on http://www.frenchtheory.com/
See that post with different algorithms in metabole
See the journal French Metablog with today different posts
No comments:
Post a Comment