2
$\begingroup$

According to Knuth's notes (see Slide 3), an algorithm, by definition, satisfies the following five properties:

  1. Finiteness: Terminates after a finite number of steps.

  2. Definiteness: Each step is precisely defined.

  3. Input: Has zero or more inputs.
  4. Output: Has one or more outputs, each of which has a specified relation to the inputs.
  5. Effectiveness: All operations are sufficiently basic that they may be performed exactly and in finite length.

Is there a term for something that satisfies steps 2-5 and also 1 with the word finite replaced by countable?

$\endgroup$
14
  • $\begingroup$ If it is an infinite number of steps, how do you even define "terminates"? $\endgroup$
    – Clement C.
    Oct 26, 2015 at 13:21
  • $\begingroup$ @ClementC. By "terminates", I mean that an output is produced after a countable number of steps. This doesn't make sense in real-life obviously, but we could make it precise in an abstract or mathematical sense. $\endgroup$
    – P. Turner
    Oct 26, 2015 at 13:28
  • $\begingroup$ The whole purpose with algorithm is to calculate the answer. If it has infinite number of steps it is practically useless (=impossible). $\endgroup$
    – A.Γ.
    Oct 26, 2015 at 13:29
  • $\begingroup$ @P.Turner One way to make sense of this question could be to look at randomized algorithms, whose expected running time is $t(n)$ for some function $t$. (see the class ZPP, for instance.) Note that the algorithm will still terminate in a finite number of steps with probability $1$; but that number could be arbitrarily large (although with very small probability). $\endgroup$
    – Clement C.
    Oct 26, 2015 at 13:31
  • 1
    $\begingroup$ @A.G. Yes, I agree. But that does not negate the fact that I need a term for something with the specified property. $\endgroup$
    – P. Turner
    Oct 26, 2015 at 13:31

1 Answer 1

3
$\begingroup$

You should check out

$\endgroup$

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.