ファイル置き場 Sendai Logic Homepage ihara

(1)

Closed Sets of Reals

Closed Sets in the Cantor Space and Degrees of

Unsolvability

Takayuki Kihara

Mathematical Institute, Tohoku University

May 21, 2010

(2)

Closed Sets of Reals Degrees of Noncomputability of Reals

Decision Problems

Slogan I

✞

✝

☎ A Set of Integers✆=^✄

✂A Decision Problem✁ A set A represents the following problem:

“decide whether a given integer belongs to A !” Example

1 The set of all prime numbers

=“Decide whether a given integer is prime!”

2 The set of all theorems of a theory T

=“Decide whether a given sentence is a theorem of T !”

3 The set of all programs which eventually halt

=“Decide whether a given program eventually halts!”

(3)

Decision Problems

Slogan I

✞

✝

☎ A Set of Integers✆=^✄

✂A Decision Problem✁ Definition

If a problem A ⊆ Nis algorithmically decidable, we say that A is computableorrecursive.

Then one might ask whethernon-computableproblem exists. We notice the following:

An algorithm must be written by a finite word.

The setΣ^<ωof all finite words of an alphabetΣis countable. Thus, the set of all computable problems is at most countable. The set 2^ωof all decision problems is uncountable.

(4)

Natural Decision Problems

However...

Everynaturalproblem should be representable by a finite word.

So the set of all natural problems is at most countable...? Does there exist a non-computablenaturalproblem? If one think thatarithmetically definableproblem is natural...

We notice that every∆⁰

1problem is computable. In fact, computability is completely characterized by

∆⁰₁-definability!

(Fundamental Theorem) ∆⁰

1 ⁼ ^Computable

Is everyΣ⁰₁problem computable?

(5)

Σ⁰

1

Decision Problems

(Question) Is everyΣ⁰

1problem computable? Examples ofΣ⁰

1 decision problems

1 _Th₍_T_{) =}the set of all theorems of an axiomatizable theory T .

2 _HALT ₌the set of all programs which eventually halt. Theorem

1 (G ¨odel’s incompleteness theorem) If a consistent

axiomatizable theory T contains an elementary arithmetic, then Th(T)is non-computable!

2 (Turing’s theorem) HALT is non-computable!

(6)

Oracle Computation

Now, we are interested in degrees of algorithmic unsolvability. For given non-computable problems A and B, which problem ismore non-computable?

Definition

A Turing functionalis a algorithm with special instructions of the form “z:=Oracle(x)” for some variableszandx. Φ(f;n)executes the algorithmΦwith an input n, and if an instruction “z:=Oracle(x)” occurs and if the current value of xis x, thenΦassigns the value f(x)to the variablez. Φ(f;n) = m if the computationΦ(f;n)halts with an output m, andΦ(f;n)is undefined, otherwise.

A Turing functional is a partial function: ω^ω×ω → ω, and is usually regarded as a partial function: ω^ω→ω^ω.

(7)

Definition

1 A problem A is computable froma problem B (denoted by A ≤_T B) if a Turing functionalΦ :B 7→A exists.

2 _A _≡_T _{B if A} _≤_T _{B and B} _≤_T _{A .}

3 Turing degreesordegrees of unsolvabilityare defined by D =2^ω/ ≡_T, and letdeg_T(A) =A/ ≡_T.

Observation

At most countable Turing functionals exist.

Indeed, there exists a computable enumeration{Φe^}e∈ω^{of all}

Turing functionals.

For every problem B,{A ∈2^ω :A ≤_T B}is countable.

(8)

Basic results in the global structure

Theorem

For every problem A :

1 Continuum many problems≥_T A exist.

2 (Sacks) If A is noncomputable, then

the Lebesgue measure of{B ∈ 2^ω: B ≥_T A}is 0.

3 Hence, almost all problems are Turing incomparable with A .

Arithmetically definable problems are at most countable. We next focus on the degree structure of arithmetical problems, includingΣ⁰

1problems, such as the halting problem.

(9)

Definition

The halting problem relative to Ais the set of all Turing functionals which eventually halt with an oracle-input A . Formally, it is defined by A^′ = {e : Φ_e(A;0) ↓}.

We call A^′the Turing jump of A. A^′ is aΣ⁰

1⁽^A⁾^problem.

