Hi Tom,

Apparently you have (re)discover Ackermann function which indeed provide formally a sequence of more and more growing functions, similar to the sequence I was pointing too. I will present it in a easier way for the benefit of the others, but also for using a presentation which will facilitate the future successive diagonalizations. In your second recent post you got the first diagonalization right (or almost right) but the diag is quite hidden and it would be hard to continue the process.

(Note that you could have define f(0, m, n) as the successor function)

So your sequence of functions are, in your "Ackerman like parametrized presentation", the functions f(1, m, n) is m + n (or m [1] n, writting "+" as [1] ; for first function)
f(2, m, n)        is      m  *  n      (or m [2]  n)
f(3, m, n)        is      m  ^  n  (or m [3] n)
f(4, m, n)        is      m  [4]  n
f(5, m, n)        is      m  [5]   n    
etc


It will be easier to diagonalize functions of one argument, that is x + x, x * x, x ^ x, x [4] x, x[5]x, etc.

Let us see their values on 10:

1) 10 + 10 = 20
2) 10 * 10 =  10+10+10+10+10+10+10+10+10 = 100  (ten sums)
3) 10 ^ 10 = 10*10*10*10*10*10*10*10*10 =  10000000000  (ten products)
4) 10 [4] 10 = 10 ^ (10 ^ (10 ^ (10 ^ (10 ^ (10 ^ (10 ^ (10 ^ (10 ^ 10))))))))) (ten exponentiations) Note the parenthesis: schoolboys/girls know that a ^ (b ^ c) is in general different and bigger than (a ^ b) ^ c .

Note also that 10 [4] 10 is already so big that the known observed part of the physical universe is not enough big to write its digits. [4] is called tetration, and 10 [4] 10 can be read 10 tetrated up to 10 (like 10 ^ 10 can be read as 10 up to the power of 10). Each function (operation) is the iteration of the preceding one. So:

5) 10 [5] 10 = 10 [4] (10 [4] (10 [4] (10 [4] (10 [4] (10 [4] (10 [4] (10 [4] (10 [4] (10 [4] 10))))))))))

6) 10 [6] 10 = 10 [5] (10 [5] (10 [5] (10 [5] (10 [5] (10 [5] (10 [5] (10 [5] (10 [5] (10 [5] 10))))))))))

etc.

Those are unimaginably BIG numbers. Archimedes biggest number 10^63 is far greater than 10 [3] 10 (that is 10 ^ 10), but "infinitesimal" compared to 10 [4] 10, which is itself "infinitesimal" compared to 10 [5] 10, not to speak of 10 [1000] 10 ....

So if you give something like (10 [10] 10) [100] (10 [10] 10), having defined the [i] for i = 1 to 100, then you are specifying a *very very very* huge number.

I give, for all, one last exercise before introducing diagonalization: define recursively in an explicit way the operation [i+1] from the preceding operation [i]. If you know a "computer language" (Fortran, Lisp, Prolog, c++, Java, whatever ...) write the program. If you don't know any such language, read my "combinators posts" and program those function with S and K, (if you have the time). Well, just be sure you follow the idea.

Must leave now.


Bruno



Le 21-mai-06, à 09:08, Tom Caylor a écrit :


I've been working on this off and on when I get a chance, even before
my "first guess".  My version of this defines an operation as a
recursive function f(N,m,n), where N is the degree of the operation.
m is one of the operands.   n is the other operand, which is the
counting operand.  n is the number iterations that the recursive
function is evaluated.

I'll call addition the operation of degree 1. So addition can be
defined as follows.

Initial value:
f(1,m,0) = m

Recursion rule:
f(1,m,k) = f(1,m,k-1) + 1

So for a given n,
f(1,m,n) = f(1,...f(1,m,0) + 1,... + 1)   (f(1) taken n times)
            = f(1,m,0) + 1 + ... + 1        (1 added n times)
            = f(1,m,0) + n
            = m + n

Note that counting can be separately defined as the operation of degree
0, but this didn't add to the current argument.  Counting is also
equivalent to adding with m=0.

Multiplication is defined in a similar manner, as the operation of
degree 2.

Initial value:
f(2,m,0) = 0

Recursion rule:
f(2,m,k) = f(2,m,k-1) + m

