All posts by admin

Documentation for the structure function calculator

$h^*_x(m)=q$ means that in order to have at most $\text{(alphabet size)}^{m}$ accepting paths of length $n=|x|$, we need $q$ states.

Rules

  • We are considering single-run complexity where the automaton must proceed to a fresh state except
    that there is one state that may be repeated.
  • Thus: the automaton need not be deterministic; a run may be abandoned midway;
  • the run can start before we get to the run-state;
  • runs that are of less than maximal length of their “flavor” (such as 322023 which is shorter than 20322023 in the given example) do count (they are in any case insignificant for statistical model selection purposes); runs of less than maximal length for their size-of-flavor (such as 2311322 for size 3) do count; in general any subrun of a run counts.

The provided example comes from a series of codons in part of a messenger RNA (mRNA) molecule whose genetic code is $$AUG\, ACG\, GAG\, CUU\, CGG\, AGC\, UAG$$
encoded as
$$x=012032202311322023102$$
which has length $n=21$ and is a string from the alphabet $\{0,1,2,3\}$ which has size $b=4$. There is a run of length $r=8$ from the subalphabet $j=\{0,2,3\}$, namely an occurrence of 20322023. The corresponding automaton has $q=n+1-r=21+1-8=14$ many states and accepts $|j|^r=3^8$ many strings of length $n$. When $3^8\le b^m$ we can then assert that $h^*(m)\le q$. Thus
$$
6561 = 3^8\le 4^m
$$
Note
$$
(4^2,4^3,4^4,4^5,4^6,4^7)= (16, 64, 256, 1024, 4096, 16384)
$$
So $h^*(7)\le 14$.

The longest unary ($|j|=1$) run is of length $r=2$. This gives $q=n+1-r=20$ and only one string is accepted so $h^*(m)\le 20$ for all $m$.

The longest binary ($|j|=2$) run is of length $r=4$. This gives $q=n+1-r=18$ and when $2^4\le 4^m$ (i.e., $2\le m$), we can assert $h^*(m)\le q$. So $h^*(2)\le 18$.

What can we say about $h^*(6)$? $4^6=4096$ and
$(3^4,3^5,3^6,3^7,3^8)=(81, 243, 729, 2187, 6561)$. So
$$3^8\le 4^7\Longrightarrow h^*(7)\le 22-8=14$$
$$3^7=2187\le 4^6=4096\Longrightarrow h^*(6)\le 22-7=15$$
$$3^6= 729\le 4^5 = 1024\Longrightarrow h^*(5)\le 22-6=16$$
$$3^5= 243\le 4^4 = 256\Longrightarrow h^*(4)\le 22-5=17$$
$$3^4= 81 \le 4^4 = 256(\Longrightarrow h^*(4)\le 22-4=18)$$
$$3^3= 27\le 4^3 = 64\Longrightarrow h^*(3)\le 22-3=19$$
So we cannot obtain $h^*(3)\le 18$ by a partial ternary run, but we can obtain it because $h^*(2)\le 18$ because of the binary run.

Note
$$3^r\le 4^1\Longrightarrow r\le 1$$
$$2^r\le 4^1\Longrightarrow r\le 2$$
So a binary run of length 2 narrows it down to $4^1$.
And this corresponds to
$$q=n+1-r=21+1-2=20,$$
so $h^*(1)\le 20$.

Some examples of “inversion” (different explanation for the string depending on whether the subalphabet, or the size of the subalphabet, is taken into account):
21112
212220
020001
211120
1333030
32322131
201011311
1010113303
01210312303

Complexity Option Game High Score Table

Complexity Option Game

