3.1.6 - primitive_recursion

3.1.6

Introduction to the Primitive Recursion

Introduction

Throughout this Chapter I've been slowly developing the concept of a function and shown some of the things we can do with them. In this article I add a new component to our function defining arsenal: The Primitive Recursion. This is the most fundamental and basic kind of recursion, and it's the foundation for all of the more advanced recursive functions we'll explore in chapters to come. What is the Primitive Recursion? Let's find out

The Primitive Recursion

The concept of Primitive Recursion, or recursion in general, began with 19th century mathematics, as mathematicians were trying to formalize mathematics to protect it against paradoxes and ambiguities. Recursion can be used to define mathematics in a mechanistic and efficient way.

At the heart of recursion is the idea of something which makes reference to itself. The classic example is an image which contains a perfect copy of itself within itself:

In order for this to work the copy must itself contain a copy, which must contain a copy, ad infinitum. This is essentially an example of the primitive recursion. We can say an image which makes reference to itself is a Recursive Image. By the same token, a Recursive function is one that makes reference to itself in its own definition. For example:

f(x) := f(f(x))

By this definition:

f(x) = f(f(x)) = f(f(f(x))) = f(f(f(f(x)))) = f(f(f(f(f(x))))) = ...

This would continue ad infinitum. Note that if we wanted to know the value of say f(3), we'd have to find the value of f(f(3)), then f(f(f(3))), then f(f(f(f(3)))), ... but since in each instance determining f(3) relies on determining f(3), we never actually determine f(3). While in a recursive image this kind of infinite recursion is aesthetically pleasing, it is useless for our purposes of defining recursive functions. We do want the process to terminate after a finite number of steps and produce a definite number!

It will not be possible for us to define a recursive function using a single explicit formula. Instead we must create a piecewise function composed of two Rules. One of the rules is known as the Base Case. Every recursive function we'll ever define will always have a Base Case Rule. The Base Case simply gives us an immediate answer for a specific (usually smallest possible) input. The second rule is the Recursive Case. This rule simply defines the output in terms of the original function. If you recall our work on piecewise functions, the following should be fairly clear:

Let r(n) be defined when n is a Counting number as follows:

when n=1, r(1) = 1

otherwise r(n) = r(n-1) + 1

Believe or not, we've just defined a very simple recursive function. Evaluating it will show you how recursion comes into play here.

Say you want to evaluate r(1).

You simply observe the rule that says when n=1, r(1) = 1

So r(1) = 1.

To evaluate r(2), you observe that the first part (the base case) does not apply. Thus we use the second formula that says r(n) = r(n-1)+1

So r(2) = r(2-1)+1 = r(1) + 1

Since r(1)=1 we conclude that r(1)+1 = 1+1 = 2 and therefore r(2) = 2

To evaluate r(3), you observe the base case does not apply, therefore:

r(3) = r(3-1)+1 = r(2) + 1 = r(2-1) + 1 + 1 = r(1) + 1 + 1 = 1 + 1 + 1 = 3

Thus r(3) = 3

It should be obvious from a moments reflection that r(n) = n for all n. r is in fact the Return function, one of the simplest functions imaginable. It simply returns the input as output. We have defined it recursively however. The definition r(n) = n defines exactly the same function. We say that r(n) = n is the Explicit form of the recursive function r. Not all recursive functions can be reduced to an Explicit form and that should alert you that recursive functions are broader than the elementary functions.

Note that we have to be careful how we set up any recursion. Even if we include a Base Case we can still inadvertantly set up an infinite recursion. For example:

Let s(n) be defined when n=Counting Number,

when n=1, s(1) = 2

otherwise s(n) = s(s(n-1))

When we go to evalute s(1) = 2 we have no difficulty. But see what happens when we try to compute

s(2) using our recursive definition:

s(2) = s(s(2-1)) = s(s(1)) = s(2) = s(s(2-1)) = s(s(1)) = s(2) = s(s(2-1)) = s(s(1)) = s(2) = ...

The result is that we keep looping indefinitely between the 3 expressions s(2), s(s(2-1)), and s(s(1)). This never terminates, so we say that s(2) is undefined. Note that when an infinite cycle occurs it's because a result relies on itself. For example, we see that to evaluate s(2), we must evaluate s(2). In our first example, to evaluate f(3) we had to evaluate f(3). So to ensure that our functions terminate we must make sure that evaluations don't depend on themselves.

Now that we have some idea of how a basic recursive function works, what is The Primitive Recursion? Here is my definition:

Def. The Primitive Recursion

The Primitive Recursion base b of a function of Real Numbers to Real Numbers, f(x), with real b, is a recursive function R(n) where n is a whole number defined as follows:

when n=0 , R(0) = b

otherwise R(n) = f(R(n-1))

The Primitive Recursion goes by many names and forms: it is synonymous with the notion of a functional power. In fact R(i) is equal to the ith functional power of f at b. From time to time we may want to use slightly altered definitions of the primitive recursion. For example, we can define the general primitive recursion of f as:

R(b,n) where b is real and n is whole:

when n=0, R(b,0) = b

otherwise R(b,n) = f(R(b,n-1))

This has the advantage of letting us alter the base case at will. Regardless of the fine points of the definition, as we progress we will notice the pattern of this primitive recursion again and again and again. It in fact will form an important foundation for our theory of recursive functions, for all higher levels of recursion that we will use are built from the building block of the primitive recursion.

As we have defined it, the primitive recursion is really just re-iterated composition of a function with itself. We can derive this directly from the definition itself. For example:

R(1) = f(R(1-1)) = f(R(0)) = f(b)

R(2) = f(R(2-1)) = f(R(1)) = f(f(b))

R(3) = f(R(2)) = f(f(f(b)))

...

In general

R(n) = f(f(f(f( ... f(f(f(b))) ... )))) w/n f's when n>0

It is in this form that R(n) would be known as the functional power. We will often find the functional power notation useful to make this idea more compact. We can say that:

f ⁿ(x) = f(f(f( ... f(f(f(x))) ... ))) w/n f's where n is a positive integer

(Alternatively we can use the notation f^n(x) when convenient)

The functional power notation can also be extended to all the integers. Firstly we observe that:

f ^a(f ^b(x)) = f ^a+b(x) : a,b = Z⁺

is a natural consequence of our definition over the positive integers, Z+. We next extend this law to all the integers. This leads to an interesting consequence for f⁰(x):

By definition:

f ⁰( f ¹(x)) = f ⁰⁺¹(x) = f ¹(x)