We can iterate the Turing jump operation, such as A^′,A^′′,A^′′′, . . .

A⁽ⁿ⁾ denotes the n-th Turing jump of A . Theorem

A <_T A^′ <_T A^′′ <_T A^′′′ <_T · · ·<_T A⁽ⁿ⁾ <_T A⁽ⁿ⁺¹⁾ <_T . . ..

(10)

One often uses the sequence of Turing jumps{∅⁽ⁿ⁾}as a barometer of the degree of noncomputability.

One can ask:

“Is a given problem more noncomputable than∅⁽ⁿ⁾, or not?” But...

Is that really a good barometer?

There is no reason to believe that the use of the halting problem is essential.

Post’s theoremtells us that the halting problem is, really and truly, universal in the arithmetical hierarchy.

(11)

Post’s theorem

1 _Σ⁰

n+1 ^{= Σ} 0 1^(∅

(n)₎_.

2 _A _∈ _∆⁰

n+1 ^⇐⇒ ^A ^≤^T ^∅ (n)_.

Relativized Post’s theorem

1 _Σ⁰

n+1⁽^B^{) = Σ} 0 1⁽^B

(n)₎_.

2 _A _∈ _∆⁰

n+1⁽^B^{) ⇐⇒} ^A ^≤^T ^B (n)_.

Corollary

∆⁰

1⁽^B^{) =} Computable from B .

(12)

Basic results in Recursion Theory

Problem (Post (1944)) Does there exist aΣ⁰

1problem A such that∅<_T A <_T ∅^′?

Theorem (Kleene-Post (1954)) There exists a∆⁰

2problem A such that∅<_T A <_T ∅^′. Indeed, Turing degrees of∆⁰

2problems are not linear ordered.

Theorem (Friedberg (1957), Muchnik (1956)) There exists aΣ⁰

1problem A such that∅<_T A <_T ∅^′. Indeed, Turing degrees ofΣ⁰

1problems are not linear ordered.

(13)

Arithmetical hierarchy

∆⁰

1 ^computable

Σ⁰

1 computably enumerable

∆⁰

2 limit computable Sn<ω^Σ⁰_n arithmetical

∆¹

1 hyper-arithmetical Theorem

∆¹

1 ⁼

S

α<ω^CK

1

∆⁰_α. Hereω^CK

1 denotes the Church-Kleene’sω₁, the first noncomputable ordinal.

(14)

Hierarchy in Reverse Mathematics RCA= ∆⁰

1^-CA

WKL ACA= Σ⁰

1^-CA^{= Σ} 0

2^-CA^{= Σ} 0 n^-CA

ACA⁺ = Σ⁰_ω-CA

∆¹

1^-CA

ATR≈^S_α<ωCK 1

∆⁰_α-CA Π¹

1^-CA

(15)

1 We observed an attractive connection between a definability hierarchy and a computability hierarchy inω.

2 Does an analogous principle hold in other topological spaces? Definition (topological spaces of words)

For a set of symbolsΣ ⊆ N, the topological spaceΣ^ωis defined by the countable topological product of the discrete spaceΣ.

Equivalently, the topology ofΣ^ωis also induced by the basic neighborhood system: N_σ = {f ∈ Σ^ω :f ⊃σ}forσ ∈ Σ^<ω.

1 ₂^ωis said to bethe Cantor space.

2 _ω^ωis said to bethe Baire space.

(16)

Borel hierarchy

A_Γ

∼^{set is a}^Γ-definable set with a real parameter. Formally, A isa_Γ

∼^setin the spaceXif there exists aΓ-formula ψand a pointp~ ∈ Xⁿsuch that A = {x ∈ X: ψ(x, ~p)}.

Definability Hierarchy with Parameters=Topological Hierarchy Σ_∼⁰₁ ^open

Π_∼⁰₁ ^closed Σ∼

0

2 ^F^σ

Π_∼⁰₂ ^Gδ

∆_∼¹₁ ^Borel

(17)

lightface Borel hierarchy

A_Γset is aΓ-definable set without a real parameter. Formally, A isa_Γ setin the spaceXif there exists a Γ-formulaψsuch that A = {x ∈ X: ψ(x)}.

One might think also a_Γ set as a problem described by a Γ-formula.

Slogan II

✞

✝

☎ A Set of Reals✆=^✄

✂A Mass Problem✁

(18)