So for a given n,
f(2,m,n) = f(2,...f(2,m,0) + m,... + m)   (f(2) taken n times)
            = f(2,m,0) + m + ... + m        (m added n times)
            = f(2,m,0) + m * n
            = m * n

Exponentiation is the operation of degree 3.

f(3,m,0) = 1
f(3,m,k) = f(3,m,k-1) * m
f(3,m,n) = f(3,...f(3,m,0) * m,...* m)   (f(3) taken n times)
            = f(3,m,0) * m * ... * m        (m multiplied n times)
            = f(3,m,0) * m ^ n
            = m ^ n

Just for kicks, I tried to define "hyper-nentiation" as the operation
of degree 4, with operator symbol "@".  I was interested in what
the initial value of this would be: the mth root of m.  Any further
than this gets too weird for me.

f(4,m,0) = m^(1/m)
f(4,m,1) = m
f(4,m,k) = f(4,m,k-1) ^ m
f(4,m,n) = f(4,...f(4,m,0) ^ m,...^ m)   (f(4) taken n times)
            = m ^ m ^ ... ^ m                (m exponentiated n times)
            = m @ n

Looking closer specifically at multiplication, we see that it is
defined in terms of addition, which is the preceding function in the
sequence of functions.

f(2,m,n) = f(2,m,n-1) + m
            = f(1,m,f(2,m,n-1))
            = f(1,m,f(2,m,n-2)+m)
            = f(1,m,f(1,m,f(2,m,n-2)))
            = f(1,m,f(1,m,f(2,n-3,m)+m))
            = f(1,m,f(1,m,f(1,m,f(2,m,n-3))))
            = f(1,m,...f(2,m,n-n)+m)...)     (f(1) taken n-1 times,
f(2) taken 1 time)
            = f(1,m,...f(2,m,n-n))              (f(1) taken n times,
f(2) taken 1 time)
            = f(1,m,...f(2,m,0))                 (f(1) taken n times,
f(2) taken 1 time)
            = f(1,m,...f(1,m,0))                 (f(1) taken n times)
            = m * n

The above is a formal way of saying that multiplication of m and n is
adding n m's together.  We knew that.

Generalizing this, given the function in the sequence corresponding to
the operation of degree N.

f(N,m,n) = f(N-1,m,...f(N-1,m,n))         (f(N-1) taken n times)

The above is a formal way of saying that f(N)ing of m and n together is
the same as f(N-1)ing n m's together.

The sequence of ever growing functions is defined as f(N,m,n) for N=
1,2,3,...
Given a function of degree N, I take the growth of f(N,m,n) as defined
as its magnitude as n approaches infinity.

So here's a thought toward finding a function that's bigger than
any function in this sequence.  Define the following function.

d(m,n) = f(1,m,...f(n,m,n))

Note that n has been placed not only as the counting operation, but
also as the degree!  So now as n approaches infinity, the degree
approaches infinity. (!)  So here is a single function that has a
degree of operation that is higher than any function of a given degree
of operation.

Am I on the right track?

Tom


http://iridia.ulb.ac.be/~marchal/

X-Google-Language: ENGLISH,ASCII
Received: by 10.54.160.18 with SMTP id i18mr191684wre;
       Mon, 22 May 2006 05:29:35 -0700 (PDT)
Return-Path: <[EMAIL PROTECTED]>
Received: from bonito.ulb.ac.be (bonito.ulb.ac.be [164.15.59.220])
       by mx.googlegroups.com with ESMTP id v23si963617cwb.2006.05.22.05.29.34;
       Mon, 22 May 2006 05:29:35 -0700 (PDT)
Received-SPF: pass (googlegroups.com: best guess record for domain of [EMAIL 
PROTECTED] designates 164.15.59.220 as permitted sender)
Received: from mach.vub.ac.be (maxi.ulb.ac.be [164.15.128.8])
        by bonito.ulb.ac.be (Postfix) with ESMTP id 9EDD72F
        for <everything-list@googlegroups.com>; Mon, 22 May 2006 14:29:33 +0200 
(CEST)
Received: by mach.vub.ac.be (Postfix, from userid 21099)
        id 7E9C78D27; Mon, 22 May 2006 14:29:33 +0200 (CEST)