Highest individual payoffs
Name Payoff
Bjørn JavaScript $11
Rupert $11
Rutger $11
Rupert $11
$3
$3
Steven Gum $3
$2
$2
$2
$2
$2
Jake $2
Thorsten $2
Rutger $2
$2
Jake $2
Jake $2
Nina $2
$2
Alv $2
$2
$2
$2
$2
$1
$1
David $1
Gabriele acquagassata $1
Gabriele acquagassata $1
$1
$1
$1
James $1
$1
$1
Saurav $1
x $1
$1
ian2 $1
God $1
Lisa $1
$1
$1
Lucas $1
$1
$1
$1
Gabriele acquagassata $1
$1
$1
Morten $1
$1
$1
$1
$1
Znevhf $1
Znevhf $1
x $1
x $1
$1
$1
$1
$1
$1
$1
$1
$1
$1
$1
$1
$1
$1
$1
$1
$1
$1
nate $1
nate $1
$1
$1
Thorsten $1
nate $1
Thorsten $1
$1
Yoshiki $1
$1
Jesus CHrist $1
Jesus CHrist $1
$1
$1
$1
$1
Jake $1
Jake $1
Jake $1
Jake $1
Jake $1
Jake $1
J $1
Jake $1
Jake $1
Jake $1
Jake $1
Jake $1
axs34 $1
$1
bu $1
Rutger $1
Jake $1
Jake $1
Jake $1
moo $1
Pat $1
dev $1
$1
$1
$1
Jake $1
Soumik $1
axs34 $1
$1
Mary $1
Mary $1
Daniel $1
$1
Jake $1
Jake $1
Godot $1
Dan $1
$1
$1
$1
3 $1
$1
$1
$1
Dan $1
$1
$1
Nina $1
Matthew $1
$1
$1
Gev $0
Znevhf $0
Gev $0
Herr God $0
Znevhf $0
$0
H $0
$0
$0
$0
$0
Znevhf $0
$0
Znevhf $0
Amir $0
x $0
$0
$0
Thorsten $0
Yoshiki $0
Yoshiki $0
$0
$0
Pat $0
$0
$0
Gev $0
Doralisa $0
Doralisa $0
Gev $0
$0
Gev $0
Yoshiki $0
$0
$0
$0
$0
$0
Torsten $0
$0
$0
$0
$0
$0
$0
$0
$0
$0
$0
Buddenbroek $0
$0
$0
$0
Catiline $0
$0
$0
$0
Nagel $0
$0
$0
$0
$0
$0
J $0
$0
$0
$0
$0
J $0
Math $0
Jesus CHrist $0
$0
$0
Thorsten $0
Math $0
$0
$0
$0
$0
$0
$0
Thorsten $0
$0
A name $0
$0
$0
$0
$0
$0
$0
$0
$0
$0
$0
Chris $0
$0
$0
$0
Nina $0
Nina $0
$0
$0
$0
$0
Gabriele acquagassata $0
$0
$0
$0
$0
$0
Lisa $0
TT $0
ian2 $0
$0
$0
$0
Lucas $0
Chris $0
$0
Daniel $0
$0
axs34 $0
axs34 $0
? $0
Jake $0
Jake $0
mra $0
Jake $0
? $0
Jake $0
dev $0
? $0
Thirty Fodders $0
S. $0
Jake $0
Jake $0
$0
$0
$0
bu $0
Dan $0
dfsg $0
Godot $0
Jake $0
Jake $0
Jake $0
Jake $0
Jake $0
Jake $0
Jake $0
lol $0
Jehan $0
$0
$0
$0
$0
$0
benjamin $0
$0
$0
danish $0
i $0
i $0
test $0
$0
$0
$0
$0
$0
$0
$0
$0
$0
$0
$0
$0
Rachel $0
Ulven! (you know my name) $0
$0
Robert $0
$0
$0
hi $0
ram $0
$0
$0
Kellie $0
$0
$0
$0
Neeraj $0
$0
$0
$0
$0
lol $0
$0
$0
$0
$0
nate $0
nate $0
Kellie $0
$0
$0
$0
$0
$0
$0
$0
$0
$0
$0
nate $0
nate $0
nate $0
Kellie $0
$0

Here are the players' total earnings out of the market total of $208.

Name Earnings
Jake $23
Rupert $22
Rutger $14
Bjørn JavaScript $11
Thorsten $4
Steven Gum $3
Nina $3
Gabriele acquagassata $3
x $3
nate $3
Alv $2
Znevhf $2
Jesus CHrist $2
axs34 $2
Mary $2
Dan $2
David $1
James $1
Saurav $1
ian2 $1
God $1
Lisa $1
Lucas $1
Morten $1
Yoshiki $1
J $1
bu $1
moo $1
Pat $1
dev $1
Soumik $1
Daniel $1
Godot $1
3 $1
Matthew $1
Note: the highest payoff theoretically possible is currently $11. For comparison, Pakravan and Saadat calculated the following option prices:
Option prices
Expiry Price
0 or 1 $0
2 or 3 $0.5
4 or 5 $0.75
6 or 7 $0.875
8 or 9 $1.070313
10 or 11 $1.191406
12 or 13 $1.236328
14 or 15 $?
16 or 17 $?
18 or 19 $?
20 or 21 $?
22 or 23 $?
Infinity $Infinity?

