Running time of algorithms that sometimes loop forever

Consider the following algorithm that computes the sum of two integers (toy example):

INPUT: Integers (a,b)

 1. Toss a coin c
 2. If c = 0, then loop forever
 3. If c = 1, then compute and output a+b

What is the running time of this algorithm? The "strict" running time (defined as a strict upper bound on the running time over all inputs and all possible random choices of the algorithm) is infinite. The "expected" running time (defined as the average running time over all inputs and random choices) is infinite, too.

Thus, apparently this is an algorithm whose running time (strict/expected) is infinite. However, the algorithm still appears to be useful, since it produces a reasonable result with probability 1/2.

Is there a notion of "running time" in computer science that captures such algorithms? Can you point me to references or a textbook?

Thanks!

The textbook Computational Complexity: A Modern Approach by Arora and Barak looks at the class $ZTIME(T(n))$ (chapter 7), of algorithms whose expected running time is bounded by $T(n)$ (but which do not necessarily halt on all random seeds). This class cannot capture the notion you describe, because you are looking for a function whose range includes $\infty$, whereas Arora and Barak only look at time functions $T\colon \mathbb{N}\to \mathbb{N}$. Another close analogue to what you describe is $RE$, the class of problems recognizable by a Turing Machine which is only guaranteed to halt on yes-instances.

To my knowledge, even the Complexity Zoo doesn't cover algorithms with infinite expected running time. The reason, I suppose, that these algorithms aren't studied is twofold: (1) they are not useful, because an algorithm with an infinite running time produces no answer and (2) they are not needed to solve any problems that cannot be solved by a deterministic computer with a finite or unbounded running time. To see (2), imagine an algorithm $A$ for deciding membership in a language, in the sense that when it halts, it outputs the right answer, but it is not guaranteed to halt for all inputs. Then you can just do a breadth-first search on the configuration graph. The class of problems solvable with these restrictions is $RE$. If the algorithm is guaranteed to have at least one halting path, the class is $R$.

StackExchange Computer Science Q#68190, answer score: 5