Impredicativeness, recursion, and the Big Bang
or
The ascent of the wolf, the goat, and the cabbage up the steps of the Hanoi tower

 

A strange title, isn't it? There is an old proverb about this, which in a decent version sounds something like this: "Why does a goat need a button accordion?" But in fact, all the words and concepts used in this title are essentially interconnected. These connections deserve close attention and are considered by us in this article.
Note 1: In mathematical calculations, I use the Mathcad 15 program. The interface of this program is quite close to the commonly used mathematical language. I try to clarify cases of possible misunderstanding. In addition, all the mathematics of this article can be implemented in other packages, for example, in Excel.
Note 2: This article does not contain any mathematical discoveries. I only tried to draw attention to some well-known facts. The papers in which (I think) I said something new are at:

https://doi.org/doi:10.30970/ms.63.1.14-20
and at arXiv at:
https://arxiv.org/a/zhuravlov_v_1
msc: 11A99, 03A99, udc 511
Keywords: uncertainty relation, Russell's paradox, induction and recursion, Tower of Hanoi, number systems.

Introduction: Russell's Paradox and the Big Bang

     I once published the following text:
     "You say: recursion... You can, of course, object that none of you said anything like that. Well, and if you did say it, what could I tell you? Probably this.
     Everything possible always happens, if you wait long enough. The Universe is designed as if it arose at some point in the past. And according to the uncertainty principle Δ t*Δ E ≥ ℏ /2, the inaccuracy of fixing this initial moment generates the inaccuracy of the zero energy of the pre-universal vacuum. Therefore, a tunnel transition from a state with virtual non-zero energy to a state with real energy worked - the Big Bang happened, and the Universe arose... In short, Baron Munchausen pulled himself out of the swamp by his own hair! That's all there is to recursion - a fundamentally contradictory basis for everything infinite and any strict, impeccably consistent logic. That is This process of mutual determination of reality and concept was described by Hegel in his foggy philosophy, and then discovered in the most precise mathematics...
     So that's what it's all about! And you say - recursion, recursion...
     It is also true that recursion will not disappear anywhere, even if you and I forget not only to talk about it, but also to think about it... But can we not think about ourselves?"
     And immediately I received an objection: "a tunnel transition is not a recursion." This objection is absolutely fair and... is purely formal. That is, true in form, it is false in essence.
     When a tunnel transition occurs from a state with "zero" real energy (and an "infinite" range of virtual energies), we discover that the real state at the present moment of time determines states in the past. As a result, we have a process that determines itself. And this is the essence of the above-mentioned hypothesis of the Big Bang.
     But this is the meaning of mathematical induction and recursion - the object is self-determining (this time not in the physical world, but in arithmetic, natural or even ordinal). And this is the essence of the recursive process.
     Self-determination looks beautiful and paradoxical. However, this paradox is fraught with contradiction! Let us pay attention to the famous Russell paradox, which showed the impossibility of Cantor's "naive" (not very strict, not sufficiently formalized) set theory. "Is the set of all sets that are not its elements an element of itself?" The question is unsolvable: each answer entails its own negation. This paradox is avoided only by limiting, cutting down and clarifying the concept of a set. In one version, each set is considered an element of a certain universal set - a strongly limited analogue of the intuitive concept of "the set of all sets". In another version (in the theory of types), arbitrary collections of elements are called classes; sets are classes that are elements of other classes. The classes themselves have only elementary (algebraic) properties of sets. There are other options. In any case, we are talking about such formal restrictions of the concept of a set that would exclude the situation leading to Russell's paradox. One of the options seems to me to be the consideration of set theory in positive logic (in which there is no negation; since non-constructive negation leads to concepts of an excessively large volume, a contradiction in positive logic means the possibility of proving any assertion). It is also possible to construct set theory in quantum logic, in which entangled states of an assertion and its negation are possible...
     However, according to Gödel's incompleteness theorem, set theory is fundamentally incomplete. Therefore, a contradiction may arise not necessarily because of the emergence of Russell's paradox. The danger of contradictions may arise when considering "large enough" infinite sets. But these questions are beyond the scope of our article. Let's return to our... goats.

