« first day (276 days earlier)      last day (123 days later) » 

1:32 AM
@Secret hi
A: BigNum Bakeoff Reboot

Leaky NunPython 3, ~ fε0(999) N=9**9**9 def f(a,n): if a[0]==[]:return a[1:] if a[0][0]==[]:return[a[0][1:]]*n+a[1:] return [f(a[0],n)]+a[1:] a=eval("["*N+"]"*N) n=2 while a:a=f(a,n);n+=1 print(n) Try it online!

just thought that you might be interested @Secret
hmm... I'll have a look after I deal with that irrational cover question...
Meanwhile I need to figure out how to make Asaf more weird, cause past experience told me that I often have trouble explaining what I am doing to non weird people
I don't understand what you are doing, or why you expect the limit to be an open set. But in any case, writing $\lim_{k\to\aleph_0}$ is making me cringe. — Asaf Karagila 7 hours ago
1:57 AM
Oh hi
@Secret haha
In any case, I don't like writing $\to \infty$ unless the set of indices is only linearly ordered. If I can well order it, I will make sure to make it clear that no one dared to count to uncountable
:P Use something like sup{... : k<...}
2:13 AM
@SimplyBeautifulArt I suspect the more general case will be: let $f$ be any nondecreasing function of the ordinals. Then an OCF including $f$ and all functions that strictly grows slower than $f$ will produce everything before $f^2(n)$ and $\psi(n) \geq \sup (g < f : g^2(n))$
e.g. $2,k+2,k^2,k^k, \epsilon_{\epsilon_{k}}, \phi (\phi (n,k)), \Gamma_{\Gamma_k}...$
and I suspect that will also work even if $f$ is $\alpha$-uncomputable
however, unless $f$ has a growth rate comparable to $x \to \omega_1 + x$, none of these OCFs can reach $\omega_1$
I have to head to bed
Night man
2 days ago, by Simply Beautiful Art
$$[x,y,z] = \begin{cases} x+1,& y\cdot z=0\\ \sup\{[[x,y,a],b,x]: a<z, b<y\} ,&\rm else\end{cases}$$
2:36 AM
[0,1,0] = ?
[0,1,0] = 1
[n,0,0] = n+1
@SimplyBeautifulArt pin this?
2:58 AM
so many notations seemed to evaluate to the same number
so uh, seems like the slowest growing function ever?
3:02 AM
the strength is in the middle number :)
not the first number
Error: Too many nested arguments, program will terminate
1 hour later…
4:19 AM
Thinking about an increasing function defined as follows:
$\sup(n < \omega : n)$
$\sup (n_1 < \omega : n_1)$
$\sup (n_2 < \omega : \sup (n_1 < \omega : n_1)+n_2)$
$\sup(n_3 : < \omega : \sup (n_2 < \omega : \sup (n_1 < \omega : n_1)+n_2)n_3)$
$\sup (n_4 < \omega : \varphi (n_4,\sup(n_3 : < \omega : \sup (n_2 < \omega : \sup (n_1 < \omega : n_1)+n_2)n_3)))$
after this point, I am going to omit all $n_i < \omega$ and they will be implied by the nesting of the sups
and therefore rewriting the above in short hand gives:
$\sup (n_1)$
$\sup([\varphi(\cdot ,\sup(\varphi(,\sup(\sup(n_1)+n_2)n_3))] \circ^{n_5} \sup(\varphi(n_4,\sup(\sup(n_1)+n_2)n_3)))$
$\sup (\varphi \binom {n_6}{\sup([\varphi(\cdot ,\sup(\varphi(,\sup(\sup(n_1)+n_2)n_3))] \circ^{n_5} \sup(\varphi(n_4,\sup(\sup(n_1)+n_2)n_3)))})$
$\sup ([\varphi \binom{1}{\cdot}]\circ^{n_7} \sup(\varphi \binom {n_6}{\sup([\varphi(\cdot ,\sup(\varphi(,\sup(\sup(n_1)+n_2)n_3))] \circ^{n_5} \sup(\varphi(n_4,\sup(\sup(n_1)+n_2)n_3)))}))$
$\sup (\varphi_{n_8}\binom{1}{\sup ([\varphi \binom{1}{\cdot}]\circ^{n_7} \sup(\varphi \binom {n_6}{\sup([\varphi(\cdot ,\sup(\varphi(,\sup(\sup(n_1)+n_2)n_3))] \circ^{n_5} \sup(\varphi(n_4,\sup(\sup(n_1)+n_2)n_3)))}))}))$
$\sup (\varphi_{\cdot}\binom{1}{\sup (\varphi_{n_8}\binom{1}{\sup ([\varphi \binom{1}{\cdot}]\circ^{n_7} \sup(\varphi \binom {n_6}{\sup([\varphi(\cdot ,\sup(\varphi(,\sup(\sup(n_1)+n_2)n_3))] \circ^{n_5} \sup(\varphi(n_4,\sup(\sup(n_1)+n_2)n_3)))}))}))}) \circ^{n_9} \sup (\varphi_{n_8}\binom{1}{\sup ([\varphi \binom{1}{\cdot}]\circ^{n_7} \sup(\varphi \binom {n_6}{\sup([\varphi(\cdot ,\sup(\varphi(,\sup(\sup(n_1)+n_2)n_3))] \circ^{n_5} \sup(\varphi(n_4,\sup(\sup(n_1)+n_2)n_3)))}))}))$
which in $\psi$ OCF reads:
$0, \omega, \omega 2, \omega^2, \psi (\Omega^{\omega} + \omega^2), \psi (\Omega^{\Omega} + \psi (\Omega^{\omega} + \omega^2)), \psi (\Omega^{\Omega^{\omega}}+\psi (\Omega^{\Omega} + \psi (\Omega^{\omega} + \omega^2))), \psi (\Omega^{\Omega^{\Omega}}+\psi (\Omega^{\Omega^{\omega}}+\psi (\Omega^{\Omega} + \psi (\Omega^{\omega} + \omega^2))), $
5:05 AM
rip latex
actually, now that I get a better feel of the pattern, I can rewrite this mess more concisely in terms of $\psi$
The function grows like this:
$0,\omega,\omega 2, \omega^2, \psi (\Omega + \omega^2), \psi (\Omega^{\omega} + \psi (\Omega + \omega^2)), \psi (\Omega^{\Omega^{\omega}}+ \psi (\Omega^{\omega} + \psi (\Omega + \omega^2))$ and so on...
Another function I am thinking consists of only two things:
$f(n) = \begin{cases} n+1, \text{n is a sup or n is 0}\\ \sup (something (n)), \text{otherwise}\end{cases}$
$f(1) = \sup (f(0) n) = \omega$
$f(2) = \omega +1$
$f(3) = \sup (\omega^{\cdot} \circ^n f(2)) = \sup (\omega,\omega^{\omega+1},\omega^{\omega^{\omega +1}},...) = \epsilon_0 \prod_{n < \omega}{}^{n}\omega$
$f(4) = f(3) + 1$
$f(5) = \sup (\varphi (n,f(4))) = \varphi (\omega, 0) = \psi (\Omega^{\omega})$
$f(7) = \sup (\varphi (\cdot, f(6)) \circ^n f(6)) = \Gamma_0 = \varphi (1,0,0) = \psi (\Omega^{\Omega})$
$f(9) = \sup (\varphi \binom{n}{f(8)}) = \varphi \binom{\omega}{1} = SVO = \psi (\Omega^{\Omega^{\omega}})$
$f(11) = \sup (\varphi \binom{1}{\cdot} \circ f(10)) = LVO= \psi (\Omega^{\Omega^{\Omega}})$
$f(13) = \sup (\varphi_{n}\binom{1}{f(12)}) = LVO(\omega) = \psi (\Omega^{\Omega^{\Omega^{\omega}}})$
ok this is TOO SLOW
$f(m) = \sup (g_{m^+}(n))+1$
where $g_{m^+}> g_m$ and $g_m$ picks the index that gives the faster growth and $g_0=0$
$f(0) = 1$
$f(1) = \sup (\omega^{\cdot} \circ^{n} f(0)) + 1 =\psi (0) + 1$
$f(2) = \sup (\varphi (\cdot,f(1)) \circ^n f(1) + 1) = \psi (\Omega^{\Omega}) + 1$
$f(3) = \sup \varphi_{\cdot} \binom{1}{f(2)} \circ^n f(2) = \psi ({}^4\Omega) +1$
6:04 AM
$f(4) = \sup (\psi ({}^{f(3)+n}\Omega)) = \psi ({}^{f(3)+\omega}\Omega) + 1 = \psi' (\psi ({}^4\Omega)+1)$
$f(5) = \sup (\psi' ({}^{f(4)+n}\Omega) = \psi'({}^{f(4)+\omega}\Omega)$
$f(6) = \sup (\psi^{'(f(5)+n)}(\Omega)) = \psi^{'(f(5)+\omega)} (\Omega)$
However, what I want is the following:
$...\sup g_2(\sup (g_1(\sup(g_0(0))+1)+1)+1)$
or in other words: $f(\omega)$
The resulting ordinal should be computable, but very huge
6:20 AM
well every ordinal is very huge
We can prove $\sup (f(n))$ is computable by induction since for all $n < \omega$, $f(n)$ is a finite sequence of computable function and successors, thus the result is computable. Then for $\omega = \sup (n)$, since all finite cases are computable, and the $\omega$th case is just a union of them all, it follows $f(\omega)$ should be computable, even if we don't have a way to write it down
6:37 AM
I just checked transfinite induction again...
The limit case need to be proved separately
So checking again:
$f(\omega) = \sup (f(n)) = (\prod_{n < \omega} \sup(g_n(\cdot + 1)) \circ ) 0$
While each $g_n$ is computable hence terminate in finite steps, the whole sequence is countable, thus by definition is the same as not terminating. Therefore $f(\omega)$ will run forever unless given countable steps. Thus $f(\omega)$ is uncomputable
Which means...:
$$f(\omega) = \omega_1^{CK}$$
looks like we just found a function that can shoot past that $\omega_1^{CK}$ barrier
After this point, things get a bit vague...
$f(\omega + 1) = \sup (g_{\omega} \omega_1^{CK}) + 1$
Two obvious choice for $g_{\omega}$ will be:
$g_{\omega} : \alpha \to \omega_{\alpha}^{CK}$
$g_{\omega} : \alpha \to \omega_{\alpha^{+}}^{CK}$
But the top one seems more suitable as it grows faster and $g_{n}$ is required to be a function that grows faster than the one in the previous stage
In fact, even a tower of $\omega_{\cdot}^{CK}$ is not fast enough,as after finite number of steps, it will get stuck
To be fast enough so that it does not get stuck in finite number of steps, we need something like $f(\omega_1^{CK})$. This is well defined as having $\omega_1^{CK}$, we can collapse it down to obtain all the countable ordinals (which will be given by some finite sequence of computable functions)
($+,\times, \wedge$) choose $\wedge$
because $\times = \sum +$ while $\wedge = \prod \cdots \prod (\sum +)$
Ah I see now...
The reason I can get to $\omega_1^{CK}$ despite using only computable functions is because it is the function hierarchy $\{g_0,g_1,g_2,..\}$ is uncomputable.
Suppose we instead define the hierarchy to be one which adds two levels of $\Omega$ into the $\psi$ for each n, then the nth stage will be the notation $\psi ({}^{n}\Omega)$ which is computable and thus supremum can easily bring it to the $\omega$th level with the notation $\psi ({}^{\omega}\Omega) = BHO$ and be computable (thus never reaching $\omega_1^{CK})$
Q: Sequence for which no closed form can exist

stefanI was wondering whether there exists a (computable) sequence of numbers, for which it can be proven that no closed form can exist. Edit: By closed form I mean an expression involving only a constant number of elementary functions. So something like a sum can not occur in the expression.

Q: How to prove that a sequence with recurrence relation has no closed form expression?

ColliotIt is always easy to forge recurrence relations. E.g. $$a_{n+1}=2a_n+\dfrac{1}{a_n}, a_0=1$$ But it is always hard to find the general closed form expression. And it is even harder to prove that there is no such expression. Another example is here. And I highly suspect sequences like $$a_n = \...

so, for the case of sequences, it is in general not known whether there always exists a theory that can check if a closed form (i.e. there exists a computable function that can enumerate all the elements of the sequence) exists
This means, it is not known whether we can construct $\{g_{\alpha}\}$ in such a way that it has no closed form as a function of $\alpha$, but nevertheless, computable
15 hours later…
10:49 PM
@SimplyBeautifulArt Hiya
I predict that you will respond with "heyo"
@Nilknarf hi
welcome to the wonderful world of ordinals... they mesmerize me every second
Have you played a game of "big numbers" with @Simply yet?
11:41 PM
Hey @Nilknarf
@Secret Input $\omega$ into:
2 days ago, by Simply Beautiful Art
$$[x,y,z] = \begin{cases} x+1,& y\cdot z=0\\ \sup\{[[x,y,a],b,x]: a<z, b<y\} ,&\rm else\end{cases}$$
@Nilknarf I found a game involving big numbers...
11:55 PM
@SimplyBeautifulArt are you going to get everyone addicted :P
@Nilknarf what is that game?

« first day (276 days earlier)      last day (123 days later) »