Super duper recursive function

[exfret]

Okay, so safari crashed on me, so my well-written post on this super cool function I made was just destroyed, so I won't go into as much depth as I would if MY POSTS DIDN'T ALWAYS DISAPPEAR!!!! Sorry, just had to rant a little. Anyways, my function is basically defined as the (f(x),n) where you go to the f(n)th level recursion with f(x), which would probably mean something to you if stupid safari hadn't... *Exfret goes grumbling on about stuff*... Anyways, I'll just give you an example for when f(x)=x+1 and n=2.

First level: f(n)=2+1=3

Second level: f2(x)=f(x) applied to itself f(n) times=f(f(f(x)))=(((x)+1)+1)+1=x+3
f2(n)=n+3=2+3=5

Third level: ff(n)(x)=f3(x)=f2(x) applied to itself f2(n) times=f2(f2(f2(f2(f2(x)))))=(((((x)+3)+3)+3)+3)+3=x+3*5=x+15
ff(n)(n)=n+15=2+15=17

So you could return the function f(x)=x+15, or the number 17. This may not seem like a very quickly growing function, but if g(x)=x^(2^x), then (x+1,3)~g(g(g(870))). The arguments that returned 17 were f(x)=x+1 and n=2, but those that got this huge number were f(x)=x+1 and n=3. Oh, what a tiny change can do.

Here's the sequence varying n but keeping f(x) to x+1, starting at x=0:
1, 4, 17, a gazillion, then I don't even want to think about what comes after that...

Edit: It's actually 1,5,17 as ARP pointed out.

[robly18]

Sounds like a bit of a twist on the ackermann function?

Either way, sounds like a nice exercise in Haskell.

However, I can't quite understand it. I tried to code it to get a sense of it but I can't quite understand what we're doing here. So what does this function do then, exactly?

[A Random Player]

Looks to me that:

Code: Select all