The Wolf, Goat, and Cabbage Problem

     We need to transport a live cargo across a river. The cargo is a wolf, a goat, and a head of cabbage. The wolf can eat the goat, and the goat can eat the cabbage. When we are nearby, the situation is under control and no one eats anyone. To cross, we use a small boat that can only fit one of these objects. How can we transport all three without losses?
     While we are transporting the wolf, the goat will eat the cabbage; while we are transporting the cabbage, the wolf will eat the goat. We can safely transport the goat. But then, if we go after one of the remaining ones, and then after the other, then either the wolf will eat the goat, or the goat will eat the cabbage - in our absence. So what should we do?
     We will see the solution if we pay attention to the relationships between all three objects. So: the wolf eats the goat, the goat eats the cabbage, but the wolf and the cabbage are mutually neutral. The central position is occupied by the goat: it can both eat and be eaten. In a chain of three links, the central link is the only one that has two hooks with its neighbors; the other two links have only one hook each. The solution is that the goat will have to be moved twice. We move it, safely leaving the wolf and the cabbage on the shore. Then we go back for the cabbage (or the wolf), and move the goat back, leaving the cabbage (or the wolf) on the opposite shore; and then we move the wolf (or the cabbage), leaving the goat on the shore; and only then we move the goat to the shore, where the wolf and the cabbage are safely waiting for us.
     Note: the solution lies in repeating actions that sometimes return some objects to their previous state. We can try to generalize the problem by increasing the length of the chain. However, then there will be more than one intermediate link - as soon as we sail away in a boat, they will begin to "devour" each other. Does the problem have generalizations? Yes! But then the situation becomes more complicated.

Tower of Hanoi

     There are three rods. The first one has n disks strung on it, ordered strictly by increasing diameter; the other two rods are empty. At each move we must move some disk from one rod to another. The condition is purely physical: we can only move the upper disk lying on an arbitrary rod. The second condition: we cannot put a larger disk on a smaller one. Our goal is to move all the disks to one of the pair of empty rods.
     The process goes something like this:

 
I will also cite an article that gives the formulation of the problem and its algorithmic solutions - iterative and recursive (the article is presented almost in full; unfortunately, it was written quite a long time ago: at the moment, I have lost information about the author):

---

Towers of Hanoi

Author: Bystrytsky V.D.
When writing the article, materials from the book by J. Arsak "Programming Games and Puzzles" were used.

     The 'Towers of Hanoi' puzzle is an old and well-known one, with several amusing legends tied to it, but the essence of the problem that I will try to consider using the example of this task is the use of recursive algorithms and their transformation into non-recursive ones.
     First, let's formulate the task. Given three rods ((0) - initial, (2) - final, (1) - additional) on rod (0) a certain number of disks are strung (we will assume it is equal to n) while all disks have different diameters and are located on rod (0) in order of decreasing diameter from bottom to top (see .gif). It is necessary to move all disks to rod (2); in this case, only one disk can be moved in one move, and as a result of the move, there should not be a situation where a disk with a larger diameter is placed on a disk with a smaller diameter.
     The choice of a particular strategy for moving disks leads to a new question: how many moves are needed for the puzzle to be completely solved. Moreover, it is obvious that the number of moves increases with the number of disks, and it is desirable to obtain some function f(n), which would give the number of moves required for a given strategy to solve the problem depending on the number of disks. The article considers only one strategy, the optimality of which can be proven. First, the strategy is derived as a recursive algorithm, and then reduced to a non-recursive form.