lightface theory and computability

Definition

1 _G₍_X_{) = {σ :} _N_σ _⊆ _X_}_.

2 _T

Y ⁼ ^G⁽^Y^∁⁾^∁ ^{= {σ :}^Nσ∩Y ,_∅}. Representation of open and closed sets

1 _int₍_X_{) =}^S

σ∈G(X)^Nσ^;

hence, for an open set O, O =^S_σ∈G(O)N_σ.

2 _T

Y is a tree without dead ends, and cl(Y) = [T_Y]; hence, for a closed set C, C = [T_C].

3 An open set O isΓ-openif G(O)is aΓset.

4 A closed set C isΓ-closedif T_C is aΓset.

5 _{O is a}_Σ⁰

1 set if and only if it is aΣ⁰

1^{-open set.}

6 _{C is a}_Π⁰set if and only if it is aΠ⁰-closed set.

(19)

1 (Post’s theorem) Inω:

1 _Σ⁰

1^(∅

(n)_{) ⇐⇒ Σ}0 n+1^.

2 _Π⁰

1^(∅

(n)_{) ⇐⇒ Π}0 n+1^. 2 _{In 2}^ω_:

1 _Σ⁰ 1^(∅

(n)_{) ⇐⇒ Σ}0

n+1^-open ^=⇒ ^Σ 0

n+1^{& open} ^=⇒ ^Σ 0 n+1

2 _Π⁰

1^(∅

(n)_{) ⇐⇒ Π}0

n+1^-closed ^⇒ ^Π 0

n+1& closed ⇒ _Π⁰

n+1

Remark

In the above figure, no reverse implication holds for n≥ 1:

1 There exists a set which is_Σ⁰

2 ^{but not}^Σ∼ 0 1^.

2 _∅^(ω)_is_Π⁰

2singleton (i.e.,{∅^(ω)}is a_Π⁰

2set), hence is closed.

(ω) _Π0 _ω

(20)