Now we observe that f⁰ returns the input f¹(x) as output. Therefore f⁰(x) = x. We can next extend to the negative functional powers:

f ^-1(f ¹(x)) = f⁰(x) = x

So f^-1 is a function which takes the output f¹(x) and returns the input x. It is the anti-function of f. f^-1 is commonly called the Inverse function of f. To extend further we simply let f ^-n(x) be the nth functional power of the Inverse of f. Thus we can extend the concept of functional power (and the primitive recursion) to all integers. In practice however, developing an inverse of a function is much more difficult than a composition. Furthermore we will rarely have use for working backwards like this.

In any case we can now define the primitive recursion of f as:

R(x,n) = f ⁿ(x)

The application of the Primitive Recursion to any real-to-real function, will produce a new function. This operation however is a great deal more powerful and general than any method we have previously used to generate functions. The reason for our interest in the Primitive Recursion is because, generally speaking, the primitive recursion quickly produces very large values, if the initial function is already a relatively fast growing function.

Not all functions will grow rapidly under primitive recursion however. Take for example this simple piece-wise function:

Let f(n) be defined when n=Z⁺ as follows:

when n is even , f(n) = 1

when n is odd , f(n) = 2

Some examples of values for this function are:

...

f(-3) = 2

f(-2) = 1

f(-1) = 2

f(0) = 1

f(1) = 2

f(2) = 1

f(3) = 2

...

All this function does is alternate between the values 1 and 2. Let's see what happens if we apply a primitive recursion base 100 to f:

R(0) = 100

R(1) = f(R(0)) = f(100) = 1

R(2) = f(R(1)) = f(1) = 2

R(3) = f(R(2)) = f(2) = 1

R(4) = f(R(3)) = f(1) = 2

etc.

The primitive recursion just get's locked into the same loop. It will never produce a value any larger than the one we initially put in, so it's useless for generating large numbers.

If we want the Primitive Recursion of a function to be a rapidly growing recursive function, then the function f, has to meet a few additional requirements:

1. f should be a Strictly increasing function

2. f should be a Strictly magnifying function

A strictly increasing function is one in which if a<b then f(a) < f(b) for all a and b. What this means in laymen's terms is that as you increase the input the output only increases, it never stops or decreases.

This sequence can be defined by f(n) = 2n for n is a positive integer. Note that this sequence is strictly increasing since f(a) = 2a < 2b = f(b) assuming a<b. It is strictly magnifying since a < 2a = f(a) for all a=Z⁺. It is also minimally successive since a+1 =< a+a = 2a = f(a) for all a=Z⁺. In addition to these properties, this function has one additional property which is key to its ability to create rapid growth under primitive recursion. Notice that the difference f(n)-n is always increasing:

f(1)-1 = 2-1 = 1

f(2)-2 = 4-2 = 2

f(3)-3 = 6-3 = 3

f(4)-4 = 8-4 = 4

...

f(n)-n = n

In the earlier examples of functions under primitive recursion we find that this difference was a constant:

x+0.01 - x = 0.01

x+1 - x = 1

Functions whose difference between output and input is always increasing I'll call Strictly gaining functions. In Calculus a Strictly gaining function f(x) would be one whose second derivative f''(x) was always greater than or equal to zero for all x:

f''(x)>=0 : ALL x

For our purposes it will be simpler to say that a Strictly gaining function is a function such that:

f(a)-a < f(b)-b Provided a<b

A question we will explore in the next article is whether Strictly gaining is a sufficient condition for the primitive recursion to grow fast than the original function.

For now let's just test out our doubling function, and see what happens when we apply the primitive recursion base 1:

R(0) = 1 by definition

R(1) = S(R(1-1)) = S(R(0)) = S(1) = 2*1 = 2 [via the second rule]

R(2) = S(R(2-1)) = S(R(1)) = S(2) = 2*2 = 4

R(3) = S(R(2)) = S(4) = 2*4 = 8

R(4) = S(R(3)) = S(8) = 2*8 = 16

R(5) = S(R(4)) = S(16) = 2*16 = 32

...

We can see that R is both a strictly increasing and strictly magnifying sequence. Furthermore we can say that R is a faster growing sequence than f. The Table below compares the two functions:

R(n) is in fact growing exponentially. We can even give R(n) an explicit formula:

R(n) = 2ⁿ

Not bad by ordinary standards, but R(n) is still technically an elementary function, since we can describe it with an elementary formula. But we aren't done with Primitive Recursion yet. Keep in mind that we can apply primitive recursion to any function whose output can be used as valid input. And any Primitive Recursion is itself a function. So why not apply Primitive Recursion to R(n) to create a second level of primitive recursion!

So we now define the Primitive Recursion base 1 of R(n):

Let R₂(n) be the primitive recursion of R. So we would have:

R₂(0) = 1 [by definition]

R₂(1) = R(R₂(0)) = R(1) = 2^1 = 2

R₂(2) = R(R₂(1)) = R(2) = 2^2 = 4

(So far nothing new...)

R₂(3) = R(R₂(2)) = R(4) = 2^4 = 16

R₂(4) = R(16) = 2^16 = 65,536

R₂(5) = R(65,536) = 2^65,536 =