The noncentral $t$ distribution is an elementary function relative to erf

In this note we show that for each fixed number of degrees of freedom $\nu$, the noncentral $t$ distribution with noncentrality parameter (= the mean of the numerator) $\mu$ is an elementary function relative to erf.

The pdf is, per Wikipedia,
$$
f(x) =\frac{\nu^{\frac{\nu}{2}} \exp\left (-\frac{\nu\mu^2}{2(x^2+\nu)} \right )}{\sqrt{\pi}\Gamma(\frac{\nu}{2})2^{\frac{\nu-1}{2}}(x^2+\nu)^{\frac{\nu+1}{2}}} \int_0^\infty y^\nu\exp\left (-\frac{1}{2}\left(y-\frac{\mu x}{\sqrt{x^2+\nu}}\right)^2\right ) dy.$$
The non-elementary part is the integral
$$
\int_0^\infty y^\nu\exp\left (-\frac{1}{2}\left(y-\frac{\mu x}{\sqrt{x^2+\nu}}\right)^2\right ) dy = g\left(\frac{\mu x}{\sqrt{x^2+\nu}}\right)
$$
where
$$
g(a)=\int_0^\infty y^\nu\exp\left (-\frac{1}{2}\left(y-a\right)^2\right ) dy.
$$
We claim that $g$ is elementary relative to the error function erf, or equivalently relative to the standard normal cdf $\Phi$.

Namely, by change of variable and the binomial theorem,
$$
g(a)=\sum_{k=0}^\nu a^{\nu-k} {\nu\choose k} \alpha_k
$$
where
$$
\alpha_k = \int_a^\infty x^k e^{-x^2/2}\,dx
$$
Next using $u=x^{k-1}$, $dv=x e^{-x^2/2}\,dx$ and integration by parts, we can show a recurrence relation for $\alpha_k$:
$$\alpha_k = a^{k-1}e^{-a^2/2} + (k-1)\alpha_{k-2}$$
Finally, $\alpha_0=\sqrt{2\pi}(1-\Phi(a))$ and $\alpha_1 = e^{-a^2/2}$, and we are done.

Interactions between computability, universal algebra, and group theory

All talks will be in Keller Hall 314.

Scientific program

Thursday February 12

  • 10:30-11:20am Olga Kharlampovich (CUNY — Hunter College): Elementary classification questions for groups and algebras I: Groups.
  • 11:30am-1:20pm: CASUAL LUNCH. Suggestion: Manoa Gardens
  • 1:30-2:20pm Free discussion

Friday February 13

  • 9:30-10:20am Bakhadyr Khoussainov (University of Auckland):A quest for algorithmically random algebraic structures
  • 11:30-12:20pm Alexei Miasnikov (Stevens Institute of Technology): Elementary classification questions for groups and algebras II: Associative and Lie algebras.
  • 12:30-1:20pm BRIEF LUNCH. Suggestion: Sustainability Courtyard
  • 1:30-2:20pm Paul Kim Long V. Nguyen (University of Hawaii — Leeward Community College): $\Sigma^0_3$-completeness of subdirect irreducibility
Abstract (Kharlampovich and Miasnikov)

We consider some fundamental model-theoretic questions that can be asked about a given algebraic structure (a group, a ring, etc.), or a class of structures, to understand its principal algebraic and logical properties. These Tarski type questions include: elementary classification and decidability of the first-order theory.

In the case of free groups we proved that two non-abelian free groups of different ranks are elementarily equivalent, classified finitely generated groups elementarily equivalent to a finitely generated free group (also done by Sela) and proved decidability of the first-order theory.

We describe partial solutions to Tarski’s problems in the class of free associative and Lie algebras of finite rank and some open problems. In particular, we will show that unlike free groups, two free associative algebras of finite rank over the same field are elementarily equivalent if and only if they are isomorphic. Two free associative algebras of finite rank over different infinite fields are elementarily equivalent if and only if the fields are equivalent in the weak second order logic, and the ranks are the same. We will also show that for an infinite field the theory of a free associative algebra is undecidable.

Things to do in Honolulu

