Question: Consider the following program. Does $f(1)=\infty$?

\begin{align*} f(i):=&|\text{while } \frac{1}{i}>0\\ &||i\leftarrow i+1\\ &|i \end{align*}

I would say that $f(1)=\infty$ is a true statement. The program does not terminate, but one could consider the sequence of points $\{x_i\}_{i\in \mathbb{N}}$ given by $x_i:=\frac{1}{i}$, so that $\{x_i\}_{i\in \mathbb{N}}$ converges to the limit $0$ which makes $\underbrace{\frac{1}{i}}_{=0}>0$ false which means $f(1)=\infty$. However, I could be wrong.

  • The line $||i\leftarrow i+1$ add 1 to the original variable $i$? – gimusi Sep 24 at 13:25
  • 1
    Yes, that is exactly what that means. So, $\frac{1}{1}>0$ is true in the beginning so then we add $1$ to $i$ which looking at the precondition we know $\frac{1}{2}>0$ is true. This loop continues over and over until the statement is false. – W. G. Sep 24 at 13:29
  • For strictly positive inputs $i$, the algorithm never terminates. In fact, the loop criterion $\frac{1}{i}>0$ can be simplified to $i>0$, except that the former is ill-defined when the denominator is zero. For the strictly positive inputs, repeatedly incrementing $i$ by one does not change the fact that $i$ is positive. If we keep the $\frac{1}{i}>0$, for negative integer inputs and the input $0$ (zero), the criterion eventually involves division by zero which is not usually defined. For negative inputs that are not integer, after a number of iterations, $0<i<1$ at which time $i$ is returned. – Jeppe Stig Nielsen Sep 24 at 14:34
  • 1
    @JeppeStigNielsen For any negative input, integer or not, the iteration fails on the first step because $$-|x|^{-1} < 0$$ – twalberg Sep 24 at 16:10
  • Depends on the programming language most programming languages round the result so $1/n$ might equal $0$ for some $n$. – kingW3 Sep 24 at 16:57
up vote 1 down vote accepted

The final result of the function would depend on the method of division you'd end up using, at least if this function is executed by a computer.

One thing we can be sure of, however, is that the result of f(1) will under no circumstance be 0.

After all, the input of the function is 1 and the loops keeps increasing the value of i.

For example, if the function is executed using integer division, (1 / 2) > 0 would be false, and the function would end up yielding a result.

However, the result would be 2, not 0.

Therefore, the function either runs out of resources, or returns something larger than 0 - but never 0.


Although I'm answering this question as a programmer, rather than as mathematician, the logic remains true whether it be mathematical or programmatic: Even if we assume the loop can run to infinity, and we assume 1 divided by infinity as greater than 0, the function would produce infinity, not 0.

Pure logic dictates that f(1) != 0, whichever notation is preferred :)


Since I'm writing this as a programmer on the internet anyway, I might as well provide proof along with this answer.

I wrote the following snippet:

<?php

function f($i) {
    while ((1 / $i) > 0) {
        $i = increase($i);
    }
    return $i;
}

function increase($n) {
    if ($n < 100) {
        return $n + 1;
    }
    return INF;
}

(I would have used if ($n < INT_MAX) but that results in a 3+ seconds runtime)

Long story short, assert(f(1) === INF); passes, and

dump(f(1));

Is indeed float(INF).

Run this code

  • I am going to edit the question slightly. So, assuming the loop does go to infinity does imply that $f(1)=\infty$? – W. G. Sep 24 at 21:02
  • If 1/∞ > 0, then yes. – Stratadox Sep 24 at 22:55
  • ...what I meant is if !(1/∞ > 0), then yes, f(1)=∞ – Stratadox Sep 24 at 23:05
  • Actually, here's an example of your function. It's written in php and has the explicit assumption that after 100 comes infinity. Since floating point arithmetic agrees that !(1 / INF) > 0, the example indeed produces float(INF) when ran. – Stratadox Sep 24 at 23:14
  • 1
    It's the concept of infinity as described by the language the example is ran in :) Floating point arithmetic has its own concept of infinity, which I assume comes pretty close to a mathematically accepted definition. – Stratadox Sep 24 at 23:21