2 003 529 930 406 846 464 979 072 351 560 255 750 447 825 475 569 751 419 265 016 973 710 894 059 556 311 453 089 506 130 880 933 348 101 038 234 342 907 263 181 822 949 382 118 812 668 869 506 364 761 547 029 165 041 871 916 351 587 966 347 219 442 930 927 982 084 309 104 855 990 570 159 318 959 639 524 863 372 367 203 002 916 969 592 156 108 764 948 889 254 090 805 911 457 037 675 208 500 206 671 563 702 366 126 359 747 144 807 111 774 815 880 914 135 742 720 967 190 151 836 282 560 618 091 458 852 699 826 141 425 030 123 391 108 273 603 843 767 876 449 043 205 960 379 124 490 905 707 560 314 035 076 162 562 476 031 863 793 126 484 703 743 782 954 975 613 770 981 604 614 413 308 692 118 102 485 959 152 380 195 331 030 292 162 800 160 568 670 105 651 646 750 568 038 741 529 463 842 244 845 292 537 361 442 533 614 373 729 088 303 794 601 274 724 958 414 864 915 930 647 252 015 155 693 922 628 180 691 650 796 381 064 132 275 307 267 143 998 158 508 811 292 628 901 134 237 782 705 567 421 080 070 065 283 963 322 155 077 831 214 288 551 675 554 073 345 107 213 112 427 399 562 982 719 769 150 054 883 905 223 804 357 045 848 197 956 393 157 853 510 018 992 000 024 141 963 706 813 559 840 464 039 472 194 016 069 517 690 156 119 726 982 337 890 017 641 517 190 051 133 466 306 898 140 219 383 481 435 426 387 306 539 552 969 691 388 024 158 161 859 561 100 640 362 119 796 101 859 534 802 787 167 200 122 604 642 492 385 111 393 400 464 351 623 867 567 078 745 259 464 670 903 886 547 743 483 217 897 012 764 455 529 409 092 021 959 585 751 622 973 333 576 159 552 394 885 297 579 954 028 471 943 529 913 543 763 705 986 928 913 757 153 740 001 986 394 332 464 890 052 543 106 629 669 165 243 419 174 691 389 632 476 560 289 415 199 775 477 703 138 064 781 342 309 596 190 960 654 591 300 890 188 887 588 084 733 625 956 065 444 888 501 447 335 706 058 817 090 162 108 499 714 529 568 344 061 979 690 565 469 813 631 162 053 579 369 791 403 236 328 496 233 046 421 066 136 200 220 175 787 851 857 409 162 050 489 711 781 820 400 187 282 939 943 446 186 224 328 009 837 323 764 931 814 789 848 119 452 713 007 440 220 765 680 910 376 203 999 203 492 023 906 626 264 491 909 167 985 461 515 778 839 060 397 720 759 279 378 852 241 294 301 017 458 086 862 263 369 284 725 851 403 039 615 558 564 330 385 450 688 652 213 114 813 638 408 384 778 263 790 459 607 186 876 728 509 763 471 271 988 890 680 478 243 230 394 718 650 525 660 978 150 729 861 141 430 305 816 927 924 971 409 161 059 417 185 352 275 887 504 477 592 218 301 158 780 701 975 535 722 241 400 019 548 102 005 661 773 589 781 499 532 325 208 589 753 463 547 007 786 690 406 429 016 763 808 161 740 550 405 117 670 093 673 202 804 549 339 027 992 491 867 306 539 931 640 720 492 238 474 815 280 619 166 900 933 805 732 120 816 350 707 634 351 669 869 625 020 969 023 162 859 350 071 874 190 579 161 241 536 897 514 808 261 904 847 946 571 736 601 005 892 476 655 445 840 838 334 790 544 144 817 684 255 327 207 315 586 349 347 605 137 419 779 525 190 365 032 198 020 108 764 738 368 682 531 025 183 377 533 908 861 426 184 800 374 008 082 238 104 076 468 878 471 647 552 945 326 947 661 700 424 461 063 311 238 021 134 588 694 532 200 116 564 076 327 023 074 292 426 051 582 811 070 387 018 345 324 567 635 625 951 430 032 037 432 740 780 879 056 283 663 406 965 030 844 225 855 967 039 271 869 461 158 513 793 386 475 699 748 568 670 079 823 960 604 393 478 850 861 649 260 304 945 061 743 412 365 828 352 144 806 726 676 841 807 083 754 862 211 408 236 579 802 961 200 027 441 324 438 432 402 331 257 403 545 019 352 428 776 430 880 232 850 855 886 089 962 774 458 164 680 857 875 115 807 014 743 763 867 976 955 049 991 643 998 284 357 290 415 378 143 438 847 303 484 261 903 388 841 494 031 366 139 854 257 635 577 105 335 580 206 622 185 577 060 082 551 288 893 332 226 436 281 984 838 613 239 570 676 191 409 638 533 832 374 343 758 830 859 233 722 284 644 287 996 245 605 476 932 428 998 432 652 677 378 373 173 288 063 210 753 211 238 680 604 674 708 428 051 166 488 709 084 770 291 208 161 104 912 555 598 322 366 244 868 556 651 402 684 641 209 694 982 590 565 519 216 188 104 341 226 838 996 283 071 654 868 525 536 914 850 299 539 675 503 954 938 371 853 405 900 096 187 489 473 992 880 432 496 373 165 753 803 673 586 710 175 783 994 818 471 798 498 246 948 060 532 081 996 066 183 434 012 476 096 639 519 778 021 441 199 752 546 704 080 608 499 344 178 256 285 092 726 523 709 898 651 539 462 193 004 607 364 507 926 212 975 917 698 293 892 367 015 170 992 091 531 567 814 439 791 248 475 706 237 804 600 009 918 293 321 306 880 570 046 591 458 387 208 088 016 887 445 835 557 926 258 465 124 763 087 148 566 313 528 934 166 117 490 617 526 671 492 672 176 128 330 845 273 936 469 244 582 892 571 388 877 839 056 300 482 483 799 839 692 029 222 215 486 145 902 373 478 222 682 521 639 957 440 801 727 144 146 179 559 226 175 083 889 020 074 169 926 238 300 282 286 249 284 182 671 243 405 751 424 188 569 994 272 331 606 998 712 986 882 771 820 617 214 453 142 574 944 015 066 139 463 169 197 629 181 506 579 745 526 236 191 224 848 063 890 033 669 074 365 989 226 349 564 114 665 503 062 965 960 199 720 636 202 603 521 917 776 740 668 777 463 549 375 318 899 587 866 282 125 469 797 102 065 747 232 721 372 918 144 666 659 421 872 003 474 508 942 830 911 535 189 271 114 287 108 376 159 222 380 276 605 327 823 351 661 555 149 369 375 778 466 670 145 717 971 901 227 117 812 780 450 240 026 384 758 788 339 396 817 962 950 690 798 817 121 690 686 929 538 248 529 830 023 476 068 454 114 178 139 110 648 560 236 549 754 227 497 231 007 615 131 870 024 053 910 510 913 817 843 721 791 422 528 587 432 098 524 957 878 034 683 703 337 818 421 444 017 138 688 124 249 984 418 618 129 271 198 533 315 382 567 321 870 421 530 631 197 748 535 214 670 955 334 626 336 610 864 667 332 292 409 879 849 256 691 109 516 143 618 601 548 909 740 241 913 509 623 043 612 196 128 165 950 518 666 022 030 715 613 684 732 364 660 868 905 014 263 913 906 515 063 908 199 378 852 318 365 059 897 299 125 404 479 443 425 166 774 299 659 811 849 233 151 555 272 883 274 028 352 688 442 408 752 811 283 289 980 625 912 673 699 546 247 341 543 333 500 147 231 430 612 750 390 307 397 135 252 069 338 173 843 322 950 701 049 061 867 539 433 130 784 798 015 655 130 384 758 155 685 236 218 010 419 650 255 596 181 934 986 315 913 233 036 096 461 905 990 236 112 681 196 023 441 843 363 334 594 927 631 946 101 716 652 913 823 717 182 394 299 216 272 538 461 776 065 694 542 297 877 071 383 198 817 036 964 588 689 811 863 210 976 900 355 735 884 624 464 835 706 291 453 052 757 101 278 872 027 965 364 479 724 025 405 448 132 748 391 794 128 826 423 835 171 949 197 209 797 145 936 887 537 198 729 130 831 738 033 911 016 128 547 415 377 377 715 951 728 084 111 627 597 186 384 924 222 802 373 441 925 469 991 983 672 192 131 287 035 585 307 966 942 713 416 391 033 882 754 318 613 643 490 100 943 197 409 047 331 014 476 299 861 725 424 423 355 612 237 435 715 825 933 382 804 986 243 892 498 222 780 715 951 762 757 847 109 475 119 033 482 241 412 025 182 688 713 728 193 104 253 478 196 128 440 176 479 531 505 057 110 722 974 314 569 915 223 451 643 121 848 657 575 786 528 197 564 843 508 958 384 722 923 534 559 464 521 215 831 657 751 471 298 708 225 909 292 655 638 836 651 120 681 943 836 904 116 252 668 710 044 560 243 704 200 663 709 001 941 185 557 160 472 044 643 696 932 850 060 046 928 140 507 119 069 261 393 993 902 735 534 545 567 470 314 903 886 022 024 639 948 260 501 762 431 969 305 640 666 366 626 090 207 048 887 438 898 907 498 152 865 444 381 862 917 382 901 051 820 869 936 382 661 868 303 915 273 264 581 286 782 806 601 337 500 096 593 364 625 146 091 723 180 312 930 347 877 421 234 679 118 454 791 311 109 897 794 648 216 922 505 629 399 956 793 483 801 699 157 439 700 537 542 134 485 874 586 856 047 286 751 065 423 341 893 839 099 110 586 465 595 113 646 061 055 156 838 541 217 459 801 807 133 163 612 573 079 611 168 343 863 767 667 307 354 583 494 789 788 316 330 129 240 800 836 356 825 939 157 113 130 978 030 516 441 716 682 518 346 573 675 934 198 084 958 947 940 983 292 500 086 389 778 563 494 693 212 473 426 103 062 713 745 077 286 156 922 596 628 573 857 905 533 240 641 849 018 451 328 284 632 709 269 753 830 867 308 409 142 247 659 474 439 973 348 130 810 986 399 417 379 789 657 010 687 026 734 161 967 196 591 599 588 537 834 822 988 270 125 605 842 365 589 539 690 306 474 965 584 147 981 310 997 157 542 043 256 395 776 070 485 100 881 578 291 408 250 777 738 559 790 129 129 407 309 462 785 944 505 859 412 273 194 812 753 225 152 324 801 503 466 519 048 228 961 406 646 890 305 102 510 916 237 770 448 486 230 229 488 966 711 380 555 607 956 620 732 449 373 374 027 836 767 300 203 011 615 227 008 921 843 515 652 121 379 215 748 206 859 356 920 790 214 502 277 133 099 987 729 459 596 952 817 044 582 181 956 080 965 811 702 798 062 669 891 205 061 560 742 325 686 842 271 306 295 009 864 421 853 470 810 407 128 917 646 906 550 836 129 916 694 778 023 822 502 789 667 843 489 199 409 657 361 704 586 786 242 554 006 942 516 693 979 292 624 714 524 945 408 858 422 726 153 755 260 071 904 336 329 196 375 777 502 176 005 195 800 693 847 635 789 586 878 489 536 872 122 898 557 806 826 518 192 703 632 099 480 155 874 455 575 175 312 736 471 421 295 536 494 084 385 586 615 208 012 115 079 075 068 553 344 489 258 693 283 859 653 013 272 046 970 694 571 546 959 353 658 571 788 894 862 333 292 465 202 735 853 188 533 370 948 455 403 336 565 356 988 172 582 528 918 056 635 488 363 743 793 348 411 845 580 168 331 827 676 834 646 291 995 605 513 470 039 147 876 808 640 322 629 616 641 560 667 508 153 710 646 723 108 461 964 247 537 490 553 744 805 318 226 002 710 216 400 980 584 497 526 023 035 640 038 083 472 053 149 941 172 965 736 785 066 421 400 842 696 497 103 241 919 182 121 213 206 939 769 143 923 368 374 709 228 267 738 708 132 236 680 086 924 703 491 586 840 991 153 098 315 412 063 566 123 187 504 305 467 536 983 230 827 966 457 417 620 806 593 177 265 685 841 681 837 966 106 144 963 432 544 111 706 941 700 222 657 817 358 351 259 821 080 769 101 961 052 229 263 879 745 049 019 254 311 900 620 561 906 577 452 416 191 913 187 533 984 049 343 976 823 310 298 465 893 318 373 015 809 592 522 829 206 820 862 230 332 585 280 119 266 496 314 441 316 442 773 003 237 792 274 712 330 696 417 149 945 532 261 035 475 145 631 290 668 854 345 426 869 788 447 742 981 777 493 710 117 614 651 624 183 616 680 254 815 296 335 308 490 849 943 006 763 654 806 102 940 094 693 750 609 845 588 558 043 970 485 914 449 584 445 079 978 497 045 583 550 685 408 745 163 316 464 118 083 123 079 704 389 849 190 506 587 586 425 810 738 422 420 591 191 941 674 182 490 452 700 288 263 983 057 950 057 341 711 487 031 187 142 834 184 499 153 456 702 915 280 104 485 145 176 055 306 971 441 761 368 582 384 102 787 659 324 662 689 978 418 319 620 312 262 421 177 391 477 208 004 883 578 333 569 204 533 935 953 254 564 897 028 558 589 735 505 751 235 129 536 540 502 842 081 022 785 248 776 603 574 246 366 673 148 680 279 486 052 445 782 673 626 230 852 978 265 057 114 624 846 595 914 210 278 122 788 941 448 163 994 973 881 884 622 768 244 851 622 051 817 076 722 169 863 265 701 654 316 919 742 651 230 041 757 329 904 473 537 672 536 845 792 754 365 412 826 553 581 858 046 840 069 367 718 605 020 070 547 247 548 400 805 530 424 951 854 495 267 247 261 347 318 174 742 180 078 574 693 465 447 136 036 975 884 118 029 408 039 616 746 946 288 540 679 172 138 601 225 419 503 819 704 538 417 268 006 398 820 656 328 792 839 582 708 510 919 958 839 448 297 775 647 152 026 132 871 089 526 163 417 707 151 642 899 487 953 564 854 553 553 148 754 978 134 009 964 854 498 635 824 847 690 590 033 116 961 303 766 127 923 464 323 129 706 628 411 307 427 046 202 032 013 368 350 385 425 360 313 636 763 575 212 604 707 425 311 209 233 402 837 482 949 453 104 727 418 969 287 275 572 027 615 272 268 283 376 741 393 425 652 653 283 068 469 997 597 097 750 005 560 889 932 685 025 049 212 884 068 274 139 881 631 540 456 490 350 775 871 680 074 055 685 724 021 758 685 439 053 228 133 770 707 415 830 756 269 628 316 955 687 424 060 527 726 485 853 050 611 356 384 851 965 918 968 649 596 335 568 216 975 437 621 430 778 665 934 730 450 164 822 432 964 891 270 709 898 076 676 625 671 517 269 062 058 815 549 666 382 573 829 274 182 082 278 960 684 488 222 983 394 816 670 984 039 024 283 514 306 813 767 253 460 126 007 269 262 969 468 672 750 794 346 190 439 996 618 979 611 928 750 519 442 356 402 644 303 271 737 341 591 281 496 056 168 353 988 188 569 484 045 342 311 424 613 559 925 272 330 064 881 627 466 723 523 751 234 311 893 442 118 885 085 079 358 163 848 994 487 544 756 331 689 213 869 675 574 302 737 953 785 262 542 329 024 881 047 181 939 037 220 666 894 702 204 258 836 895 840 939 998 453 560 948 869 946 833 852 579 675 161 882 159 410 981 624 918 741 813 364 726 965 123 980 677 561 947 912 557 957 446 471 427 868 624 053 750 576 104 204 267 149 366 084 980 238 274 680 575 982 591 331 006 919 941 904 651 906 531 171 908 926 077 949 119 217 946 407 355 129 633 864 523 035 673 345 588 033 313 197 080 365 457 184 791 550 432 654 899 559 705 862 888 286 866 606 618 021 882 248 602 144 999 973 122 164 138 170 653 480 175 510 438 406 624 412 822 803 616 648 904 257 377 640 956 326 482 825 258 407 669 045 608 439 490 325 290 526 337 532 316 509 087 681 336 614 242 398 309 530 806 549 661 879 381 949 120 033 919 489 494 065 132 398 816 642 080 088 395 554 942 237 096 734 840 072 642 705 701 165 089 075 196 155 370 186 264 797 456 381 187 856 175 457 113 400 473 810 762 763 014 953 309 735 174 180 655 479 112 660 938 034 311 378 532 532 883 533 352 024 934 365 979 129 341 284 854 970 946 826 329 075 830 193 072 665 337 782 559 314 331 110 963 848 053 940 859 283 988 907 796 210 479 847 919 686 876 539 987 477 095 912 788 727 475 874 439 806 779 824 968 278 272 200 926 449 944 559 380 414 608 770 641 941 810 440 758 269 805 688 038 949 654 616 587 983 904 660 587 645 341 810 289 907 194 293 021 774 519 976 104 495 043 196 841 503 455 514 044 820 928 933 378 657 363 052 830 619 990 077 748 726 922 998 608 279 053 171 691 876 578 860 908 941 817 057 993 404 890 218 441 559 791 092 676 862 796 597 583 952 483 926 734 883 634 745 651 687 016 166 240 642 424 241 228 961 118 010 615 682 342 539 392 180 052 483 454 723 779 219 911 228 595 914 191 877 491 793 823 340 010 078 128 326 506 710 281 781 396 029 120 914 720 100 947 878 752 551 263 372 884 222 353 869 490 067 927 664 511 634 758 101 193 875 319 657 242 121 476 038 284 774 774 571 704 578 610 417 385 747 911 301 908 583 877 890 152 334 343 013 005 282 797 038 580 359 815 182 929 600 305 682 612 091 950 943 737 325 454 171 056 383 887 047 528 950 563 961 029 843 641 360 935 641 632 589 408 137 981 511 693 338 619 797 339 821 670 761 004 607 980 096 016 024 823 096 943 043 806 956 620 123 213 650 140 549 586 250 615 282 588 033 022 908 385 812 478 469 315 720 323 233 601 899 469 437 647 726 721 879 376 826 431 828 382 603 564 520 699 468 630 216 048 874 528 424 363 593 558 622 333 506 235 945 002 890 558 581 611 275 341 783 750 455 936 126 130 852 640 828 051 213 873 177 490 200 249 552 738 734 585 956 405 160 830 583 053 770 732 533 971 552 620 444 705 429 573 538 361 113 677 523 169 972 740 292 941 674 204 423 248 113 875 075 631 319 078 272 188 864 053 374 694 213 842 169 928 862 940 479 635 305 150 560 788 126 366 206 497 231 257 579 019 598 873 041 195 626 227 343 728 900 516 561 111 094 111 745 277 965 482 790 471 250 581 999 077 498 063 821 559 376 885 546 498 822 938 985 408 291 325 129 076 478 386 322 494 781 016 753 491 693 489 288 104 203 015 610 283 386 143 827 378 160 946 341 335 383 578 340 765 314 321 417 150 655 877 547 820 252 454 780 657 301 342 277 470 616 744 241 968 952 613 164 274 104 695 474 621 483 756 288 299 771 804 186 785 084 546 965 619 150 908 695 874 251 184 435 837 306 590 951 460 980 451 247 409 411 373 899 927 822 492 983 367 796 011 015 387 096 129 749 705 566 301 637 307 202 750 734 759 922 943 792 393 824 427 421 186 158 236 161 317 886 392 553 095 117 188 421 298 508 307 238 259 729 144 142 251 579 403 883 011 359 083 331 651 858 234 967 221 259 621 812 507 058 113 759 495 525 022 747 274 674 369 887 131 926 670 769 299 199 084 467 161 228 738 858 457 584 622 726 573 330 753 735 572 823 951 616 964 175 198 675 012 681 745 429 323 738 294 143 824 814 377 139 861 906 716 657 572 945 807 804 820 559 511 881 687 188 075 212 971 832 636 442 155 336 787 751 274 766 940 790 117 057 509 819 575 084 563 565 217 389 544 179 875 074 523 854 455 200 133 572 033 332 379 895 074 393 905 312 918 212 255 259 833 790 909 463 630 202 185 353 848 854 825 062 897 715 616 963 860 712 382 771 725 621 313 460 549 401 770 413 581 731 931 763 370 136 332 252 819 127 547 191 443 450 920 711 848 838 366 818 174 263 342 949 611 870 091 503 049 165 339 464 763 717 766 439 120 798 347 494 627 397 822 171 502 090 670 190 302 469 762 151 278 521 956 142 070 806 461 631 373 236 517 853 976 292 092 025 500 288 962 012 970 141 379 640 038 055 734 949 269 073 535 145 961 208 674 796 547 733 692 958 773 628 635 660 143 767 964 038 430 796 864 138 563 447 801 328 261 284 589 184 898 528 048 048 844 180 821 639 423 974 014 362 903 481 665 458 114 454 366 460 032 490 618 763 039 502 356 402 044 530 748 210 241 366 895 196 644 221 339 200 757 479 128 683 805 175 150 634 662 569 391 937 740 283 512 075 666 260 829 890 491 877 287 833 852 178 522 792 045 771 846 965 855 278 790 447 562 192 663 992 008 409 302 075 673 925 363 735 628 390 829 817 577 902 153 202 106 409 617 373 283 598 494 066 652 141 198 183 810 884 515 459 772 895 164 572 131 897 797 907 491 941 013 148 368 544 639 616 904 607 030 107 596 818 933 741 217 575 988 165 127 000 761 262 789 169 510 406 315 857 637 534 787 420 070 222 051 070 891 257 612 361 658 026 806 815 858 499 852 631 465 878 086 616 800 733 264 676 830 206 391 697 203 064 894 405 628 195 406 190 685 242 003 053 463 156 621 891 327 309 069 687 353 181 641 094 514 288 036 605 995 220 248 248 886 711 554 429 104 721 929 134 248 346 438 705 368 508 648 749 099 178 812 670 565 665 387 191 049 721 820 042 371 492 740 164 460 943 459 845 392 536 706 132 210 616 533 085 662 021 188 968 234 005 752 675 486 101 476 993 688 738 209 584 552 211 571 923 479 686 888 160 853 631 615 862 880 150 395 949 418 529 489 227 074 410 828 207 169 303 387 818 084 936 204 018 255 222 271 010 985 653 444 817 207 470 756 019 245 915 599 431 072 949 578 197 878 590 578 940 052 540 122 867 517 142 511 184 356 437 184 053 563 024 181 225 473 266 093 302 710 397 968 091 064 939 272 722 683 035 410 467 632 591 355 279 683 837 705 019 855 234 621 222 858 410 557 119 921 731 717 969 804 339 317 707 750 755 627 056 047 831 779 844 447 637 560 254 637 033 369 247 114 220 815 519 973 691 371 975 163 241 302 748 712 199 863 404 548 248 524 570 118 553 342 675 264 715 978 310 731 245 663 429 805 221 455 494 156 252 724 028 915 333 354 349 341 217 862 037 007 260 315 279 870 771 872 491 234 494 477 147 909 520 734 761 385 425 485 311 552 773 301 030 342 476 835 865 496 093 722 324 007 154 518 129 732 692 081 058 424 090 557 725 645 803 681 462 234 493 189 708 138 897 143 299 831 347 617 799 679 712 453 782 310 703 739 151 473 878 692 119 187 566 700 319 321 281 896 803 322 696 594 459 286 210 607 438 827 416 919 465 162 267 632 540 665 070 881 071 030 394 178 860 564 893 769 816 734 159 025 925 194 611 823 642 945 652 669 372 203 155 504 700 213 598 846 292 758 012 527 715 422 016 629 954 863 130 324 912 311 029 627 923 723 899 766 416 803 497 141 226 527 931 907 636 326 136 814 145 516 376 656 559 839 788 489 381 733 082 668 779 901 962 886 932 296 597 379 951 931 621 187 215 455 287 394 170 243 669 885 593 888 793 316 744 533 363 119 541 518 404 088 283 815 193 421 234 122 820 030 950 313 341 050 704 760 159 987 985 472 529 190 665 222 479 319 715 440 331 794 836 837 373 220 821 885 773 341 623 856 441 380 700 541 913 530 245 943 913 502 554 531 886 454 796 252 260 251 762 928 374 330 465 102 361 057 583 514 550 739 443 339 610 216 229 675 461 415 781 127 197 001 738 611 494 279 501 411 253 280 621 254 775 810 512 972 088 465 263 158 094 806 633 687 670 147 310 733 540 717 710 876 615 935 856 814 098 212 967 730 759 197 382 973 441 445 256 688 770 855 324 570 888 958 320 993 823 432 102 718 224 114 763 732 791 357 568 615 421 252 849 657 903 335 093 152 776 925 505 845 644 010 552 192 644 505 312 073 756 287 744 998 163 646 332 835 816 140 330 175 813 967 359 427 327 690 448 920 361 880 386 754 955 751 806 890 058 532 927 201 493 923 500 525 845 146 706 982 628 548 257 883 267 398 735 220 457 228 239 290 207 144 822 219 885 587 102 896 991 935 873 074 277 815 159 757 620 764 023 951 243 860 202 032 596 596 250 212 578 349 957 710 085 626 386 118 233 813 318 509 014 686 577 064 010 676 278 617 583 772 772 895 892 746 039 403 930 337 271 873 850 536 912 957 126 715 066 896 688 493 880 885 142 943 609 962 012 966 759 079 225 082 275 313 812 849 851 526 902 931 700 263 136 328 942 095 797 577 959 327 635 531 162 066 753 488 651 317 323 872 438 748 063 513 314 512 644 889 967 589 828 812 925 480 076 425 186 586 490 241 111 127 301 357 197 181 381 602 583 178 506 932 244 007 998 656 635 371 544 088 454 866 393 181 708 395 735 780 799 059 730 839 094 881 804 060 935 959 190 907 473 960 904 410 150 516 321 749 681 412 100 765 719 177 483 767 355 751 000 733 616 922 386 537 429 079 457 803 200 042 337 452 807 566 153 042 929 014 495 780 629 634 138 383 551 783 599 764 708 851 349 004 856 973 697 965 238 695 845 994 595 592 090 709 058 956 891 451 141 412 684 505 462 117 945 026 611 750 166 928 260 250 950 770 778 211 950 432 617 383 223 562 437 601 776 799 362 796 099 368 975 191 394 965 033 358 507 155 418 436 456 852 616 674 243 688 920 371 037 495 328 425 927 131 610 537 834 980 740 739 158 633 817 967 658 425 258 036 737 206 469 351 248 652 238 481 341 663 808 061 505 704 829 059 890 696 451 936 440 018 597 120 425 723 007 316 410 009 916 987 524 260 377 362 177 763 430 621 616 744 884 930 810 929 901 009 517 974 541 564 251 204 822 086 714 586 849 255 132 444 266 777 127 863 728 211 331 536 224 301 091 824 391 243 380 214 046 242 223 349 153 559 516 890 816 288 487 989 988 273 630 445 372 432 174 280 215 755 777 967 021 666 317 047 969 728 172 483 392 841 015 642 274 507 271 779 269 399 929 740 308 072 770 395 013 581 545 142 494 049 026 536 105 825 409 373 114 653 104 943 382 484 379 718 606 937 214 444 600 826 798 002 471 229 489 405 761 853 892 203 425 608 302 697 052 876 621 377 373 594 394 224 114 707 074 072 902 725 461 307 358 541 745 691 419 446 487 624 357 682 397 065 703 184 168 467 540 733 466 346 293 673 983 620 004 041 400 714 054 277 632 480 132 742 202 685 393 698 869 787 607 009 590 048 684 650 626 771 363 070 979 821 006 557 285 101 306 601 010 780 633 743 344 773 073 478 653 881 742 681 230 743 766 066 643 312 775 356 466 578 603 715 192 922 768 440 458 273 283 243 808 212 841 218 776 132 042 460 464 900 801 054 731 426 749 260 826 922 155 637 405 486 241 717 031 027 919 996 942 645 620 955 619 816 454 547 662 045 022 411 449 404 749 349 832 206 807 191 352 767 986 747 813 458 203 859 570 413 466 177 937 228 534 940 031 631 599 544 093 684 089 572 533 438 702 986 717 829 770 373 332 806 801 764 639 502 090 023 941 931 499 115 009 105 276 821 119 510 999 063 166 150 311 585 582 835 582 607 179 410 052 528 583 611 369 961 303 442 790 173 811 787 412 061 288 182 062 023 263 849 861 515 656 451 230 047 792 967 563 618 345 768 105 043 341 769 543 067 538 041 113 928 553 792 529 241 347 339 481 050 532 025 708 728 186 307 291 158 911 335 942 014 761 872 664 291 564 036 371 927 602 306 283 840 650 425 441 742 335 464 549 987 055 318 726 887 926 424 102 147 363 698 625 463 747 159 744 354 943 443 899 730 051 742 525 110 877 357 886 390 946 812 096 673 428 152 585 919 924 857 640 488 055 071 329 814 299 359 911 463 239 919 113 959 926 752 576 359 007 446 572 810 191 805 841 807 342 227 734 721 397 723 218 231 771 716 916 400 108 826 112 549 093 361 186 780 575 722 391 018 186 168 549 108 500 885 272 274 374 212 086 524 852 372 456 248 697 662 245 384 819 298 671 129 452 945 515 497 030 585 919 307 198 497 105 414 181 636 968 976 131 126 744 027 009 648 667 545 934 567 059 936 995 464 500 558 921 628 047 976 365 686 133 316 563 907 395 703 272 034 389 175 415 267 500 915 011 198 856 872 708 848 195 531 676 931 681 272 892 143 031 376 818 016 445 477 367 518 353 497 857 924 276 463 354 162 433 601 125 960 252 109 501 612 264 110 346 083 465 648 235 597 934 274 056 868 849 224 458 745 493 776 752 120 324 703 803 035 491 157 544 831 295 275 891 939 893 680 876 327 685 438 769 557 694 881 422 844 311 998 595 700 727 521 393 176 837 831 770 339 130 423 060 958 999 137 314 684 569 010 422 095 161 967 070 506 420 256 733 873 446 115 655 276 175 992 727 151 877 660 010 238 944 760 539 789 516 945 708 802 728 736 225 121 076 224 091 810 066 700 883 474 737 605 156 285 533 943 565 843 756 271 241 244 457 651 663 064 085 939 507 947 550 920 463 932 245 202 535 463 634 444 791 755 661 725 962 187 199 279 186 575 490 857 852 950 012 840 229 035 061 514 937 310 107 009 446 151 011 613 712 423 761 426 722 541 732 055 959 202 782 129 325 725 947 146 417 224 977 321 316 381 845 326 555 279 604 270 541 871 496 236 585 252 458 648 933 254 145 062 642 337 885 651 464 670 604 298 564 781 968 461 593 663 288 954 299 780 722 542 264 790 400 616 019 751 975 007 460 545 150 060 291 806 638 271 497 016 110 987 951 336 633 771 378 434 416 194 053 121 445 291 855 180 136 575 558 667 615 019 373 029 691 932 076 120 009 255 065 081 583 275 508 499 340 768 797 252 369 987 023 567 931 026 804 136 745 718 956 641 431 852 679 054 717 169 962 990 363 015 545 645 090 044 802 789 055 701 968 328 313 630 718 997 699 153 166 679 208 958 768 572 290 600 915 472 919 636 381 673 596 673 959 975 710 326 015 571 920 237 348 580 521 128 117 458 610 065 152 598 883 843 114 511 894 880 552 129 145 775 699 146 577 530 041 384 717 124 577 965 048 175 856 395 072 895 337 539 755 822 087 777 506 072 339 445 587 895 905 719 156 736

