Bird’s Multi-Dimensional Array Notation

Handles recursive functions with limit ordinal ωω

Notes

1. This is an extension of Bird’s Linear Array Notation in that it caters for arrays in 2, 3 or a higher
number of dimensions.
2. [n] is a separator (enclosed in square brackets) marking the end of an n-1 dimensional space (or
(n-1)-space) of the array. For example, [2] marks the end of a 1-space or ‘row’, [3] marks the end
of a 2-space or ‘plane’, and so on. An array where the highest number enclosed in square
brackets is n is an n dimensional array.
3. ‘a ‹n› b’ represents an n dimensional b^n string of a’s (see Angle Bracket Strings on pages 2-3).
4. # and #* are strings of characters representing the remainder of the array (if they exist).
5. The comma (,) is used as shorthand for the [1] separator.

The Multi-Dimensional Array Notation has 7 rules of operation

Rule 1 (only 1 or 2 entries, all in first 1-space):

{a} = a,
{a, b} = a^b.

Rule 2 (last entry in any 1-space or higher dimensional space of array is 1):
{# [a] 1} = {#}.
When a < b,
{# [a] 1 [b] #*} = {# [b] #*} (remove trailing 1’s in (b-1)-space).

Rule 3 (second entry is 1 or only 1 entry in first 1-space):

{a, 1 #} = a.
When b ≥ 2,
{a [b] #} = a.

Rule 4 (only 2 entries in first 1-space, next non-1 entry (c) not the first entry in its 1-space):
{a, b [n1] 1 [n2] 1 [n3] ... 1 [nk] 1, c #} = {a ‹n1-1› b [n1] a ‹n2-1› b [n2] ... a ‹nk-1› b [nk] R, c-1 #},
where R = {a, b-1 [n1] 1 [n2] 1 [n3] ... 1 [nk] 1, c #}.
n1 ≥ 2 (as [n1] is immediately after the first 1-space) and n1 ≥ n2 ≥ ... ≥ nk (as a result of Rule 2). The
entry corresponding to the last 1 of the unbroken string of 1’s is replaced by a copy of the entire array
with its second entry reduced by 1. For each 1 ≤ i ≤ k, the 1 prior to the [ni] separator (‘a, b’ in the case
i = 1) is replaced by an (ni-1) dimensional b^(ni-1) string of a’s.

Rule 5 (only 2 entries in first 1-space, next non-1 entry (c) is first entry in its 1-space):
{a, b [n1] 1 [n2] 1 [n3] ... 1 [nk] c #} = {a ‹n1-1› b [n1] a ‹n2-1› b [n2] ... a ‹nk-1› b [nk] c-1 #}.
nk ≥ 2 (as [nk] is immediately before the start of a 1-space) and n1 ≥ n2 ≥ ... ≥ nk ≥ 2 (as a result of Rule
2). Similar to Rule 4 except that there are no commas after the 1’s in the unbroken string of 1’s. The
last 1 of the unbroken string is replaced by an (nk-1) dimensional b^(nk-1) string of a’s.

1
Rule 6 (Rules 1-5 do not apply, third entry is 1):
{a, b, 1, ... , 1, c #} = {a, a, a, ... , {a, b-1, 1, ... , 1, c #}, c-1 #}.
The ‘...’ between the 1’s represents an unbroken string of one or more 1’s – the last 1 of this unbroken
string is replaced by a copy of the entire array with its second entry reduced by 1, and all entries prior
to this become an unbroken string of a’s.

Rule 7 (Rules 1-6 do not apply):

{a, b, c #} = {a, {a, b-1, c #}, c-1 #}.

It is helpful when the rules are considered in sequence; first use Rule 1 if it applies, if not then use
Rule 2, etc. If none of Rules 1-6 apply then Rule 7 will.

About the Multi-Dimensional Array Notation

For every integer n ≥ 1, the entries in the second or subsequent n-spaces can only be reduced in
value when the number of entries in the first n-space is reduced to two entries (both in the first
1-space). In addition, it is only possible to reduce the values of the entries in the third or subsequent
n-spaces when all of the previous n-spaces (excluding the first 1-space) contain a single 1.

When a 1 is found between a pair of separators, Rule 2 compares the numbers inside the pair of
separators. If the number in the left of the pair is less than the number in the right, the 1 between
them is said to be ‘trailing’ and is removed along with the left separator.

The two new rules where a first 1-space of two entries is followed by a separator of [2] or higher
(Rules 4 and 5) have been designed to accommodate the possibility of strings of 1’s and separators –
with Rule 4 also catering for the scenario of a string of one or more 1’s (separated by commas or [1]
separators) following the higher-order separators. Under these Rules, each 1 preceding a separator
of [2] or higher in the unbroken string of 1’s and separators after the first 1-space is filled with an n-1
dimensional b^(n-1) string of a’s, where a and b are the first and second entries respectively in the
first 1-space and n is the number in that particular separator. (The first 1-space is replaced by an m-1
dimensional b^(m-1) string of a’s, where [m] is the separator immediately after the second entry.)
Such numbers grow at a phenomenal rate indeed under Rules 4 and 5.

Bird’s Multi-Dimensional Array Notation handles recursive functions with limit ordinal ω^ω since this is
the limit ordinal of the number of arguments (or entries) in the array. The number of arguments in
each 1-space has limit ordinal ω, and so do the number of 1-spaces in each 2-space and the number
of 2-spaces in each 3-space, and so on. Since the number of dimensions also has limit ordinal ω, we
multiply ω by itself ω times to find the limit ordinal of the number of arguments in the array.

Angle Bracket Strings

These are defined as follows:

‘a ‹0› b’ = ‘a’,
‘a ‹1› b’ = ‘a, a, a, ... , a’ (b terms of a),
‘a ‹2› b’ = ‘a ‹1› b [2] a ‹1› b [2] ... [2] a ‹1› b’ (b terms of ‘a ‹1› b’),
‘a ‹3› b’ = ‘a ‹2› b [3] a ‹2› b [3] ... [3] a ‹2› b’ (b terms of ‘a ‹2› b’),
‘a ‹4› b’ = ‘a ‹3› b [4] a ‹3› b [4] ... [4] a ‹3› b’ (b terms of ‘a ‹3› b’),

2
and so on. In general (for n ≥ 1),
‘a ‹n› b’ = ‘a ‹n-1› b [n] a ‹n-1› b [n] ... [n] a ‹n-1› b’ (b terms of ‘a ‹n-1› b’).

Since strings (such as ‘a ‹n› b’) can form part of an array (rather than the whole array), we can write
them in inverted commas, and when a string can be replaced by another string, we write this as in the
following example,
‘a ‹1› b’ = ‘a, a, a, ... , a’ (with b a’s),
where the ‘=’ sign means ‘is replaced by’. Thus, all ‘a ‹1› b’ strings can be replaced by
‘a, a, a, ... , a’ (with b a’s) and vice versa.

For each integer n ≥ 1, ‘a ‹n› b’ represents an n-space string containing b (n-1)-spaces of the string
‘a ‹n-1› b’. Note that each of the ‘a ‹n› b’ terms (when written in inverted commas) represents a
string (and should not be confused with a number); unlike numbers, strings can be replaced by longer
strings, for example, every ‘a ‹n› b’ in an array can be replaced by b copies of ‘a ‹n-1› b’ (separated
by [n] separators), and we can continue this further until each ‘a ‹1› b’ gets replaced by b copies of
‘a’ (separated by commas). Angle brackets are suitable for these strings since they are shaped like
left and right arrows, and therefore show that each of these strings can ‘expand’ into longer strings.

Examples

In the second dimension,

{a, b [2] 2} = {a ‹1› b}
= {a, a, a, ... , a} (b entries of ‘a’),
{a, b [2] c} = {a ‹1› b [2] c-1}
= {a, a, a, ... , a [2] c-1} (b entries of ‘a’ in first ‘row’).

The growth rate of Friedman’s n(k) function for k-character sequences in his Block Subsequence
Theorem is broadly comparable to that of
f(n) = {3, n [2] 2}
= {3, 3, 3, ... , 3} (with n entries).

While the number

{3, 2, 2 [2] 2} = {3, 3 [2] 2}
= {3, 3, 3}
= 3 {3} 3,
the number
{3, 3, 2 [2] 2} = {3, {3, 2, 2 [2] 2} [2] 2}
= {3, {3, 3, 3} [2] 2}
= {3, (3 {3} 3) [2] 2}
= {3, 3, 3, ... , 3} (with 3 {3} 3 entries),
which is so huge that even when expressed as an ordinary ‘1 dimensional’ array would require a
massive 3 {3} 3 entries. Even 3 {3} 3 is a power tower of 7,625,597,484,987 3’s.

The numbers
{3, 4, 2 [2] 2} = {3, {3, 3, 2 [2] 2} [2] 2}
= {3, 3, 3, ... , 3} (with {3, 3, 2 [2] 2} entries),
{3, 5, 2 [2] 2} = {3, {3, 4, 2 [2] 2} [2] 2}
= {3, 3, 3, ... , 3} (with {3, 4, 2 [2] 2} entries),

3
which means that, in general,
{3, b, 2 [2] 2} = {3, {3, b-1, 2 [2] 2} [2] 2}
= {3, 3, 3, ... , 3} (with {3, b-1, 2 [2] 2} entries).

The number
{3, 3, 3 [2] 2} = {3, {3, 2, 3 [2] 2}, 2 [2] 2}
= {3, {3, 3, 2 [2] 2}, 2 [2] 2}
is as above but with b = {3, 3, 2 [2] 2}, in other words, it would require {3, 3, 3, ... , 3} (with 3 {3} 3
entries) layers!

The number
{3, 3 [2] 3} = {3, 3, 3 [2] 2}
is as big as the last number.

While
{3, 2 [2] 1, 2} = {3 ‹1› 2 [2] 3}
= {3, 3 [2] 3}
= {3, 3, 3 [2] 2}
is as big as the last number, the number
{3, 3 [2] 1, 2} = {3 ‹1› 3 [2] {3, 2 [2] 1, 2}}
= {3, 3, 3 [2] {3, 3 [2] 3}}
(the last number is now in the second dimension).

In the third dimension,

{a, b [3] 2} = {a ‹2› b}
= {a,a,...,a [2] a,a,...,a [2] ...... [2] a,a,...,a}
(with b ‘rows’ of b entries = b^2 entries of ‘a’),
{a, b [3] c} = {a ‹2› b [3] c-1}
= {a,a,...,a [2] a,a,...,a [2] ...... [2] a,a,...,a [3] c-1}
(with b ‘rows’ of b entries = b^2 entries of ‘a’ in first ‘plane’).

While the number

{3, 2, 2 [3] 2} = {3, 3 [3] 2}
= {3, 3, 3 [2] 3, 3, 3 [2] 3, 3, 3},
the number
{3, 3, 2 [3] 2} = {3, {3, 2, 2 [3] 2} [3] 2}
= {3, {3, 3, 3 [2] 3, 3, 3 [2] 3, 3, 3} [3] 2}
is so huge that it would require a staggering
{3, 3, 3 [2] 3, 3, 3 [2] 3, 3, 3}
‘rows’ (separated, of course, by [2] separators) with just that many number of entries (each containing
the number 3) in each ‘row’!

In the (n+1)th dimension,

{a, b [n+1] c} = {a ‹n› b [n+1] c-1}
(an n dimensional space of b^n entries of ‘a’ plus a single
number of c-1 in the (n+1)th dimension)
= {a ‹n-1› b [n] a ‹n-1› b [n] ... [n] a ‹n-1› b [n+1] c-1}
(with b ‘a ‹n-1› b’ strings).

4
A simple example of how angle bracket strings work is
‘3 ‹3› 2’ = ‘3 ‹2› 2 [3] 3 ‹2› 2’
= ‘3 ‹1› 2 [2] 3 ‹1› 2 [3] 3 ‹1› 2 [2] 3 ‹1› 2’
= ‘3, 3 [2] 3, 3 [3] 3, 3 [2] 3, 3’,
thus,
{3, 2 [4] 5} = {3 ‹3› 2 [4] 4}
= {3, 3 [2] 3, 3 [3] 3, 3 [2] 3, 3 [4] 4}
= {3 ‹1› 3 [2] 2, 3 [3] 3, 3 [2] 3, 3 [4] 4}
= {3, 3, 3 [2] 2, 3 [3] 3, 3 [2] 3, 3 [4] 4}.

The most complicated rule is Rule 4. An example of its application is given here:
{4, 3 [4] 1 [3] 1 [2] 1, 1, 1, 6}
= {4 ‹3› 3 [4] 4 ‹2› 3 [3] 4 ‹1› 3 [2] 4, 4, R, 5}
= {4,4,4 [2] 4,4,4 [2] 4,4,4 [3] 4,4,4 [2] 4,4,4 [2] 4,4,4 [3] 4,4,4 [2] 4,4,4 [2] 4,4,4 [4]
4,4,4 [2] 4,4,4 [2] 4,4,4 [3] 4,4,4 [2] 4,4,R,5},
where R = {4, 2 [4] 1 [3] 1 [2] 1, 1, 1, 6}
= {4 ‹3› 2 [4] 4 ‹2› 2 [3] 4 ‹1› 2 [2] 4, 4, 4, 5}
= {4,4 [2] 4,4 [3] 4,4 [2] 4,4 [4] 4,4 [2] 4,4 [3] 4,4 [2] 4,4,4,5}
= {4 ‹1› 4 [2] 3,4 [3] 4,4 [2] 4,4 [4] 4,4 [2] 4,4 [3] 4,4 [2] 4,4,4,5}
= {4,4,4,4 [2] 3,4 [3] 4,4 [2] 4,4 [4] 4,4 [2] 4,4 [3] 4,4 [2] 4,4,4,5}.

Author: Chris Bird (Gloucestershire, England, UK)

Last modified: 2 April 2012
Ε-mail: m.bird44 at btinternet.com (not clickable to thwart spambots!)