Separation Bc =/= Ex*

15 novembro 2013, 14:30 • José Félix Costa

Sistems of recursive simultaneous equations involving function indexes. (a)

Cases's operator recursion theorem \phi_{h(i)}(y) = \Phi(h)(<i,y>). (b)

Separation Bc =/= Ex* (proof based on (a) and (b)).

That R \notin Ex*.

+++++++

Problem set VI

Fix points of recursive operators

11 novembro 2013, 10:30 • José Félix Costa

Myhil-Shepherdson's theorems for recursive functionals.

Variants of Kleene's first recursion theorem (used to prove separations such like Ex* =/= Bc and Bc^{n} =/= Bc^{n+1}, for every n \in N).

Bc-identification

8 novembro 2013, 14:30 • José Félix Costa

That ASD* is in Ex* - \cup Ex^n.

Bc-identification (Barzdins, Case and Smith).

That Bc includes Ex* (Steel, Case and Smith). (Comment on the application of the argument of the proof in case studies in the History of Science.)

Discussion on the separation Bc =/= Ex*: the set S of recursive functions f such that, for all but finitely many values n, f(n) is a possible different index of f.

Ex^n hierarchy

4 novembro 2013, 10:30 • José Félix Costa

The n-variants and *-variants of recursive functions.

Ex^n- and Ex*-identification. The sets ASD^n and ASD* of almost self-describing functions with anomalies.

Case and Smith's theorem: ASD^(n+1) \in [ Ex^(n+1) - Ex^n ].

The non-collapsing hierarchy Ex \subset Ex^1 \subset Ex^2  \subset ...  \subset Ex^n  \subset Ex*.

That tolerating anomalies increases the inferring power of scientists. That research programs can induce omission errors: the case of Copernicus.

Parameterised scientists II

1 novembro 2013, 14:30 • José Félix Costa

Jantke theorem: That the set {i \in N : [i]f is TxtEx-identifiable}is not performable on [.]f .

That the set of indexes i such that #[i]f is finite is performable on [.]f.

+++++++

We also proved that there exists a collection of sets identifiable by a memory-limited scientist that is not TxtEx-identifiable by a memory-limited scientist.

+++++++

Problem set V.

+++++++

Solution to the identification of problem set III

LL is the class to be identified. Let W_a \not\in LL and f: N x N x N > N be one to one. D collects evidence, D_L is given by Angluin's theorem and m counts mind changes.

If W_i = L \in LL and D_L \subseteq D \cup {n} \subseteq L, then [ M(\sigma ^ n) = if m < n then f(i,D,m) else f(i,D \cup {n},m) ].

If (W_i \not\in LL or D \cup {n} \not\subseteq W_i) and (there exists L \not\in LL such that D_L \subseteq D \cup {n} \subseteq L, then [ M(\sigma ^ n) = f(j,D \cup {n},m+1) ], where j is the least index of L.

Otherwise M(\sigma ^ n) = f(a,D \cup {n},m+1).