Recursive strategy

      So, we need to transfer n disks from rod (0) to rod (2). Let's assume that we have a procedure for transferring (n-1) disks, denoted as h(n-1, (0), (1)). Then the task can be easily solved as follows: first, we transfer (n-1) disks from rod (0) to rod (1), using procedure h, then transfer the n-th disk using procedure tr((0), (2)), and finally transfer (n-1) disks from rod (1) to rod (2). The work is done.
      Now we need a special case that is not recursive. If there is only one disk, we can immediately transfer it from rod (0) to rod (2). In this way, the identity holds. Thus, the procedure h can be represented as a flowchart.


      Simple? Yes, without a doubt, it is simple, but still, such a solution instills apprehension in some people. Why? Most likely, it indicates a lack of familiarity with recursive methods, though not exclusively. Recursive solutions differ from standard ones precisely because of their non-obviousness. What can be done to "believe" in the correctness of the presented strategy? In my opinion, the best way is to verify the strategy "practically" for small n.
      Let us return to the question of calculating the function f(n). For the presented recursive procedure, the mapping f(n) is fairly trivial:
f(1)=1
f(n)=2*f(n-1)+1
     The explicit form of the function f(n) is not difficult to determine from the above relations, using the principle of mathematical induction: f(n)=2ⁿ-1.
     In addition to this, let us note another property of the moving disks. Let our disks be numbered from 1 to n, so that the disk with the smallest diameter is number 1, the next largest is number 2, and so on, with the largest disk being number n. Then it can be observed that two disks with numbers of the same parity will never lie on top of each other (e.g., disk number 2 will not rest on disks numbered 4, 6, or 8). Let us prove that this property holds. The proof will proceed by induction. Assume that the property holds for the procedure h(p, (0), (1)) where де p < n (for p=1 and h(1, (0), (1))) the property holds automatically). We will then prove that it also holds for h(n, (0), (1)). We begin by transferring (n-1) disks to rod (1). Until disk (n-1) is moved, no disk is placed directly on disk number n. This ensures that the required property holds. Consider the moment when (n-2) disks are on one rod, disks numbered (n-1) and n are on another rod, and the third rod is empty. We then move disk (n-1). Next, we must move the first (n-2) disks onto disk (n-1), resulting in disks being placed on disk n. If disk number k is placed on disk n, then to form a pyramid of disks numbered from k to 1 and to allow disk (k+1) to be moved to disk (n-1), the parity of disk (k+1) must coincide with that of (n-1). However, since the required property holds for (n-1) disks, the parity of (k+1) coincides with that of n, and thus the parity of n and k is different.
      Those of you inclined towards meticulous analysis of proofs may find certain ambiguities. However, I assure you that these do not invalidate the proof; they are introduced solely for the sake of brevity.

Iterative Strategy

The iterative strategy is rooted in recursion, but the solution completely excludes recursion itself. This is beneficial from the perspective of understanding the algorithm in practice (now it can be "tangible"). This is not the recursive algorithm for "tipping" the Tower of Hanoi. Here is the method (I am not sure if it is described anywhere - I have not come across literature on this topic):

1. The order of optimal disk movement is unique and looks like this (the disks are numbered from 1-the smallest, and the steps are numbered starting from 1): step: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ... a disk that moves: 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 ... In the upper row-step numbering; in the lower row-disk numbering. It is easy to notice (if observed closely) that: 2. The numbers in the lower row represent the number of divisions without remainder (incremented by one) corresponding to the numbers in the upper row divided by 2. 3. During optimal disk movement, each disk successively occupies the same rods: even disks: {(0)-(2)-(1)} (in cycles); odd disks: {(0)-(1)-(2)} (in cycles), or vice versa-depending on the total number of disks and the target rod. To perform the movement, it is necessary to keep track of the current position of each disk. Then it's straightforward: determine which disk moves from where to where and execute the move.

