TY - GEN

T1 - Program size complexity of correction grammars in the ershov hierarchy

AU - Case, John

AU - Royer, James S.

N1 - Funding Information:
Thanks to Frank Stephan for alerting us to our earlier blunder of not noticing the need for even/odd cases in Theorem 6. Grant support was received by J. Case from NSF grant CCR-0208616, and by J. Royer from NSF grants CCR-0098198 and CCF-1319769.

PY - 2016

Y1 - 2016

N2 - A general correction grammar for a language L is a program g that, for each (x, t) ∈ N2, issues a yes or no (where when t = 0, the answer is always no) which is g’s t-th approximation in answering “x∈L?”; moreover, g’s sequence of approximations for a given x is required to converge after finitely many mind-changes. The set of correction grammars can be transfinitely stratified based on O, Kleene’s system of notation for constructive ordinals. For u ∈ O, a u-correction grammar’s mind changes have to fit a count-down process from ordinal notation u; these u-correction grammars capture precisely the Σu−1 sets in Ershov’s hierarchy of sets for Δ02. Herein we study the relative succinctness between these classes of correction grammars. Example: Given u and v, transfinite elements of O with u (2)-computable H: N → N, there is a v-correction grammar iv for a finite (alternatively, a co-finite) set A such that the smallest u-correction grammar for A is >H(iv). We also exhibit relative succinctness progressions in these systems of grammars and study the “information-theoretic” underpinnings of relative succinctness. Along the way, we verify and improve slightly a 1972 conjecture of Meyer and Bagchi.

AB - A general correction grammar for a language L is a program g that, for each (x, t) ∈ N2, issues a yes or no (where when t = 0, the answer is always no) which is g’s t-th approximation in answering “x∈L?”; moreover, g’s sequence of approximations for a given x is required to converge after finitely many mind-changes. The set of correction grammars can be transfinitely stratified based on O, Kleene’s system of notation for constructive ordinals. For u ∈ O, a u-correction grammar’s mind changes have to fit a count-down process from ordinal notation u; these u-correction grammars capture precisely the Σu−1 sets in Ershov’s hierarchy of sets for Δ02. Herein we study the relative succinctness between these classes of correction grammars. Example: Given u and v, transfinite elements of O with u (2)-computable H: N → N, there is a v-correction grammar iv for a finite (alternatively, a co-finite) set A such that the smallest u-correction grammar for A is >H(iv). We also exhibit relative succinctness progressions in these systems of grammars and study the “information-theoretic” underpinnings of relative succinctness. Along the way, we verify and improve slightly a 1972 conjecture of Meyer and Bagchi.

UR - http://www.scopus.com/inward/record.url?scp=84976648711&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84976648711&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-40189-8_25

DO - 10.1007/978-3-319-40189-8_25

M3 - Conference contribution

AN - SCOPUS:84976648711

SN - 9783319401881

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 240

EP - 250

BT - Pursuit of the Universal - 12th Conference on Computability in Europe, CiE 2016, Proceedings

A2 - Jonoska, Nataša

A2 - Bienvenu, Laurent

A2 - Beckmann, Arnold

PB - Springer Verlag

T2 - 12th Conference on Computability in Europe, CiE 2016

Y2 - 27 June 2016 through 1 July 2016

ER -