WOAH!!!

That's huge! And it get's worse:

R₂(6) = R(R₂(5)) =

R(2003529 ... ... 156736) = 2^{2003529 ... ... 156736}

Mind blowing!!! This number is roughly about 10^{10^19,727}. That's EE19,727.

And keep in mind that we've only placed the number 6, inside the second application of primitive recursion, to the modest function f(n) = 2n. Perhaps your beginning to sense the potential here?

But wait, we've already seen numbers this big in our -illion article. There were higher tier numbers larger than this. How quickly is the function R₂(n) actually growing. Well observe this pattern:

R₂(1) = 2

R₂(2) = 2^2

R₂(3) = 2^(2^2)

R₂(4) = 2^(2^(2^2))

R₂(5) = 2^(2^(2^(2^2)))

R₂(6) = 2^(2^(2^(2^(2^2))))

...

and in general

R₂(n) = 2^(2^(2^(2^ ... ^(2^(2^2)) ... ))) w/n 2's

It is not difficult to show this. Just consider that:

R₂(n+1) = R(R₂(n)) = 2^R₂(n)

So the previous output is being used as the new exponent for 2^x, and the result is a stack of exponents. In essence, R₂ is going up 1 tier, every time the argument increases by 1! That's very rapid growth.

You might argue that the numbers we are generated can still be defined with elementary formulas, so how has this radically changed anything. However, R₂ is very different than the functions we have explored earlier. It can not be described by a single elementary formula!

