Posts

Let $U$ be a universal prefix-free Turing machine. Given $X\subset\omega$, let $\Omega[X]=\sum_{U(\sigma)\downarrow\in X}2^{-|\sigma|}$. The following are straight forward observations: $\{\Omega[X]:X\subset\omega\}=[0,\Omega]$. For each $n$ there is a $\Delta^0_{n+1}$ set $X$ such that $A[X]$ is $n$-random.

Definitions Let $A\subset\omega$. $A$ is $n$-r.e. if there is a computable function $f(a,s)$ such that for all $a\in\omega$, $f(a,0)=0$, $|\{s:f(a,s)\neq f(a,s+1)\}|\leq n$, $\lim_{s\to\infty}f(a,s)=\chi_A(a)$. Note that $1$-r.e. sets are just r.e. sets; $2$-r.

The game Given parameters $(l,c,q)$. For convenience you can assume that $l$ is very large, $c=4$ and $q=1/2$. Consider the following game between a coder and a destroyer. The coder has spaces $f(\tau)$ indexed by $\tau\in 2^{\leq l}$ (all binary strings of length $\leq l$ which are called codes).

Definitions Let $K(\cdot)$ denote the Komogorov complexity. $2^{<\omega}$ is the set of all binary strings of finite length. $\log$ is the logarithm with base $2$. For $\sigma\in 2^{<\omega}$, an $(n,c)$-cover of $\sigma$ is a finite set of strings $A_\sigma$ such that

The game Given $k$, consider the following game of $2$ players. In each round, player 1 chooses a set $R$ of $k$ natural numbers that he has not yet chosen earlier player 2 chooses an even number $n\in[\min R,\max R]$, that he has not yet chosen earlier If player 2 is unable to make a move at some round, he loses the game; otherwise he wins.

Definitions Given $n$, let $2^n$ be the set of all $n$-bits binary strings, and $[n]=\{0,1,\cdots,n-1\}$. Given a class $\mathcal{C}\subset 2^n$. The VC dimension, $\text{VCD}(\mathcal{C})$ is the maximum $|A|$ such that each binary string on $A$ can be extended to a member in $\mathcal{C}$, i.