Program Size Complexity of Correction Grammars in the Ershov Hierarchy

A general correction grammar for a language L is a program g that, for each \((x,t)\in \mathbb {N} ^2\), issues a yes or no (where when \(t=0\), the answer is always no) which is g’s t-th approximation in answering “\(x{\in } 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\in 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 \(\varSigma _u^{-1}\) sets in Ershov’s hierarchy of sets for \(\varDelta _2^0\). Herein we study the relative succinctness between these classes of correction grammars. Example: Given u and v, transfinite elements of O with \(u }H({i_{v}})\). 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.