Pow!Wow! art festival

Travel: parking, getting to campus from your hotel, and beaches.

High Score Table

Complexity Guessing Game

The top spots are inhabitated by computability theorists such as Mushfeq Khan, Rutger Kuyper, Rupert Hölzl, Greg Igusa.

Rank Name # times correct ($a$) # times wrong ($b$) Bayesian proportion ($\frac{a+100}{a+b+200}$)
1 qefhsum 1000 0 0.917
2 Rutger 500 0 0.857
3 Rupert 333 3 0.808
4 Greg 105 39 0.596
5 Patrick Chambers 121 57 0.585
6 44 19 0 0.543
7 Peter Hengyao Han 25 7 0.539
8 David 25 13 0.525
9 Emma 10 1 0.521
10 domotorp 14 8 0.514
11 2 9 4 0.512
Tone 6 1 0.512
13 Bert 7 3 0.51
Alexey 6 2 0.51
Kayleigh Hyde 4 0 0.51
0edk 4 0 0.51
17 adam 7 4 0.507
3 6 3 0.507
amir 4 1 0.507
12 3 0 0.507
as 3 0 0.507
Tone 3 0 0.507
23 Jack 17 14 0.506
24 Noah 3 1 0.505
abelard 3 1 0.505
Znevhf 3 1 0.505
reza 2 0 0.505
Cameron 2 0 0.505
niels 2 0 0.505
d-wax 2 0 0.505
9 2 0 0.505
Evgeny 2 0 0.505
Erin 2 0 0.505
charli 2 0 0.505
Bjorn 2 0 0.505
Bradley Valiente 2 0 0.505
37 Kevin Buzzard 9 8 0.502
James Myer 6 5 0.502
Binh 5 4 0.502
Tyler Iyomasa 4 3 0.502
Lionel 4 3 0.502
Abdel 4 3 0.502
Sonia 2 1 0.502
Pedro 2 1 0.502
x 2 1 0.502
1 2 1 0.502
Victor 2 1 0.502
Jesse 1 0 0.502
Jeff 1 0 0.502
Damien 1 0 0.502
Stu 1 0 0.502
heptagon 1 0 0.502
Yarramsetti Durga Sai Ratna Kumar 1 0 0.502
han 1 0 0.502
sajal 1 0 0.502
xxxxxxxxxxxxx 1 0 0.502
tr 1 0 0.502
tes 1 0 0.502
ewrerewrw 1 0 0.502
hello 1 0 0.502
Uncultured Tramp 1 0 0.502
popo 1 0 0.502
thomas 1 0 0.502
achraf 1 0 0.502
NICOLAS BAEZ 1 0 0.502
Jane 1 0 0.502
orlp 1 0 0.502
Onkar 1 0 0.502
asd 1 0 0.502
pincopallino 1 0 0.502
;pl\'p;l\'p,l 1 0 0.502
aaaa 1 0 0.502
Sander 1 0 0.502
antoine 1 0 0.502
juan 1 0 0.502
Rune 1 0 0.502
fiona 1 0 0.502
rajat 1 0 0.502
mehdi 1 0 0.502
Zain 1 0 0.502
sdv 1 0 0.502
sdfa 1 0 0.502
Шш 1 0 0.502
Nash 1 0 0.502
swathi 1 0 0.502
Morrison 1 0 0.502
Magnus Talberg 1 0 0.502
Rune 1 0 0.502
jass 1 0 0.502
Deepal 1 0 0.502
hgfhdgf 1 0 0.502
efte 1 0 0.502
asdassdasdsad 1 0 0.502
cc 1 0 0.502
pete 1 0 0.502
Michal 1 0 0.502
adelmo 1 0 0.502
Paul 1 0 0.502
gfdsgfsdf 1 0 0.502
gf 1 0 0.502
jh 1 0 0.502
Igor 1 0 0.502
Matt 1 0 0.502
BALAJI 1 0 0.502
lk 1 0 0.502
lmkn 1 0 0.502
j; 1 0 0.502
Iyua Yakobu 1 0 0.502
wdwef 1 0 0.502
XYZ 1 0 0.502
8 1 0 0.502
10001111 1 0 0.502
11 1 0 0.502
kdjfkdkkkf 1 0 0.502
l 1 0 0.502

Note: Entries under nondescript and extremely short names, such as "n", may be deleted periodically.