Received: from [164.15.10.83] (post.ulb.ac.be [164.15.10.83])
        by mach.vub.ac.be (Postfix) with ESMTP id 1AE668D02
        for <everything-list@googlegroups.com>; Mon, 22 May 2006 14:29:32 +0200 
(CEST)
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
In-Reply-To: <[EMAIL PROTECTED]>
References: <[EMAIL PROTECTED]> <[EMAIL PROTECTED]> <[EMAIL PROTECTED]> <[EMAIL PROTECTED]> <[EMAIL PROTECTED]> 
<[EMAIL PROTECTED]> <[EMAIL PROTECTED]> <[EMAIL PROTECTED]> <[EMAIL PROTECTED]> <[EMAIL PROTECTED]> <[EMAIL 
PROTECTED]>
Message-Id: <[EMAIL PROTECTED]>
From: Bruno Marchal <[EMAIL PROTECTED]>
Subject: Re: Smullyan Shmullyan, give me a real example
Date: Mon, 22 May 2006 14:29:26 +0200
To: everything-list@googlegroups.com
X-Mailer: Apple Mail (2.623)
X-Spam-Checker-Version: maxi.ulb.ac.be SA 2.63 (2004-01-11)
X-Spam-Status: No, hits=0.0, level
Hi Tom,

Apparently you have (re)discover Ackermann function which indeed provide formally a sequence of more and more growing functions, similar to the sequence I was pointing too. I will present it in a easier way for the benefit of the others, but also for using a presentation which will facilitate the future successive diagonalizations. In your second recent post you got the first diagonalization right (or almost right) but the diag is quite hidden and it would be hard to continue the process.

(Note that you could have define f(0, m, n) as the successor function)

So your sequence of functions are, in your "Ackerman like parametrized presentation", the functions f(1, m, n) is m + n (or m [1] n, writting "+" as [1] ; for first function)
f(2, m, n)        is      m  *  n      (or m [2]  n)
f(3, m, n)        is      m  ^  n  (or m [3] n)
f(4, m, n)        is      m  [4]  n
f(5, m, n)        is      m  [5]   n    
etc


It will be easier to diagonalize functions of one argument, that is x + x, x * x, x ^ x, x [4] x, x[5]x, etc.

Let us see their values on 10:

1) 10 + 10 = 20
2) 10 * 10 =  10+10+10+10+10+10+10+10+10 = 100  (ten sums)
3) 10 ^ 10 = 10*10*10*10*10*10*10*10*10 =  10000000000  (ten products)
4) 10 [4] 10 = 10 ^ (10 ^ (10 ^ (10 ^ (10 ^ (10 ^ (10 ^ (10 ^ (10 ^ 10))))))))) (ten exponentiations) Note the parenthesis: schoolboys/girls know that a ^ (b ^ c) is in general different and bigger than (a ^ b) ^ c .

Note also that 10 [4] 10 is already so big that the known observed part of the physical universe is not enough big to write its digits. [4] is called tetration, and 10 [4] 10 can be read 10 tetrated up to 10 (like 10 ^ 10 can be read as 10 up to the power of 10). Each function (operation) is the iteration of the preceding one. So:

5) 10 [5] 10 = 10 [4] (10 [4] (10 [4] (10 [4] (10 [4] (10 [4] (10 [4] (10 [4] (10 [4] (10 [4] 10))))))))))

6) 10 [6] 10 = 10 [5] (10 [5] (10 [5] (10 [5] (10 [5] (10 [5] (10 [5] (10 [5] (10 [5] (10 [5] 10))))))))))

etc.

Those are unimaginably BIG numbers. Archimedes biggest number 10^63 is far greater than 10 [3] 10 (that is 10 ^ 10), but "infinitesimal" compared to 10 [4] 10, which is itself "infinitesimal" compared to 10 [5] 10, not to speak of 10 [1000] 10 ....

So if you give something like (10 [10] 10) [100] (10 [10] 10), having defined the [i] for i = 1 to 100, then you are specifying a *very very very* huge number.

I give, for all, one last exercise before introducing diagonalization: define recursively in an explicit way the operation [i+1] from the preceding operation [i]. If you know a "computer language" (Fortran, Lisp, Prolog, c++, Java, whatever ...) write the program. If you don't know any such language, read my "combinators posts" and program those function with S and K, (if you have the time). Well, just be sure you follow the idea.

Must leave now.


Bruno



