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 "-AT_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 -AT_SYMBOL- 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: <marchal.domain.name.hidden>
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 marchal.domain.name.hidden 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.domain.name.hidden>; 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.domain.name.hidden>; 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: <1148195305.041978.291700.domain.name.hidden>
References: <14762723.1143066850497.JavaMail.root.domain.name.hidden> <200603241938.14450.quentin.anciaux.domain.name.hidden.be> <1143229104.805923.181410.domain.name.hidden.googlegroups.com> <200603242045.08484.quentin.anciaux.domain.name.hidden.be> <1143229759.310865.304480.domain.name.hidden.googlegroups.com> <44245849.3060503.domain.name.hidden.fr> <442485EE.6010907.domain.name.hidden.net> <44f38451d0bd50dafb206875eb78cd17.domain.name.hidden.ac.be> <1147793509.349430.290120.domain.name.hidden.googlegroups.com> <020c0db89efdf147a862b8c8e2bee821.domain.name.hidden.ac.be> <1148195305.041978.291700.domain.name.hidden.googlegroups.com>
Message-Id: <f9d03231bf44a02ea5974db6518f1aa1.domain.name.hidden>
From: Bruno Marchal <marchal.domain.name.hidden>
Subject: Re: Smullyan Shmullyan, give me a real example
Date: Mon, 22 May 2006 14:29:26 +0200
To: everything-list.domain.name.hidden
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
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 "-AT_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 -AT_SYMBOL- 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.domain.name.hidden
To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list
-~----------~----~----~----~------~----~------~--~---
Received on Mon May 22 2006 - 08:30:37 PDT