Example of functions that grow faster than the exponential functions and/or factorial functions?

Question

What is example of functions that grow faster than the exponential functions and/or factorial functions?

$x\mapsto \exp (\exp (x ) )$ – xavierm02 Nov 28 '13 at 15:14 — xavierm02, Nov 28 '13 at 15:14
How do you do up arrows in LaTeX? – Alec Teal Mar 18 '14 at 00:06 — Alec Teal, Mar 18 '14 at 00:06

score 1 · Accepted Answer · answered Nov 28 '13 at 15:16

1

The busy beaver function can be shown to grow faster than any computable function.

answered Nov 28 '13 at 15:16

Jemmy

1,411

Thanks Jeremy .... Can you tell me proof of that? – JamieLolingner Nov 28 '13 at 15:29
@JamieLolingner I do not know the proof of it's asymptotic domination of computable functions. The fact that it is uncomputable follows from the fact if it were, it would solve the halting problem which is known to be undecidable. A different proof is given in that wiki article. The paper where there is a proof is Radó 1962. – Jemmy Nov 29 '13 at 02:01
I believe this is the paper: http://dl.acm.org/citation.cfm?id=321270 – Jemmy Nov 29 '13 at 02:05

score 1 · Answer 2 · answered Nov 28 '13 at 15:18

1

Here there is an example: $$ x\rightarrow x^x $$

answered Nov 28 '13 at 15:18

Ikki

399

Computist · Answer 3 · 2014-03-18T00:13:15.527

0

Another interesting functions that grow faster than exponential is Ackermann function $\mathrm{A}\left(m, n\right)$. Tetration $x \mapsto {^{n}x} = \underbrace{x^{x^{\cdot^{\cdot^{x}}}}}_n$ is a special case of Ackermann function. Tetration is to exponentiation what exponentiation is to multiplication. I.e. iterated exponentiation leads to tetration. A fun fact about tetration: $^44 > $ googolplex.

edited Mar 18 '14 at 00:13

answered Mar 17 '14 at 23:53

Computist

525

Example of functions that grow faster than the exponential functions and/or factorial functions?

3 Answers3

Linked