Some interesting connections between the slow growing hierarchy and the Ackermann function (Q2747706)

In the paper under review correlations are treated between NEWLINENEWLINENEWLINE\(\bullet\) ordinal notation systems, NEWLINENEWLINENEWLINE\(\bullet\) the slow growing hierarchies (sgh) that can be defined using these systems, and NEWLINENEWLINENEWLINE\(\bullet\) estimates for the lengths of the derivations in finite rewrite systems. NEWLINENEWLINENEWLINEThe ordinal notations considered are of order types \(\varepsilon_0\) respectively \(\Gamma_0\). The sghs that are defined by these systems depend on the fundamental sequences which are established in the notation systems. Moreover it is relevant NEWLINENEWLINENEWLINE\(\bullet\) whether the notation systems are built up only from the Veblen functions or are also using ordinal addition, NEWLINENEWLINENEWLINE\(\bullet\) whether the Veblen functions in question contain fixed points or omit fixed points, and NEWLINENEWLINENEWLINE\(\bullet\) whether the ordinals in the systems are considered as set-theoretic objects or as tree ordinals. NEWLINENEWLINENEWLINEBy combining the specified properties and options, different variants of sghs arise with varying properties with respect to rewrite systems. The following situations are exemplified by the rewrite system \(R_A\) for the Ackermann function: NEWLINENEWLINENEWLINEIn \S~2, a system \(T\) of ordinal notations together with the fundamental sequences and the sgh is established such that the so-called Cichon's principle holds: \((G_\alpha)_{\alpha\in T}\) classifies the computational complexity of \(R_A\). The order tape of \(T\) is \(\Gamma_0\). NEWLINENEWLINENEWLINEIn \S~3, a system \(T^{\text{tree}}\) of tree ordinals is given which already includes a ``built-in'' system of fundamental sequences. Its order type is \(\varepsilon_0\). The sgh defined in this ordinal system is shown to majorize every function elementary recursive in the Ackermann function. Thus \((G_\alpha)_{\alpha\in T^{\text{tree}}}\) classifies the computational complexity of \(R_A\), too. The difference results from the fact that the Veblen functions in \(T^{\text{tree}}\) omit fixpoints. NEWLINENEWLINENEWLINEIn \S~4, Cichon's question is answered why the ordinal system \(T^*\) of set-theoretic ordinal notations with Veblen functions but without addition (expressed by the superscript \(^*\)) does not satisfy Cichon's principle mentioned above: The sgh for this system majorizes the elementary recursive functions and vice versa, whereas in the system \(T^{\text{tree}*}\) of tree ordinals without addition the sgh majorizes the functions elementary recursive in the Ackermann function and thus classifies the computational complexity of \(R_A\). The paper starts with a comprehensive introduction and motivation which covers nearly one third of the whole paper. It seems to confirm the opinion of the reviewer that the question of a standard notation system depends on the properties desired.