1
$\begingroup$

I have encountered several times, while doing mathematics, the following situation: We have a finite "sequence" $\left(a_{n}\right)_{n\in\left\{ 1,\ldots,p\right\} }$ of some objects that has the (meta-mathematical) property that the value of $p$ isn't known beforehand - and we get it only if we " run''/''compile'' the "sequences" $\left(a_{n}\right)_{n\in\left\{ 1,\ldots,p\right\} }$ (hence the use of the " ", since this "sequence" isn't well defined if its domain isn't know at the time of its definition). So this is actually an algorithm, since in algorithm there also a "runtime" also doesn't have to be specified at the beginning.

  1. How can we get around this difficulty, i.e. how can we rigorously define $\left(a_{n}\right)_{n\in\left\{ 1,\ldots,p\right\} }$ ?

    I always thought that we translate the "sequences" $\left(a_{n}\right)_{n\in\left\{ 1,\ldots,p\right\} }$ to another mathematical object for which one doesn't need to specify how "long'' it can run. For example I could mimick one step of $\left(a_{n}\right)_{n\in\left\{ 1,\ldots,p\right\} }$ by a function $f$, such that $a_{2}=f(a_{1}),\ a_{3}=\left(f\circ f\right)\left(a_{1}\right)$ and so on and let $f$ attain some specific value $\alpha$, if the iteration wasn't succesful for. Then I could just define my $p$ as the smallest number such that $f$ equals $\alpha$ - and now I could rigorously define $\left(a_{n}\right)_{n\in\left\{ 1,\ldots,p\right\} }$.

  2. Is the above idea correct ? Do you know of other such methods ?

  3. There are of course algorithms such that only knowing the input there is a closed expression (involving only certain function - not arbitrary ones like my $f$ above) that tells me, how long my algorithm will run, but I don't think that that is the case for all algorithms. Is that true ? Can someone contribute something interesting ? (I know, I'm going slightly off-topic here).

  4. Is there an area in mathematics that deals with questions like 1.-2. ? Maybe proof theory? What about questions like 3. ?

Note: If you should ask me for examples of such "sequences" $\left(a_{n}\right)_{n\in\left\{ 1,\ldots,p\right\} }$ : The euclidean algorithm, the greedy algorithm for a minimal spanning tree of graph...actually take any maths book that contains the word "algorithm", since a (well-defined) algorithm is nothing but a finite sequence, for which we generally don't know yet, how long it will run (I haven't checked, if for these two algorithms there is a simple closed expression in terms of "classic'' functions, that determine beforehand how long they run...if there is, pretend you don't know it and have to take the route described in 1. to get your number of iterations until the algorithm terminates )

  • 0
    Would reading [Aho, Hopcroft & Ullman](http://www.amazon.com/Data-Structures-Algorithms-Alfred-Aho/dp/0201000237) help?2012-09-14
  • 0
    @JyrkiLahtonen Sadly no. I just browsed through in at the concept of algorithm isn't formalized there2012-09-14
  • 0
    Sorry, I think that the standard formalization of an algorithm is something that a [Turing machine](http://en.wikipedia.org/wiki/Turing_machine) can perform, and had a vague recollection that the concept would be explained in that book.2012-09-14
  • 3
    It looks like you're using the word "algorithm" with a somewhat different meaning than the one it usually has in mathematics. Certainly the claim "a (well-defined) algorithm is nothing but a finite sequence" does not at all describe the usual meaning of "algorithm".2012-09-14
  • 0
    @HenningMakholm Sorry for getting back so late. Indeed, it seems that my notation of an algorithm is a different one that usually accepted (is the usual notion of an algorithm something a Turing Machine can perfom, as Lahtinen indicated ?). But how is my notation different then the usual one ?2012-09-22
  • 2
    @temo: Yes, an algorithm is something a Turing machine can do. Your use of the word seems to be so different from that that I cannot see any similarity in meaning at all -- and thus I have no idea where to begin explaining "how are they different".2012-09-22
  • 0
    It seems like you're unhappy with the idea of a sequence that we don't know the length of. Such a sequence is still perfectly fine. For example, consider the sequence of twin primes. It might be finite, or it might be infinite. We don't know. But that doesn't mean that the sequence doesn't exist!2012-12-07

2 Answers 2