H(f, n) takes a function f and a (non-negative integral) number n, and returns a function. f takes a number x and returns a number.
H(f, n) = f(f(f(...f(x)...))
          \--- f(n) f's ---/

So H(f(x)=x+1*,5) = f(f(f(f(f(f(x)))))), or x+6.

*λx.(x+1) for computing nerds.

The examples given seem to introduce an additional level of recursion though. I'll analyze it in a sec.

Edit 1: First guess.

Code: Select all

Ok, so the examples are using various subscripted versions of the function H. In this case, H is defined as
H_a(f, n) =    f(f(f(...f(x)...))
            \--- H_(a-1)(f, n) f's---/
Where H_1(f, n) is defined to be f(n).
So H_3(f(x)=x+1, 3) = H_2(f(x)=x+1, 3) f's
H_2(f(x)=x+1, 3) = H_1(f(x)=x+1, 3) f's 
H_1(f(x)=x+1, 3) = f(3) = 4

H_2(f(x)=x+1, 3) = f(f(f(f(3)))) = 7
H_3(f(x)=x+1, 3) = f(f(f(f(f(f(f(3)))))))
So H_3(f(x)=x+1, 3) = 10.

This doesn't seem to match up quite right, though.


FINALLY.

Code: Select all

Calling with f(x), n, and k
{
M_k(x) = M_(k-1)(n) copies of M_(k-1)(x)
M_1(x) = f(x)
return M_k(n)
}


f(x) = x+1, n=2, varying k, we get

M_1(x) = f(x)
At n=2, M_1(2) = f(2) = 2+1 = 3

M_2(x) = M_1(n) copies of M_1(x)
= 3 copies of M_1(x)
= 3 copies of f(x)
= f(f(f(x)))
Or in other words M_2(x) = x+1+1+1 = x+3
At n=2, M_2(2) = 2+3 = 5

M_3(x) = M_2(n) copies of M_2(x)
= 5 copies of M_2(x)=x+3
= M_2(M_2(M_2(M_2(M_2(x)))))
In other words M_3(x) = x+3+3+3+3+3 = x+15
At n = 2, M_3(2) = 2+15 = 17

One further...
M_4(x) = M_3(n) copies of M_3(x)
= 17 copies of M_3(x)=x+15
= x+255
ergo M_4(2) = 257

M_5(x) = 257 copies of x+255
= x+65535
etc.

Final Draft, Pseudocode:

Code: Select all

Exfret(k, f(x), n) =
{
New Function M(k, x) = M(k-1, x) copies of M(k-1, n)      \* In other words M(k-1, M(k-1, M(k-1, ... M(k-1, n)))...) *\
\* Implementation of the above comment requires an auxiliary variable or loop, probably *\
M(1, x) = f(x)
Return M(k, n)
}

Some notes:
It's not 1, 4, 17, it's 1, 5, 17.
257 is a gazillion.
Exfret(f(x)=x+1, n=2, k) seems to grow only exponentially. Looks similar for n>2.

[exfret]

Oh, sorry about not explaining further. I expected that you'd all be confused, but I just wanted to see if it sparked some interest and I didn't want to rewrite my post again (like I said). Now that a further explanation would be for good use, I'll explain it more. ARP, you were on the right track. I'll just explain it from the start:

Given a function f(x) and a number n, (f(x),n) is defined as the "f(n)th level recursion." Now to explain what "f(n)th level recursion" means. Here's a list of some of the first levels of recursion:

First level: f(n) (so if f(n)=1, then you would just stop here and return f(x) (or f(n), I haven't really decided whether my function should return a function or a number).

Second level: f2(n).
f2(x) is defined as f(x) applied to itself f(n) times. For example, if f(x)=2*x and n=1, then f(n)=2, so f2(x)=f(f(x))=2*2*x=4*x, meaning f2(n)=4*1=4. Since f(n)=2 in this case, we would actually stop here and be done because we would have recursed through the f(n)th/second level already.

Third level: ff(n),3(n).
I just put the 3 by there to differentiate it from further levels. (3 for 3rd level of recursion). ff(n),3(x)=ff(n)-1,3(x) applied to itself ff(n)-1,3(n) times. So, if we took f(x)=3*x and n=1, then we would start with finding f(n)=3. f2(x)=f(f(f(x)))=2(2(2(x)))=8*x. f2(n)=8*1=8, so f3(x)=f2(f2(f2(f2(f2(f2(f2(f2(f2(x))))))))=8(8(8(8(8(8(8(8(x))))))))=8^8*x. Also, f3(n)=8^8*1=8^8. Because f(n)=3, f3(x)=ff(n)(x), so we would be done. Also since f(n)=3, we would be done with the third recursion and therefore need not go further in this example.

Fourth level: ff(n),4(n).
ff(n),4(x)=ff(n)-1,4(x) put through the third level recursion. This means that if g1,3(x)=ff(n)-1,4(x), then gf(f(n)-1,4)(n),3(x)=ff(n),4(x).

Fifth level: And so on.
Basically, you just take each new function and send it back through the last level of recursion f(n) times until you get to the f(n)th level recursion.

Because I probably didn't explain this very well, I've attached a picture that hopefully helps.

Edit in response to ARP's edit (which came after I started to post this): You got the first parts right, the 1, 5, 17 (good catch on that 5). After that, though, you go into the fourth level recursion that I didn't write anything about it my very un-detailed post. This recursion causes you to need to square what is returned multiple times, which is why you get about g(g(g(870))) where g=x^(2^x) for f(x)=x+1 and n=3. Also, for the gazillion, you had n=2 and not n=3 anyways. Finally, k equals f(n), if that help clears some stuff about my function up. (In the fourth level recursion, M_k(x) becomes k after each third level recursion, and you do that f(n) times, if that makes any sense. This means that after each third level iteration, the returned function goes through another third-level iteration until it has gone through f(n) iterations..) Hopefully, this helps to un-confuse you.

[robly18]

So basically:

h(f, x, n)

Equals f(x) if f(n) = 1, f(f(x)) if f(n) = 2 and so on and so forth?

Here, I whipped this up in haskell.

Code: Select all

higgs::(Integer -> Integer) -> Integer -> Integer -> Integer
higgs f x n = iterate f x !! (f n)

It doesn't seem to work though, it isn't giving me the results you said it would.

Not sure if you can speak haskell, but here's basically what it does, this is probably where I'm misunderstanding:

It takes a function and two numbers. So f, x, n.

Then it runs f(x) if f(n) = 1, f(f(x)) if f(n) = 2, basically f(n) f's

What am I getting wrong here?

[A Random Player]

So basically:

h(f, x, n)

Equals f(x) if f(n) = 1, f(f(x)) if f(n) = 2 and so on and so forth?

Here, I whipped this up in haskell.

Code: Select all

higgs::(Integer -> Integer) -> Integer -> Integer -> Integer
higgs f x n = iterate f x !! (f n)

It doesn't seem to work though, it isn't giving me the results you said it would.

Not sure if you can speak haskell, but here's basically what it does, this is probably where I'm misunderstanding:

It takes a function and two numbers. So f, x, n.

Then it runs f(x) if f(n) = 1, f(f(x)) if f(n) = 2, basically f(n) f's

What am I getting wrong here?

That looks like my initial guess, which turned out to be wrong. Try implementing my Exfret(f, k, n). Your Higgs(f, x, n) returns a function which is applied to x it seems.

Edit: That paper; how many levels of recursion is that - where is it in the fast growing hierarchy?