R₂(n) =! 2^n

R₂(n) =! 2^(2^n)

R₂(n) =! 2^(2^(2^n))

etc.

None of these formulas captures the nature of the function, and in fact, R₂ grows faster than any of these, because eventually the stack defined by R₂ becomes larger than any stack defined in an elementary formula. R₂ also grows radically faster than any elementary formula.

Although we have spent a lot of time carefully developing the concept of functions and the primitive recursion, we can now finally get a small taste of the pay off. Where as we spent a lot of time developing multi-tier systems, it should be clear now that with functions we don't need names for all numbers, to define a very large finite number. The linguistic component was actually holding us back! Consider how easy it is now to totally transcend the numbers discussed in the -illion article. Consider the size of R₂(100), or R₂(1000), or R₂(1,000,000) or R₂(1,000,000,000)...

Wait, that's familiar; couldn't we just continue with the -illion numbers. So we're just stuck again in the old paradigm. Not at all. These decimal expansions are no longer the largest numbers we have at our disposal! R₂(100) is way bigger than anything like that, so ... why not plug that into the function:

R₂(R₂(100))

And we needn't stop there. This is merely a functional power of R₂, but we could generalize this by simply applying another primitive recursion base 1 to R₂. So let:

R₃(0) = 1

&

R₃(n) = R₂(R₃(n-1)) , when n>0