Le 21-mai-06, à 09:08, Tom Caylor a écrit :


I've been working on this off and on when I get a chance, even before
my "first guess".  My version of this defines an operation as a
recursive function f(N,m,n), where N is the degree of the operation.
m is one of the operands.   n is the other operand, which is the
counting operand.  n is the number iterations that the recursive
function is evaluated.

I'll call addition the operation of degree 1. So addition can be
defined as follows.

Initial value:
f(1,m,0) = m

Recursion rule:
f(1,m,k) = f(1,m,k-1) + 1

So for a given n,
f(1,m,n) = f(1,...f(1,m,0) + 1,... + 1)   (f(1) taken n times)
            = f(1,m,0) + 1 + ... + 1        (1 added n times)
            = f(1,m,0) + n
            = m + n

Note that counting can be separately defined as the operation of degree
0, but this didn't add to the current argument.  Counting is also
equivalent to adding with m=0.

Multiplication is defined in a similar manner, as the operation of
degree 2.

Initial value:
f(2,m,0) = 0

Recursion rule:
f(2,m,k) = f(2,m,k-1) + m

So for a given n,
f(2,m,n) = f(2,...f(2,m,0) + m,... + m)   (f(2) taken n times)
            = f(2,m,0) + m + ... + m        (m added n times)
            = f(2,m,0) + m * n
            = m * n

Exponentiation is the operation of degree 3.

f(3,m,0) = 1
f(3,m,k) = f(3,m,k-1) * m
f(3,m,n) = f(3,...f(3,m,0) * m,...* m)   (f(3) taken n times)
            = f(3,m,0) * m * ... * m        (m multiplied n times)
            = f(3,m,0) * m ^ n
            = m ^ n

Just for kicks, I tried to define "hyper-nentiation" as the operation
of degree 4, with operator symbol "@".  I was interested in what
the initial value of this would be: the mth root of m.  Any further
than this gets too weird for me.

f(4,m,0) = m^(1/m)
f(4,m,1) = m
f(4,m,k) = f(4,m,k-1) ^ m
f(4,m,n) = f(4,...f(4,m,0) ^ m,...^ m)   (f(4) taken n times)
            = m ^ m ^ ... ^ m                (m exponentiated n times)
            = m @ n

Looking closer specifically at multiplication, we see that it is
defined in terms of addition, which is the preceding function in the
sequence of functions.

f(2,m,n) = f(2,m,n-1) + m
            = f(1,m,f(2,m,n-1))
            = f(1,m,f(2,m,n-2)+m)
            = f(1,m,f(1,m,f(2,m,n-2)))
            = f(1,m,f(1,m,f(2,n-3,m)+m))
            = f(1,m,f(1,m,f(1,m,f(2,m,n-3))))
            = f(1,m,...f(2,m,n-n)+m)...)     (f(1) taken n-1 times,
f(2) taken 1 time)
            = f(1,m,...f(2,m,n-n))              (f(1) taken n times,
f(2) taken 1 time)
            = f(1,m,...f(2,m,0))                 (f(1) taken n times,
f(2) taken 1 time)
            = f(1,m,...f(1,m,0))                 (f(1) taken n times)
            = m * n

The above is a formal way of saying that multiplication of m and n is
adding n m's together.  We knew that.

Generalizing this, given the function in the sequence corresponding to
the operation of degree N.

f(N,m,n) = f(N-1,m,...f(N-1,m,n))         (f(N-1) taken n times)

The above is a formal way of saying that f(N)ing of m and n together is
the same as f(N-1)ing n m's together.

The sequence of ever growing functions is defined as f(N,m,n) for N=
1,2,3,...
Given a function of degree N, I take the growth of f(N,m,n) as defined
as its magnitude as n approaches infinity.

So here's a thought toward finding a function that's bigger than
any function in this sequence.  Define the following function.

d(m,n) = f(1,m,...f(n,m,n))

Note that n has been placed not only as the counting operation, but
also as the degree!  So now as n approaches infinity, the degree
approaches infinity. (!)  So here is a single function that has a
degree of operation that is higher than any function of a given degree
of operation.

Am I on the right track?

Tom


http://iridia.ulb.ac.be/~marchal/


--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to everything-list@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at 
http://groups.google.com/group/everything-list
-~----------~----~----~----~------~----~------~--~---

Reply via email to