Quite a lot of interest originated from the following puzzle of unknown origin:
Given two pieces of rope which burn in precisely 1 minute, time an interval of 45 seconds (3/4 minutes). The rope is not necessarily uniform, so you’re not allowed to measure 3/4 of the way along it.
The solution is to light three of the four ends of rope. When one rope burns completely (at t = 1/2), light the fourth end. This will take another 1/4 minute to burn.
If we allow infinitely many pieces of rope, what intervals of time can be measured? Trivially, we can measure time 0. If we can measure time x, then we can also measure time x+1 by lighting a fuse at the end of it. Also, given two times x and y within 1 minute of each other, we can measure time (x+y+1)/2, by lighting one end of a rope at time x and the other at time y. We abbreviate this to x ~ y, where the swung dash is pronounced ‘fuse’.
The set of fusible numbers has some nice properties. For instance, it’s closed under addition (pretty trivial to prove) and well-ordered (not so easy). The latter property is more interesting, since it means there is an order-preserving map from the fusible numbers to a bunch of ordinals.
Let’s consider fusible numbers below 1. We can time 1/2 and 3/4, as in the original puzzle. Continuing this process, all numbers of the form 1 – 2^-n can be measured:
1/2, 3/4, 7/8, 15/16, …, 1.
In this instance, 1 behaves like the ordinal ω, being a limit point. We then proceed to get more limit points, such as 5/4 (2ω) and 11/8 (3ω). These all converge to a ‘double limit point’, 3/2, which we can associate with ω^2. Continuing in this manner, we get 3/2 (ω^3), 7/4 (ω^4) and so on until we reach 2 (ω^ω).
Adding 1 to a fusible number x is equivalent to raising ω to the ordinal representation of x. This means that the integer n is equivalent to the ordinal ω^ω^ω^ … ^ω (with n omegas), and we get all ordinals below epsilon-nought in this manner.
Due to well-ordering, we can ask ‘what is the smallest fusible number greater than n?’ As mentioned in this paper, we get:
- The smallest fusible number above 0 is 1/2;
- The smallest fusible number above 1 is 9/8;
- The smallest fusible number above 2 is 2 + 1/1024;
- The smallest fusible number above 3 is 3 + 2^-1541023937.
If you’ve seen fast-growing functions in combinatorics before, this should come as no surprise.
Actually, the smallest fusible number above 3 is smaller than 3+2^-(2^^^^^^^^^16) (using Knuth’s up-arrow notation – a^^^…^^^b (n+1 arrows) = a^^^…(n arrows)…^^^(a^^^…(n+1 arrows)…^^^(b-1)) )!!
As mentioned in this paper: http://arxiv.org/abs/1202.5614
The limit of the ordinals we can get in this process is still epsilon-nought, however.
Oh, wow, that function grows even more quickly than I imagined. Presumably -log2(m(k)) overtakes Graham’s number for a moderately small value of k?
Pingback: Fast-growing functions | Complex Projective 4-Space
Pingback: Alexandroff line | Complex Projective 4-Space
Pingback: Ordinal music | Complex Projective 4-Space