Title: Theory / Unimportant / CS / Fundamental / Algorithmic randomness and complexity / I - Background / 2 - Computability
On every note of this deck, unless a note says otherwise:
Chapter: 2

Definition: The configuration of \(M\) after \(n\) step
Page: 9
Section: 1
Variables: \(M\) a computation,
\(n\in\mathbb N\)
Notation: \(M[n]\)

Definition: \(M\) halts on input \(\sigma\)
Page: 9
Section: 1
Variables: \(M\) a computation,
\(\sigma\) a string
Notation: \(M(\sigma)\downarrow\)

Definition: \(M\) does not halt on input \(\sigma\)
Page: 9
Section: 1
Variables: \(M\) a computation,
\(\sigma\) a string
Notation: \(M(\sigma)\uparrow\)

Name: A uniformly computable families of function
Definition: A sequence \((f_i)_{i\in\mathbb N}\) such that there is a computable function \(f\) such that \(f_n(x)=f(n,x)\)
Page: 11
Section: 1

Name: A uniformly partial computable families of function
Definition: A sequence \((f_i)_{i\in\mathbb N}\) such that there is a partial computable function \(f\) such that \(f_n(x)=f(n,x)\)
Page: 11
Section: 1

Name: A computably enumerable set
Definition: A set \(\text{dom}(\Phi_e)\) for some \(e\).
Page: 11
Abbreviation: A c.e. set

Name: Enumeration theorem
Definition: There exists a list containing each partial computable functions.
Page: 9
Context: Computability
Kind: Prop
Extra: smn ?

Definition: A list containing each partial computable functions.
Page: 9
Notation: \((\Phi_i)_{i\in\mathbb N}\)
Kind: Prop

Name: A universal function
Definition: A partial computable function \(f\) with two arguments such that \(f(x,y)=\Phi_x(y)\)
Page: 9
Kind: Prop

Name: A universal Turing machine
Definition: A machine computing a universal function
Page: 9
Kind: Prop

Question: The halting problem is
Answer: undecidable.
Page: 9
Chapter: 2
Index: 3
Kind: Prop

Question: Deciding whether the domain of \(\Phi_x\) is empty is
Answer: undecidable.
Page: 10
Chapter: 2
Variables: \(x\in\mathbb N\)
Index: 4
Kind: Prop

Name: s-m-n theorem
Definition: There is a computable function \(s\) such that \(\Phi_{s(x)}(y)=g(x,y)\)
Page: 10
Variables: \(g(x,y)\) a partial computable function
Index: 5
Kind: Lem
Etymology: ?

Name: A computable set
Definition: A computable enumerable set whose complement is computable enumerable.
Page: 11
Index: 1
Kind: Def

Definition: A set whose complement is c.e.
Page: 11
Notation: A co-c.e. set
Index: 1
Kind: Def

Smaller0: \(A\) is computable
Greater0: \(A\) is c.e.
Page: 11
Chapter: 2
Index: 1
Kind: Def

Name: The \(e\)-th computable enumerable set
Definition: \(\text{dom}(\Phi_e)\)
Page: 11
Variables: \(e\in\mathbb N\)
Notation: \(W_e\)
Index: 1
Kind: Def

Definition: the set of \(x\le s\) such that \(\Phi_e(x)[s]\downarrow\)
Page: 11,12
Variables: \(e,s\in\mathbb N\)
Notation: \(W_e[s]\)
Index: 1
Kind: Def
Intuition: the result of performing s steps in the enumeration of \(W_ e\).
Notation2: \(W_{e,s}\)

Name: An index for \(A\)
Definition: An integer \(e\) such that \(A=W_e\)
Page: 12
Variables: \(A\subseteq \mathbb N\) c.e.

Name: A uniformly computably enumerable family of sets
Definition: \((\text{dom}(f_n))_{n\in\mathbb N}\) for \((f_i)\) a uniformly partial computable function
Page: 12
Definition2: \((W_{g(n)})_{n\in\mathbb N}\) for some computable function \(g\).
Conjdef: equivalently
Definition3: \((\{x\mid \langle n,x\rangle\in A\})_{n\in\mathbb N}\) for some \(A\) c.e.
DefType: A sequence of set

Name: A uniformly computably family of sets
Definition: A sequence \((A_i)\) such that the functions \(\mathcal X_{A_i}\) are uniformly computable.
Page: 12

Name: A simple set
Definition: A co-infinite set which intersects each \(W_e\)
Page: 12
Definition2: A c.e. set whose complement is immune

Name: An immune set
Definition: An infinite set that contains no infinite \(c.e.\) set.
Page: 12

Question: Exemple of noncomputable c.e. set which is not simple
Answer: \(2A\) for \(A\) a noncomputable c.e. set
Page: 12
Chapter: 2