Consider the algorithm "M(x): if x<0 return -x, else return M(x-M(x-1))/2". This algorithm terminates for all real x, though this is not so easy to prove. In fact, Peano Arithmetic cannot prove the statement "M(x) terminates for all natural x". Paper to come! Joint work with @jeffgerickson and @alreadydone
@gnivasch @jeffgerickson @alreadydone And termination follows from the fact that each recursive call jumps over at least one discontinuity, so well-ordering implies that infinitely-deep recursion is impossible?
@11011110 @jeffgerickson @alreadydone M(3) = 2^-1541023937. But Python should be able to get to something like M(3 - 2^-5)
@gnivasch I tried that in Haskell, the denominator is 5552 digits, way too big for floating point precision.
@11011110 @jeffgerickson @alreadydone Not \(\omega^\omega\), but \(\varepsilon_0\)