Transfinite algorithms The Ford-Fulkerson algorithm is a classic algorithm that computes the maximum flow in a network.  It is well-known that if irrational arc capacities are allowed, the algorithm does not necessarily terminate.  However, the algorithm does satisfy the following properties.
(1) It can begin in any valid state (any valid flow can be used to initialize Ford-Fulkerson).
(2) At each step of the algorithm, there may be more than one choice, and the algorithm chooses arbitrarily between them (there may be more than one augmenting path, and Ford-Fulkerson chooses one arbitrarily).
(3) If the algorithm does not terminate, it converges to a (not necessarily optimal) state (if Ford-Fulkerson does not terminate, it converges to a (not necessarily maximum) flow). 
Note that (3) is in contrast to algorithms which do not terminate because they cycle, such as certain pivoting rules of the Simplex algorithm.  
Whenever a non-terminating algorithm satisfies the above properties, we can regard it as a transfinite algorithm whose run-time is an ordinal number as follows. If a run of the algorithm terminates after a finite number of steps, then its run-time is the corresponding finite ordinal.  Otherwise, by (3) it converges to some state $S$.  By (1) we can let $\omega$ steps pass and reinitialize the algorithm beginning with $S$.  We then recurse.  The (worst-case) ordinal run-time is the worst run-time over all valid runs of the algorithm (there are multiple possible runs by (2)).   

Question. Are there other examples of non-terminating algorithms which satisfy properties (1), (2), and (3)?  If so, have their ordinal run-times been analyzed?

In this paper, Spencer Backman and I proved that the ordinal run-time of the Ford-Fulkerson algorithm on a network with $m$ arcs is $\omega^{\Theta(m)}$.  The only other example we know of is chip firing on metric graphs, by Backman.  We are aware of the work of Hamkins and Lewis on Infinite Time Turing Machines, but as far as we can tell the above question is of a slightly different flavour.
 A: There are many algorithms in machine learning that seem to fit your formal definition, but don't seem to produce anything useful when you analyze them in your model.
Hill climbers or SGD are a good example of this. If you add an oracle for determining that you are at the global optimum, a hill climbing algorithm can be run until it finds a local optimum, then thrown into an infinite loop in which it stays in place. It only actually terminates at the global optimum.
Even when run on a simple curve like $\sin(x)/x$ it is possible for the algorithm to never find the global optimum.
Worse, your algorithm could enter a "transfinite loop" where, although no individual run of the algorithm loops, running it starting with $x$ converges to $y$ and running it starting with $y$ converges to $x$.
A: In this paper Jay Kienzle and I consider traversal algorithms over infinite, well-ordered graphs. The situation is a little different than your conditions (1)-(3): the algorithms are deterministic and the graphs are infinite, but the algorithms are transfinite with a well-defined ordinal "run time." Moreover, this paper is explicitly concerned with deriving tight upper bounds for said run times in terms of the order type of the original graph. So in that sense, I think this paper is close to the spirit of your question.