The only thing we can say here is that $f(1)$ is not defined, or that the program does not terminate for the input $1$.

We cannot say that $f(1)=0$.

  • If I understand this correctly, the term "total correctness" of the program requires the program to terminate which is often considered in proofs. However, why is that $f(1)$ is not defined in the mathematical sense? Is it required to finite? – W. G. Sep 24 at 13:37
  • 4
    @W.G. $f(1)$ is not defined because $f$ does not terminate for the input $1$. It's as simple as that. – 5xum Sep 24 at 13:42
  • I am not trying to rock the boat here or anything, but I agree that the program does not terminate. Any computer would say that $f(1)$ makes no sense . However, we know that the loop continues on forever. Every iteration for the NATURAL NUMBERS, can be proved inductively to show that $\frac{1}{i}>0$ is true. Assuming the loop is finite would be wrong. The loop must go on forever. If the loop was finite, the program clearly would not exist as $\frac{1}{i}>0$ would always be true never giving an output. As the loop goes on to infinity, why can't we assume $i$ goes to infinity? – W. G. Sep 24 at 13:53
  • 3
    @W.G. You can if you want to, but then you must specifically state how you evaluate programs that "go to infinity". In mathematics, you can play with whatever tool you want, but you must first decide how to use the tools. Limits are one such rigorous tool for dealing with infinity. Computer programs, as usually defined, are not - so you must expand their definition. – 5xum Sep 24 at 13:59
  • 1
    "Any computer would say that f(1) makes no sense" <- In all probability, any computer would probably consider f(1) == 0 a true statement, considering the most common course for a computer program in such case is to use either integer or, most likely, float division: with integer division, 1 / 2 = 0 and with float division 1 / lots = eventually considered equal to 0. This argument would not apply were the program written to handle the number as fraction, in which case the program either terminates in a division by zero or by running out of memory. – Stratadox Sep 24 at 18:53

It's a bit of a funny question. Looks like the best answer is "no." The number $1$ is not in the domain of $f$, because the program doesn't terminate.

It's true that as a human we can see that the in-memory value of $1/i$ is headed toward $0$, but $f$ was never going to return $1/i$, it was going to return $i$, which is headed off to $\infty$. Even if it were going to return $1/i$, the answer still shouldn't be $0$, because the program doesn't terminate and there's no notion of a limiting operation made explicit here.

The function is undefined at $i=1$ since $\not \exists b$ such that $b=f(1)$.

For a formal proof, indicating with $i_k$ the value assumed by $i$ at the $k^{th}$ loop, we can show by induction that $\forall k$

  • $i_k\ge 1 \implies \frac 1{i_k}>0$

therefore the loop will never end.

More in general $f(i)$ is undefined for any $i>0$ and $f(i)=i$ for any $i< 0$.

For $i=0$ it depends on how the "while" command returns to the operation $1/0$.

Instead of a while-loop, a better programming analogy of limits is the lazy list.

In Haskell:

naturals = [1..]
my_limit = [1/n n <- naturals]
take 100 my_limit

Outputs:

