0
$\begingroup$

I was reading some documents on web about finiteness property of an algorithm where it is mentioned that "The algorithm must always terminate after a finite number of steps." Does it mean that any Pseudocode does not contain infinite loop or it should be equivalent to Halting Turing Machine. I don't know whether the statement about finiteness property of an algorithm is correct or not. I have not found any reliable source for it and I have not read it in CLRS.

Please find the attachment for some links about this statement.
http://courses.cs.vt.edu/cs2104/Fall12/notes/T16_Algorithms.pdf [Page 3]
https://en.wikipedia.org/wiki/Algorithm_characterizations
https://www.cmpe.boun.edu.tr/~akin/cmpe223/chap1.htm

So, My question is, whether the statement "The algorithm must always terminate after a finite number of steps" is correct or not and whether my interpretation about this statement is correct or not and if it is incorrect then please correct it.
Please help.

$\endgroup$
2
$\begingroup$

Yes, an algorithm should always stop after a finite number of steps, otherwise we say that it doesn't halt. An algorithm that doesn't halt for certain inputs can be considered as partial functions (algorithms). Algorithms that work for any input are more useful.

An algorithm can be viewed as a function $f: \mathbb{N} \to \mathbb{N}$. if it is defined for all input values, we say that $f$ is "total" ; for an algorithm, it means that it halts for any input. On the other hand, if a function $f$ is "undefined" for an input, say $4$, we say that $f$ is a partial function, and in computation theory, we write $f(4)\uparrow$ meaning it "diverges", or simply "doesn't halt".

An example for a partial function can be the inverse of the integer square function, i.e. $sq(n) = n^2$. The inverse, $sq^{-1}$ is defined only on perfect squares, that is, $$sq^{-1}(n) = \cases{\sqrt{x} \text{ if $x$ is a perfect square} \\ \text{undefined otherwise.}}$$

$\endgroup$
  • $\begingroup$ Thank you :). Can you please explain partial functions and give some examples ? $\endgroup$ – ankit Apr 11 at 7:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.