There are many classical connections between the proof-theoretic strength of systems of arithmetic and the provable totality of recursive functions. In this paper we study the provability strength of the totality of recursive functions by investigating the degree structure induced by the relative provability order of recursive algorithms. We prove several results about this proof-theoretic degree structure using recursion-theoretic techniques such as diagonalization and the Recursion Theorem.

We develop a new method for constructing hyperimmune minimal degrees and construct an ANR degree which is a minimal cover of a minimal degree.

We study the global properties of [Formula: see text], the Turing degrees of the n-r.e. sets. In Theorem 1.5, we show that the first order of [Formula: see text] is not decidable. In Theorem 1.6, we show that for any two n and m with n < m, [Formula: see text] is not a Σ1-substructure of [Formula: see text].

We show that there is a non-GL2 degree which is a minimal cover of a minimal degree. This answers a question by Lerman.

We show that there is a strong minimal pair in the computably enumerable Turing degrees, i.e. a pair of nonzero c.e. degrees a and b such that a∩b = 0 and for any nonzero c.e. degree x ≤ a, b ∪ x ≥ a.

We investigate the “unprovability of unprovability”. Given a sentence P and a fixed base theory T, the unprovability of P is the sentence “\ ”. We show that the unprovability of an unprovable true sentence can be “hard to prove”.

We present some abstract theorems showing how domination properties equivalent to being $\overline{GL}_{2}$ or array nonrecursive can be used to construct sets generic for different notions of forcing. These theorems are then applied to give simple proofs of some known results. We also give a direct uniform proof of a recent result of Ambos-Spies, Ding, Wang, and Yu [2009] that every degree above any in $\overline{GL}_{2}$ is recursively enumerable in a 1-generic degree strictly below it. Our major new result is (...) that every array nonrecursive degree is r.e. in some degree strictly below it. Our analysis of array nonrecursiveness and construction of generic sequences below ANR degrees also reveal a new level of uniformity in these types of results. (shrink)

In this paper we prove that a degree a is array nonrecursive (ANR) if and only if every degree b ≥ a is r.e. in and strictly above another degree (RRE). This result will answer some questions in [ASDWY]. We also deduce an interesting corollary that every n-REA degree has a strong minimal cover if and only if it is array recursive.

We show that there is a generalized high degree which is a minimal cover of a minimal degree. This is the highest jump class one can reach by finite iterations of minimality. This result also answers an old question by Lerman.

Reading in Chinese is complex because readers should not only recognize characters by basic units but also integrate characters into words when reading text. While many efforts have been devoted to investigating the effect of sub-lexical orthographic knowledge in Chinese character reading, less is known about the role played by lexical orthographic knowledge at word level. A total of 424 secondary learners with Chinese as a second language in Hong Kong were assessed with character reading, reading comprehension, and two lexical (...) orthographic knowledge tasks: lexical orthographic choice and lexical orthographic choice in context. Path analysis results demonstrated that these lexical orthographic skills significantly mediated the effect of character reading on comprehension, in which OKCC was a more critical mediator as its mediating effect was bigger than that of OKC. Further analyses showed that these mediating effects were significant only among students with richer learning experience. Our results illustrate the possible trajectory of CSL learners’ literacy development from character reading to reading comprehension and provide pedagogical implications for teaching and learning. (shrink)