[1.0,0.5,0.3333333333333333,0.25,0.2,0.16666666666666666,0.14285714285714285,0.125,0.1111111111111111,0.1,9.090909090909091e-2,8.333333333333333e-2,7.692307692307693e-2,7.142857142857142e-2,6.666666666666667e-2,6.25e-2,5.8823529411764705e-2,5.555555555555555e-2,5.263157894736842e-2,5.0e-2,4.7619047619047616e-2,4.5454545454545456e-2,4.3478260869565216e-2,4.1666666666666664e-2,4.0e-2,3.8461538461538464e-2,3.7037037037037035e-2,3.571428571428571e-2,3.4482758620689655e-2,3.333333333333333e-2,3.225806451612903e-2,3.125e-2,3.0303030303030304e-2,2.9411764705882353e-2,2.857142857142857e-2,2.7777777777777776e-2,2.702702702702703e-2,2.631578947368421e-2,2.564102564102564e-2,2.5e-2,2.4390243902439025e-2,2.3809523809523808e-2,2.3255813953488372e-2,2.2727272727272728e-2,2.2222222222222223e-2,2.1739130434782608e-2,2.127659574468085e-2,2.0833333333333332e-2,2.040816326530612e-2,2.0e-2,1.96078431372549e-2,1.9230769230769232e-2,1.8867924528301886e-2,1.8518518518518517e-2,1.818181818181818e-2,1.7857142857142856e-2,1.7543859649122806e-2,1.7241379310344827e-2,1.694915254237288e-2,1.6666666666666666e-2,1.639344262295082e-2,1.6129032258064516e-2,1.5873015873015872e-2,1.5625e-2,1.5384615384615385e-2,1.5151515151515152e-2,1.4925373134328358e-2,1.4705882352941176e-2,1.4492753623188406e-2,1.4285714285714285e-2,1.4084507042253521e-2,1.3888888888888888e-2,1.36986301369863e-2,1.3513513513513514e-2,1.3333333333333334e-2,1.3157894736842105e-2,1.2987012987012988e-2,1.282051282051282e-2,1.2658227848101266e-2,1.25e-2,1.2345679012345678e-2,1.2195121951219513e-2,1.2048192771084338e-2,1.1904761904761904e-2,1.1764705882352941e-2,1.1627906976744186e-2,1.1494252873563218e-2,1.1363636363636364e-2,1.1235955056179775e-2,1.1111111111111112e-2,1.098901098901099e-2,1.0869565217391304e-2,1.0752688172043012e-2,1.0638297872340425e-2,1.0526315789473684e-2,1.0416666666666666e-2,1.0309278350515464e-2,1.020408163265306e-2,1.0101010101010102e-2,1.0e-2]

In Python:

import itertools
naturals = itertools.count(1)
my_limit = (1/n for n in naturals)
list(itertools.islice(my_limit, 100))

Outputs:

[1.0, 0.5, 0.3333333333333333, 0.25, 0.2, 0.16666666666666666, 0.14285714285714285, 0.125, 0.1111111111111111, 0.1, 0.09090909090909091, 0.08333333333333333, 0.07692307692307693, 0.07142857142857142, 0.06666666666666667, 0.0625, 0.058823529411764705, 0.05555555555555555, 0.05263157894736842, 0.05, 0.047619047619047616, 0.045454545454545456, 0.043478260869565216, 0.041666666666666664, 0.04, 0.038461538461538464, 0.037037037037037035, 0.03571428571428571, 0.034482758620689655, 0.03333333333333333, 0.03225806451612903, 0.03125, 0.030303030303030304, 0.029411764705882353, 0.02857142857142857, 0.027777777777777776, 0.02702702702702703, 0.02631578947368421, 0.02564102564102564, 0.025, 0.024390243902439025, 0.023809523809523808, 0.023255813953488372, 0.022727272727272728, 0.022222222222222223, 0.021739130434782608, 0.02127659574468085, 0.020833333333333332, 0.02040816326530612, 0.02, 0.0196078431372549, 0.019230769230769232, 0.018867924528301886, 0.018518518518518517, 0.01818181818181818, 0.017857142857142856, 0.017543859649122806, 0.017241379310344827, 0.01694915254237288, 0.016666666666666666, 0.01639344262295082, 0.016129032258064516, 0.015873015873015872, 0.015625, 0.015384615384615385, 0.015151515151515152, 0.014925373134328358, 0.014705882352941176, 0.014492753623188406, 0.014285714285714285, 0.014084507042253521, 0.013888888888888888, 0.0136986301369863, 0.013513513513513514, 0.013333333333333334, 0.013157894736842105, 0.012987012987012988, 0.01282051282051282, 0.012658227848101266, 0.0125, 0.012345679012345678, 0.012195121951219513, 0.012048192771084338, 0.011904761904761904, 0.011764705882352941, 0.011627906976744186, 0.011494252873563218, 0.011363636363636364, 0.011235955056179775, 0.011111111111111112, 0.01098901098901099, 0.010869565217391304, 0.010752688172043012, 0.010638297872340425, 0.010526315789473684, 0.010416666666666666, 0.010309278350515464, 0.01020408163265306, 0.010101010101010102, 0.01]

Your question might be interpreted to ask what the last element of such a lazy list is.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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