This recursive function will quickly surpass R₂(R₂(100)):

R₃(0) = 1

R₃(1) = R₂(R₃(0)) = R₂(1) = 2

R₃(2) = R₂(R₃(1)) = R₂(2) = 2^2 = 4

R₃(3) = R₂(R₃(2)) = R₂(4) = 2^2^2^2 = 65,536

R₃(4) = R₂(R₃(3)) = R₂(65,536) > R₂(100)

R₃(5) = R₂(R₃(4)) = R₂(R₂(65,536)) > R₂(R₂(100))

R₃(6) = R₂(R₂(R₂(65,536))) = HUGE!!!

It's difficult to come to terms with the number R₃(6). Imagine a power tower of 65,536 2s. That, when it's decimal was computed, would be a number so massive that it couldn't fit into the space of the observable universe (a property that will become frightfully common as we progress through large numbers!). In fact, it's hard to convey to the laymen just how much vaster than number is! Imagine the universe as just a tiny sub-atomic particle in a larger universe with as many observable universes, as the observable universe has particles! Call this the 2nd order Hubble Volume. Now imagine a 3rd order Hubble Volume made up of particles the size of 2nd order Hubble Volumes. Now generalize this idea, so that the (n+1)th order Hubble Volume is made up of particles of the nth order Hubble Volume. Even if we went up to the 10^80th order Hubble Volume, we STILL would not have anywhere near enough space to contain the digits of a power tower of 65,536 2's. In fact, the number is so inexplicably large, that you would have to go to a Hubble Volume of such a massive order, that THAT number would not be comprehensible to the laymen. In fact the order of the Hubble volume, just to store the digits of the decimal expansion of a power tower of 65,536 2s, would be ITSELF a power tower of 65,534 2s!