nbsp;    In fact, this "tipping" algorithm emerges from the recursive one upon closer examination. Hence, we remove recursion and prove certain facts more or less rigorously.
nbsp;    First, note that under the constraints placed on disk movement, the disk numbered 1 is always located on the top of one of the rods. At any step, we can move either disk 1 or one of the disks (with the smallest diameter) positioned atop a rod other than the one holding disk 1. From this, we can conclude that disk 1 moves once every two steps; otherwise, the disk configuration would repeat. Let's demonstrate that disk 1 always moves according to one of two selected strategies: either {(0)-(1)-(2)} or {(0)-(2)-(1)}, with the choice of strategy depending on the parity of the total number of disks n. Disks always move in a single direction. For h(n,(0),(2)), we need to execute h(n-1,(0),(1)) and h(n-1,(1),(2)); that is, instead of transitioning directly from rod (0) to rod (2), we make this move using rod (1), effectively creating two reverse-direction moves. In this process, disk 1 continues to move consistently in the same direction, although its movement is altered during the transition from (n-1) to n.
nbsp;    In principle, this already enables us to outline the iterative algorithm for moving disks as follows:

      A decent algorithm if we intend to manually move the disks, though the phrase "move the only disk that can be moved, except disk 1" lacks sufficient specificity. Let's prove a critical statement:

The number of any step can be uniquely expressed as k=(2r+1)2^p-1.

      Thus, the first thing we need to prove is that, at step k, we move the disk numbered p. For p = 1, this is trivial since it indeed moves on every odd step. Returning to the recursive algorithm, note that moving disk pp only occurs within the procedure h(p,(rod1),(rod2)), and between two calls to this procedure, there is exactly one disk movement (algorithm h-m-h). The number of steps needed to execute the procedure h(p,(rod1),(rod2)) equals f(p). Thus, the first movement of disk p occurs at step f(p-1)+1=2^p-1. Each subsequent movement occurs every 2^p-1-1+1+2^p-1=2^p-1 steps. Therefore, the step numbers at which disk pp moves indeed follow k=(2r+1)2^p-1. Furthermore, as demonstrated, disks with odd numbers follow the same strategy as disk 1, while disks with even numbers follow the reverse strategy. This completes the proof. Thus, we can now concretize the iterative algorithm outlined above:


      I hope this article highlights the fact that recursion enables many problems to be solved elegantly and concisely-in "two lines." Addressing the same problem without recursion, however, leads to considerable challenges, even when starting with a recursive algorithm and attempting to simply rework it.

---

Formula-based solutions: determining the state of the tower at any moment in time

     Apart from being "non-obvious (implicit?)", recursive solutions have another drawback: they are time-consuming. The Tower of Hanoi problem resembles the famous legend in which a king asked the inventor of chess to name the desired reward. The inventor requested a mere trifle: 1 grain of wheat for the first square of the chessboard and twice as much for each subsequent square. The problem turned out to be technically and materially unsolvable. The same is true for the tower: it requires (2^u - 1) steps to transfer u disks to another rod, with all the resulting implications. The consolation is that the problem becomes easier if one finds a non-recursive solution in the form of an explicit formula, which calculates the state of the tower based on the number of steps needed for its construction. This way, there is no need to compute the tower's state at all previous steps. Moreover, this approach eliminates not only recursion but also iteration. Here is that formula:


This is the column of disk u on the n-th move; that is, the tower is represented as a matrix (row and column indexing starts at 0, purely for convenience in calculations; thus, the top row of the matrix is always 0, and the disks, which are always perfectly ordered by increasing diameter, range from 1 to u). The functions round( ) and mod( ,3) are the standard rounding and modulo 3 functions.
     This is a simple arithmetic formula that, through elementary functions, embodies the same ideas as the well-known Gray code algorithm, which is based on counting the number of bits required to move each disk.
     Algorithmically: the formula states that:
     1. On each move, only the disk that remained stationary on the previous move is moved.
     2. All disks move cyclically (modulo 3); specifically, even-numbered disks jump over a rod to the right, while odd-numbered disks move directly to the adjacent rod on the right. (Note that "even and odd" as well as "right and left" can be swapped simultaneously for all disks.)
     The value of this formula lies in the fact that it is neither recursive nor iterative: we can directly compute the state of the tower for any move number without tracing its prior states.
     I present this formula, along with all subsequent ones, without proofs (though I provide examples of how they work), as they are easily proven by induction-a characteristic trait of recursive processes. I derived these formulas independently and have not encountered them elsewhere.
