11/09/2011, 04:15 AM

(11/09/2011, 01:40 AM)JmsNxn Wrote: This is a rather disturbing flaw that I've come across with zeration that rather surprises me the authors didn't consider.This is only a problem if you consider the Ackermann function to be the standard for defining operations. The usual definition of the Ackermann function (not the original one) has:

By the Ackermann function:

[...]

A(0,n) = n+1

A(m,n) = 2 Δ{m-2} (n+3) - 3

where Δ{x} denotes the x'th operation. Notice that the operations are slightly off from the "standard" basic operations; this is usually not considered a problem because we're considering asymptotic behaviour here.

The motivation behind zeration is an operation that when repeated n times amounts to addition by n. So m zerated to itself n times should equal to m+n. Clearly, zeration should be somehow linked to the increment operator, since that's the only thing that can sanely give you addition by n when repeated n times. So m zerated to itself should equal (m+1). However, this tells us nothing about what happens if m is zerated to a number not equal to itself. So should m zerated to k be equal to (m+1) or (k+1)? It makes little sense to always choose one or the other, because then the operator is essentially unary and the other argument is always ignored. This is the reason the definition was chosen to be max(m,k)+1, since, "intuitively" speaking, the largest argument to the operation should dominate in the computation of the result. That this definition doesn't 100% fit into one of the definitions of the Ackermann function isn't really a problem, since the asymptotic behaviour of the n-times-composed function is the same. Besides, having the max operation come out as part of the basic operations hierarchy is nice, because it is quite frequently used in math.