To store the digits of THAT number would itself take an Hubble Volume order roughly equal to a power tower of 65,532 2's. We could continue to repeat this process, finding the order of the Hubble volume, then trying to store that number and finding out what order Hubble volume that would require ... and after roughly 32,000 applications of this technique we would eventually reach a number small enough that it would only require about the 19,727th order Hubble Volume. That's the kind of number we're dealing with. This is already insanely beyond anything we would recognize as known reality...

And this is NOT what R₃(6) is! That Number is Just R₃(4). Now imagine a power tower with R₃(4) 2's. This number is so large that we would have to apply the above trick, not 32,000 times, but roughly R₃(4) times to get it down to familiar numbers!

And that is STILL NOT R₃(6)! That's only R₃(5). R₃(6) is a power tower of 2's with R₃(5) terms!

There is an entire multiverse of large numbers out there to explore, and we have just caught a single definite member out of this fantastic world, and given it a precise description! This is the power of just THREE applications of Primitive Recursion! The number R₃(6), beats everything in the illion articles and just completely leaves it in the dust. Furthermore, the definition is exceptionally tidy and simple. Here is the definition in full:

R(n) = 2ⁿ : n = {0,1,2,3,...}

R₂(n) = 1 : n=0

R₂(n) = R(R₂(n-1)) : n>0