However, I believe they pertain to well-established mathematical principles.
     In the reverse direction, the behavior changes if (u+1) in the power of 2 is replaced with u. This forms the algorithm for reverse progression: from a given tower state, by calculating the number of steps required to return to the initial state, we can determine the number of steps leading to the given state. However, this path is iterative, which, as we noted earlier, grows excessively long as the number of disks u increases. Alternatively, the initial state can also be reached using a direct formula to count the steps (which, in essence, is also an iterative method).
     Based on this formula, it is straightforward to construct a program that generates the matrix of tower u for the n-th move:

 

i.e. the program constructs a matrix where the number j (disk number by its diameter) is placed in the column (rod number) corresponding to move n. We begin with the zero disk, though this is not mandatory. In the absence of disks, zeros are placed (note that our disks can "hover in the air": they maintain a stable horizontal position, which does not affect the situation at all; later, we can easily incorporate "gravity").
     An illustration of the formula and the program's operation is a video demonstrating the movement of a tower of 7 disks to another rod:

       number.avi.

      After watching the video, we observe that:
      1. The disks are consistently well-ordered by their diameters, which is a requirement of the problem's conditions.
      2. Even- and odd-numbered disks always alternate, a point previously mentioned by Bystritsky in his article.
      3. Being non-recursive, our formula always works (not only for 7 disks), as tower movement is inherently recursive: to construct a larger tower, one must first construct a smaller one twice, as Bystritsky noted.
      4. The formula confirms: moving a tower of n disks requires (2ⁿ-1) steps (127 for (n = 7)). Unlike the constructive (recursive) algorithm, the formula enables rapid determination of the tower configuration, even for very large n. In contrast, the algorithm may lead to a frustrating scenario timewise, making the task practically unattainable. Nonetheless, there are situations where the practical execution of the task may only be feasible through recursion... This is not merely a conflict between constructive mathematics and formal mathematics. It represents a discrepancy between thought and reality, a mystery as profound as their correspondence. This forms the basis of the eternal questions of philosophy.

Inverse problem

     How can one determine the move number at which a given tower configuration arose? To address this, we require an auxiliary program:


- this is a cyclic permutation of the 3 columns of a matrix (modeling rods, as we have already mentioned); for example:

 
     Now, using the matrix Y(u, n), we calculate the move number n at which this matrix appeared:



- this is a vector of powers of two for the following sum:


which gives us the desired number of the corresponding move; for example:


     The mechanism of this procedure is as follows: The largest disk u, displaced from its zero position, gives the lower bound for n; this is 2^u-1 -exactly the number of moves needed to transfer the tower (u-1) and move the disk u. Then, the "subtower" must be returned to its zero position (by cyclically shifting the entire matrix), after which the next largest displaced disk is identified, and so on.
     This is also a "return" recursion, but it recurses over the number of disks rather than moves; the recursion step is not necessarily one (it is variable), which greatly reduces computation time.

