Title: Theory / Unimportant / CS / Fundamental / Algorithmic randomness and complexity / Intro

Definition: \(A\Delta B\) is finite
Page: 3
Chapter: 1
Variables: \(A,B\) sets
Notation: \(A=^*B\)

Definition: The string \(A(0)\dots A(n-1)\)
Page: 3
Chapter: 1
Variables: \(A\subseteq \mathbb N\)
Notation: \(A\rightharpoonup n\)

Definition: 1 if \(i\in A\),
\(0\) otherwise
Page: 2
Chapter: 1
Variables: \(A\subseteq\mathbb N\),
\(i\in\mathbb N\)
Notation: \(A(i)\)

Question: \(A\) as a binary sequence
Answer: \(A(0)A(1)\dots\)
Page: 2
Chapter: 1
Variables: \(A\subseteq\mathbb N\),

Question: \(A\) as a real is
Answer: the real \(0.A(0)A(1)\dots\)
Page: 2
Chapter: 1
Variables: \(A\subseteq\mathbb N\),

Name: The \(e\)-th column of \(A\)
Definition: The set of \(\langle e,n\rangle\) such that \(\langle e,n\rangle\in A\)
Page: 2
Chapter: 1
Variables: \(A\) a set of pairs
\(e\in\mathbb N\)
Notation: \(A^{[e]}\)

Name: The empty string
Page: 2
Chapter: 1
Notation: \(\lambda\)

Definition: The concatenation of strings \(\sigma\) and \(\tau\)
Page: 2
Chapter: 1
Variables: \(\sigma\) a finite string,
\(\tau\) a string
Context: Information Theory
Notation: \(\sigma\frown\tau\)

Name: The length-lexicographic ordering on \(2^{<\omega}\)
Definition: The order with \(\sigma<\tau\) if \(|\sigma|<|\tau|\) or \(|\sigma|=|\tau|\) and \(\sigma(n)=0\) for the least \(n\) with \(\sigma(n)\ne\tau(n)\)
Page: 2
Chapter: 1
Notation: \(<_L\)

Definition: The set of infinite word with prefix \(\sigma\)
Page: 4
Chapter: 1
Section: 2
Variables: \(\sigma\) a finite word.
Notation: [$]\llbracket\sigma\rrbracket[/$]
Typ: Clopen sets

Name: The set generated by \(A\)
Definition: [$]\bigcup_{\sigma\in A}\llbracket\sigma\rrbracket[/$]
Page: 4
Chapter: 1
Section: 2
Variables: \(A\) a set of finite strings
Notation: [$]\llbracket A\rrbracket[/$]

Name: A generator of \(A\)
Definition: A set \(B\) such that [$]\bigcup_{\sigma\in B}\llbracket\sigma\rrbracket=A[/$]
Page: 4
Chapter: 1
Section: 2
Variables: \(A\) a set of infinite strings
Typ: A set of finite strings

Name: The topology of \(2^{<\omega}\)
Definition: The topology with subbasic open sets [$]\llbracket\sigma\rrbracket[/$] for \(\sigma\in 2^{<\omega}\)
Page: 4
Chapter: 1
Section: 2

Name: A cover of \(C\)
Definition: A set \(A\) such that [$]C\subseteq\llbracket A\rrbracket[/$]
Page: 5
Chapter: 1
Section: 2
Variables: \(C\subseteq 2^\omega\)

Name: The outer measure of \(C\)
Definition: The least \(\sum_{\sigma\in A}2^{-\sigma}\) for \(A\) a countable cover of \(C\)
Page: 5
Chapter: 1
Section: 2
Variables: \(C\subseteq 2^\omega\)
Notation: \(\mu^*(C)\)
French: Mesure extérieure de \(C\)

Name: The inner measure of \(C\)
Definition: \(1-\mu^*(\bar C)\)
Page: 5
Chapter: 1
Section: 2
Variables: \(C\subseteq 2^\omega\)
Notation: \(\mu_*(C)\)

Name: A measurable set of \(2^\omega\)
Definition: A set \(C\subseteq 2^\omega\) such that \(\mu^*(C)=\mu_*(C)\)
Page: 5
Chapter: 1
Section: 2

Name: The measure of \(C\)
Definition: \(\mu^*(C)\)
Page: 5
Chapter: 1
Section: 2
Variables: \(C\subseteq 2^\omega\)
Assuming: \(C\) measurable