R₃(n) = 1 : n=0

R₃(n) = R₂(R₃(n-1)) : n>0

In just 5 lines of mathematics we have easily transcended what almost anyone would come up with if asked to come up with a really really big number; and this is just the beginning ... it now becomes completely routine the apply primitive recursion as many times as we like. Just try to imagine the meaning of an expression like R₁₀₀(100). The human mind just can't wrap itself around something like that ... it transcends human understanding. And it gets far far worse... we can devise complex and elaborate systems, hierarchies, involving repeated application of primitive recursion. Even the slightest application of these systems results in numbers that far exceed anything the average person is likely to imagine. In fact these methods for obtaining vastly huge numbers are very recent human inventions. Only in the last 200 years did mathematicians begin to really develop the mathematics of recursive functions (in preparation for the development of the modern computer no less!). No number in antiquity even comes close to R₁₀₀(100)...

What I'm trying to convey is simply the sheer transcendence of the recursive method. Hopefully, although these methods took a while to develop, you can now appreciate their incredible superiority to our previous paradigm of extending a naming scheme, or using decimal notation or power towers to define a large number. These methods are deeper, more general, and much much more powerful than any kind of explicit formula. They generate newer and newer kinds of functions, and thereby newer and newer kinds of large numbers ... ad infinitum. While we might not be getting to infinity any faster than we were by simply counting 1,2,3 ... we are now accelerating at an ever increasing, ever more frighting rate, away from the small positive integers to a realm, transcendent, glorious and sacred. A place no human mind will ever exhaust, and where even gods discover they are not top of the heap, but merely beings along an infinite stairway of being ... not ending with infinity ... but never ending ... ever ...

Now intrepid mortal, ... are you brave enough to continue on these fringe borders of the mathematical landscape? If so, proceed to the next article in which we learn another trick, just as fundamental as primitive recursion, that when used in conjunction will open the flood gates to recursion without end ...