Parity and Number Systems

        These remaining topics are not directly related. Therefore, I grouped them under one heading.
        Note. When applying our formulas and programs, boundary conditions must be monitored. For example, the state of the tower at the n-th move can be calculated for any number of disks u and any n. However, if n>3*(2^u - 1), the disks will begin (correctly!) cyclic movements, endlessly transferring the tower between the 3 rods. For the reverse procedure, towers must be taken where n less or equal (2^u - 1). Additionally, it should be noted that u (the number of disks) can be infinitely large, but the first (2^u - 1) moves of a tower with u disks will coincide with the behavior of a tower with (u+1) disks.
     This is the parity function of n, calibrated to give the degree of parity of n as output (i.e., the power of two in the decomposition of n into the product of powers of prime factors).


     Let's focus on its graphs (the first one being a line, the second represented as dots):




     Let's add 1 to it. Now, all odd numbers give the function a value of 1. As is well known, odd numbers constitute "half" of all numbers. Numbers that are divisible by 2 exactly once will constitute "a quarter," and so on, as shown by the graphs (quotation marks " " indicate that our statements are "asymptotically" valid for all finite sets m:={1, ..., u}).
     However, observing the tower's behavior, we notice that the numbers (equal to the diameters of its disks) behave in exactly the same way: 1 acts on every odd move, 2 on every singly even move, 3 on every 8-th move, and so on. Moreover, each of these numbers has its own initial phase of movement: 1 will be the first, and any arbitrary disk will begin its movement from the 2^u-1-th move. From this, we conclude that ε(u, n)=c(n)+1 for sufficiently large u, where ε(u, n) is defined by the formula:


- where equality means the characteristic function of the corresponding set.
     That is, this formula is also a definition of the parity function (calibrated so that ε(u, n)=c(n)+1). It shows which disk will move on the n-th move. For example: ε(7,34)=c(34)+1=2.
     And since we know that all even disks make sequential cyclic moves, and odd ones - "skip one column", and that a larger disk cannot cover a smaller one, now we have another non-recursive and non-iterative algorithm for calculating the state of the tower.
     You can verify the correctness of these calculations by taking the difference of the tower matrices at adjacent moves:


This means that on the 34-th move, the disk numbered 2 moved from the second rod to the zeroth, as we have just calculated. If the disk is stationary, its position is reset to zero.
     Now let's turn to different ways of representing the tower as a mathematical object. Here is a program that returns a linear list of column numbers of the u-tower on the n-th move:


For example, let"s calculate the matrix of the 7-tower at moves 33 and 34:

 




     The parity function is very interesting. Being quasiperiodic, for any uu, starting from the moment 2^u-1, it is locally one-to-one over the period 2^u. This allows us to consider the Tower of Hanoi as a numeral system. Perhaps such a numeral system may prove to be practically useful.

Conclusion

     In conclusion, we will show several illustrations of the described processes. Looking at the graphs, one can observe the fractal nature of the tower: each subsequent number advances with a frequency that is twice as low as the previous one. The following ornaments were obtained using certain transformations of the tower (I no longer remember which ones):

 
     This is not surprising, since fractals have a fundamentally recursive nature. Perhaps the parity function can somehow be connected with the Haar wavelet.
     Here are some more interesting illustrations. I thought that the 3 rods of the tower could be arranged in a circle, like arguments in a complex number. In this case, we represent the disks as points moving along such a circle at fixed levels, connected by straight line segments:

nunchaku.avi

- this is the same 7-tower. It turns out to be something like nunchaku with seven segments, spun by an invisible master standing at the center of the circle.
     What if we make the parity function continuous (in this case, using parabolic interpolation), turning the nunchaku into an elegant exotic whip:

Zmyej.avi

     I think this opens up many possibilities, including practical applications. But this lies beyond the scope of our study.
     It seems that all finite recursive problems can be solved without recursion, but infinity without it is impossible. It is this very infinity that brings us close to a contradiction. Recursion (induction) is the first (still primitive) mathematical model of self-reflection and self-determination of an object (according to Hegel), which creates "being for another" out of "being in itself and for itself." But it all starts simply: an infinite set is equivalent in size to its own subset.
     Well, at this stage, all that remains for me is to humbly contemplate the Tower of Hanoi and reflect, reflect...

Osyol.avi

References

[1] Haskell B. Curry, McGraw-Hill Book Company, INC.
Foundations of Manthematical logic, (1969).

[2] By.G. Polya, Ptinceton University Press,
Patterns of plausible reasoning, (1954)