Definability Hierarchy=Computability Hierarchy Clopen (_∆⁰

1⁾ Finite set of finite strings Effectively open (_Σ⁰

1⁾ ^{C. e. (}^Σ 0

1^{) set G}^Oof finite strings. Effectively closed (_Π⁰

1⁾ ^{Co-c.e. (}^Π 0

1^{) sets T}^C of finite strings. Now, the complexity and the Turing degree of G_O (resp. T_C) is regarded as those of an open set O (resp. a closed set C). To avoid confusion, aΓset in 2^ωis said to beaΓclass.

(21)

Slogan II

✞

✝

☎ A Set of Reals✆=^✄

✂A Mass Problem✁

A set A represents a solution set of a problem: “find an element of A !”

Example

1 The set of all transcendental numbers.

=“Find a transcendental number!”

2 The set of all fixed-points of a continuous function on[0,1].

=“Find a fixed-point of a continuous function on[0,1]!”

3 The set of all 4-colorings of a map.

=“Color a map using at most 4 colors!”

4 The set of all complete consistent extensions of a theory T

=“Find a complete consistent extension of T !”

(22)

Degrees of points in

Π⁰₁

sets

A question is whether or not there exists a computably unsolvable problem.

The example 1 is computably solvable becauseπand e are not algebraic, and are computable reals.

The examples 2,3,4 are closed (_Π

∼ 0

1) problem in spaces [0,1],4^ω,2^ω, respectively.

Does there exist a computably unsolvable problem in these examples?

(23)

Remark

1 Every open set contains a computable point.

2 Some closed set contains no computable point. E.g., for a noncomputable real r, the singleton{r}contains no computable point.

3 However, the closed set{r}is not effectively closed.

4 _Every_∆⁰

1-closed set contains a computable point.

5 Does an effectively closed set (i.e._Π⁰

1) always contain a computable point?

(24)

Examples of

Π⁰₁

classes

Problem Does a_Π⁰

1class always contains a computable point? In other words:

Does a_Π⁰

1mass problem always have a computable solution?

Example (_Π⁰

1 ^problems)

1 The set of all zeros of a computable continuous function.

2 The set of all fixed points of a computable continuous function.

3 The set of all (prime) ideals of a c.e. Boolean algebra.

4 The set of all subgroups of a c.e. group.

5 The set of all 4-colorings of a computable map.

6 The set of all marriages in a computable society.

(25)

Computability of points in

Π⁰₁

sets

Observation

1 _Every_Π⁰

1 singleton is computable.

2 Every isolated point in a_Π⁰

1class is computable.

3 Every somewhere dense_Π⁰

1 class contains a computable point.

4 _{For a}_Π⁰

1 class P, if the Lebesgue measure of P is a positive computable real, then P contains a computable point. Theorem

Assume P is aΠ⁰

1 ^class:

1 _{If x} _∈ P is of the Cantor-Bendixson rank n, then x ≤_T ∅⁽²ⁿ⁾.

2 If P is countable, then the CB-rank of P is< ω^CK

1 ^{; hence,}

(26)

Degrees of points in

Π⁰₁

sets

In some sense, every_Π⁰

1class contains a nearly computable points.

Kreisel Basis Theorem (1958) Every_Π⁰

1class contains a∆⁰

2^point.

Indeed, every end point in the class is of aΣ⁰

1^degree.

Corollary in Reverse Mathematics ACA⊢WKL.

Kreisel-Shoenfield Basis Theorem (1960) Every_Π⁰

1class contains a point p <_T ∅^′.

(27)

Jockusch-Soare Low Basis Theorem (1972) Every_Π⁰

1class contains a low point p, i.e. p^′ ≤_T ∅^′. Corollary in Reverse Mathematics

There exists aω-model of WKL which contains only low sets; hence, WKL⁰ACA.

(28)

Antibasis theorems

Theorem (Kreisel’s Anti-Basis Theorem (1953)) There exists a_Π⁰

1classes which contains no computable point.

Corollary in Reverse Mathematics

Everyω-model of WKL must contain a noncomputable set; hence, RCA⁰WKL.

(29)

Proof of Anti-Basis Theorem.

(Lindenbaum) Every consistent theory has a complete consistent extension.

(Shoenfield; 1960) The set of all complete consistent extension of an axiomatizable theory forms a_Π⁰

1^class.

(G ¨odel’s incompleteness theorem) Elementary arithmetic has no complete consistent axiomatizable extensions.

Hence, for example, the set of all complete consistent extension of Peano Arithmetic is a desired_Π⁰

1class without a computable point.

(30)

When a real is computable

Assume we would like to computeπ.

1 (Bit Computation) We compute the following sequence: 3,3.1,3,14,3.141,3.1415, . . .

So, a computable real is a computable sequence of rationals!

2 (Neighborhood Computation) We compute a descending sequence of open neighborhoods N_π↾nofπ.

Hereµ(Nπ↾n) ≤10⁻ⁿ and{π} =^Tn^Nπ↾nis a_Π⁰

2^singleton.

We notice that{_{π} =}^T_nNπ↾nis aΠ⁰₁singleton because Nπ↾n

is, indeed, clopen.

Neighborhood Computation Computable Point = _Π⁰

1^singleton

(31)

Definition

We say that a_Π⁰

2⁽^A⁾^{set P is}effectively nullif P = ^T_nU^A

n ^{for an}

A -computable sequence{U^A

n^}^n∈ω^of^Σ 0

1⁽^A⁾-open sets for which µ(U_n) ≤ 2⁻ⁿ.

Observation

x is noncomputable ⇐⇒ x avoids any_Π⁰

1^singleton.

⇐=x avoids any_Π⁰

2effectively singleton. Definition

1 _{x is}Kurtz randomif x avoids any_Π⁰

1 ^{null set.}

2 _{x is}Martin-L ¨of randomif x avoids any_Π⁰

2effectively null set.

(32)

Fact

Every null set is covered by a_Π

∼ 0

1 Every null set is covered by a_Π⁰

2⁽^A⁾effectively null set with an oracle A .

2 Some null set cannot be covered by any_Π⁰

1⁽^A⁾null set with any oracle A .

3 Indeed, some_Π⁰

2effectively null set cannot be covered by any Π⁰₁(A)null set with any oracle A .

In this sense, Kurtz randomness seems to be too weak.

(33)

Definition

1 _{x is}Kurtz randomif x avoids any_Π⁰

1 ^{null set.}

2 _{x is}Martin-L ¨of randomif x avoids any_Π⁰

3 _{x is}weakly 2-randomif x avoids any_Π⁰

2^{null set.}

Observation However, a_Π⁰

2-procedure is not effective:

1 _No_∆⁰

2 real avoids any_Π⁰

2^singleton.

2 Indeed, a nonarithmetical real∅^(ω)does not avoid a_Π⁰ singleton. 2

In this sense, weakly 2-random seems to be too strong, if we regard “being random” as a generalization of “being

(34)

Observation Not every_Π⁰

2effectively singleton is computable. Problem

What reals are represented by a_Π⁰

1 effectively singleton?

(35)

Martion-L ¨ of random reals

We have observed aΠ⁰

1class without computable points. Now we ask whether there is aΠ⁰

1class without “almost” computable points:

(Question) Does there exist aΠ⁰

1 class which contains only Martin-L ¨of random real?

Theorem

1 The set MLR of all Martin-L ¨of random reals form a_Σ⁰

2^class.

2 There exists aΠ⁰

1class which contains only Martin-L ¨of random real.

3 MLR is degree-isomorphic to a_Π⁰

1 ^class.

4 _Every_Π⁰

1 class of Lebesgue measure>0 contains a point of

(36)

Corollary in Reverse Mathematics

Everyω-model of WWKL must contain a Martin-L ¨of random set; hence, RCA⁰WWKL.

(37)

Generic properties are another example of “almost-all” properties: (Random) If a property P almost always holds,

then a random point satisfies P.

(Generic) If a property P generically holds, then a generic point satisfies P.

Here:

“P almost always holds” means that P isconull, i.e., its complement is measure 0.

“P generically holds ( P)” usually means that P iscomeager, i.e., its complement is a countable union of nowhere dense sets.

(38)

Definition

1 _{x is}weakly 1-genericif x avoids any nowhere dense_Π⁰

1^{set P;}

Equivalently, if int(P) = ∅ ⇒ x ^< P.

2 _{x is}_1-genericif, for any_Π⁰

1 ^{class P, x} ^<^int⁽^P^{) ⇒} ^x ^< ^P.

We have already observed the existence of the following:

1 _A_Π⁰

1class without computable points.

2 _A_Π⁰

1class without non-ML-random points. Now we again ask whether there is a_Π⁰

1class without

“almost” computable points. However... recall that, if a_Π⁰

1contains no computable points, then it must be nowhere dense!

Hence, every_Π⁰

1 class contains a non-1-generic point.

(39)

Some invisible reals from

Π⁰₁

classes

Definition (Invisible Notions)

1 _{x is}_unrankedif it avoids any countable_Π⁰

1^class.

2 _{x is}semi-genericif it is noncomputable and it avoids any_Π⁰ class without computable points. 1

3 _{x is}Kurtz randomif it avoids any null_Π⁰

1^class.

4 _{x is}weakly 1-genericif it avoids any nowhere dense_Π⁰

1^set.

5 _{x is}weakly n-genericif it avoids any nowhere dense Π⁰_n-closed set.

And, for a Turing-degree d;

1 _{d is}completely unrankedif d contains only unranked reals.

2 _{d is}purely semigenericif d contains only semigeneric reals.

3 _{d is}_invisible_{if any}_Π⁰class P contains no point of degree d

(40)

Some invisible reals from

Π⁰₁

classes

Theorem (Lewis) There exists a∆⁰

3invisible real. Indeed, every weakly 2-generic real is invisible.

(41)

A computably unsolvable_Π⁰

1 mass problem exists.

For given computably unsolvable problems P and Q, which problem ismore unsolvable?

Definition

1 _A _≤

T ^B if a Turing functional B 7→A exists.

2 _P _≤

M ^Q if a Turing functional Q →P exists.

A Medvedev degreeis a equivalent class induced by≡_M.

Observation

∅is the most difficult problem;

∅is a problem without solutions!

A computably solvable problem is on of the easiest problems.

(42)

Medvedev degrees

In 1955, Medvedev introduced the notion of Medvedev degree to give a semantics of the Intuitionistic Propositional Logic. But it may have been first suggested by Kolmogorov. The top element∅corresponds to the contradiction⊥. The bottom elementω^ωcorresponds to the tautology⊤. If one witnesses the truth of P and if Q ≤_M P, then one can also witnesses the truth of Q via a computable procedure! Actually, Medvedev showed that the set of all Medvedev degrees forms a Brouwer algebra (i.e. dual Heyting algebra). Now we observed that the Medvedev degrees gives a truth value, and also a computability value.

But our interest is not in a truth value but in a computability value.

(43)

Observation

If P ⊇Q then P ≤_M Q; Intuitively:

If a problem P has more solutions than Q, then P must be easier than Q!

If P is of Lebesgue measure> 0, then P has many many solutions. So, P is expected to be easy.

However, we should remember that some problem P of Lebesgue measure>0 contains only random points!

Nevertheless, still a problem of measure>0 is easy, in some sense.

Proposition

The Medvedev degrees of all_Π⁰

1 classes of Lebesgue measure

>0 form a prime ideal in the_Π⁰

1Medvedev degrees.

(44)

Definition (Cenzer-K.-Weber-Wu (2009)) For a_Π⁰

1^{class P} ^⊆² ω_,

1 _{P is}_immuneif there is no infiniteΣ⁰

1 subtree of T_P.

2 _{P is}tree-immuneif there is no infinite∆⁰

1 subtree of T_P. For a_Π⁰

1^{set P} ^⊆^ω ω_,

P isimmuneif there is noΣ⁰

1 ^{subtree S} ^⊆^T^P^{such that}^[^S^{] , ∅}^.

Theorem (Demuth-Kucera)

1 The set of all fixed-point-free functions forms a immune_Π⁰ class. 1

2 Every immune_Π⁰

1^class^⊆^ω

ωcontains no points computable from a 1-generic.

3 _{If a} _>0 is not semi-generic then some immune_Π⁰

1^class

contains a point of degree a.

(45)

Scott’s Basis Theorem EveryΠ⁰

1class contains a point which computable from a complete consistent extension of PA.

Theorem (Pour-El–Kripke (19XX) / Simpson (2000)) The following are equivalent for anyΠ⁰

1 ^{class P:}

1 P has the greatest Medvedev degree among all nonempty_Π⁰ classes. 1

2 P is computably homeomorphic to the set of all complete consistent extension of PA (ZFC, RCA₀, etc.)

(46)

Theorem (Cole-Kihara (2010))

The∀∃-theory of Medvedev degrees of_Π⁰

1 classes is decidable.

(47)

Recall that a_Π⁰

1class P is generated by aΠ⁰

1^{set T}^P^.

So,∅ ≤_T T_P ≤_T ∅^′. Every_Π⁰

1 class P for which T_P ≡_T ∅contains a computable point, hence P has the Medvedev degree 0.

The Medvedev degree of P is 1 then T_Phas the Turing degree 0^′.

(Def.) A_Π⁰

1^{class P is}^thin^{if every}^Π 0

1^{subclass Q} ^⊆ ^{P is open}

in the relative topology of P:

1 If P is a thinΠ⁰₁class then TPis of ANR-degree.

2 For every ANR-degree a, there exists a thinΠ⁰₁class P such that TPis of degree a.

3 _{No thin}_Π⁰

1class has the Medvedev degree 1.

4 _{No thin}_Π⁰

1class without isolated points has the Medvedev degree 0.

(48)

Theorem (K. (2010)) LetI_Mbe an ideal of∆⁰

2Turing degrees generated by {deg_T(T_Q) : Q ∈ M}.

1 _Let_Mbe an effective family of_Π⁰

1 classes, and supposeI_M form a proper ideal in∆⁰

2 Turing degrees. Then there exists a Π⁰

1 class P such that∅<_T T_P <_T ∅^′such that Q ≤_M P for every Q ∈ M.

2 _{If P is a}_Π⁰

1^{class of}^∅^<^T ^T^P ^<^T ^∅

′then there exists aΠ⁰ class Q >_M P for which∅<_T T_Q <_T ∅^′. 1

(49)

ファイル置き場 Sendai Logic Homepage ihara

Closed Sets in the Cantor Space and Degrees of

Unsolvability

Decision Problems

Decision Problems

Natural Decision Problems

Decision Problems

Oracle Computation

Basic results in the global structure

Basic results in Recursion Theory

Arithmetical hierarchy

Borel hierarchy

lightface Borel hierarchy

lightface theory and computability

Degrees of points in

sets

Examples of

classes

Computability of points in

sets

Degrees of points in

sets

Antibasis theorems

When a real is computable

Martion-L ¨ of random reals

Some invisible reals from

classes

Some invisible reals from

classes

Medvedev degrees

Thank you!