Phase Transition Thresholds for Generalized Goodstein Sequences, Hydra Games and Ackermannian Functions.
Gabriele Buriola
Authors: Gabriele Buriola and Andreas Weiermann
We extend previous results [2] regarding the phase transition thresholds for Goodstein Sequences and Hydra Games to a more general setting. In both cases, we substitute the original successor function with the iterations of a strictly increasing primitive recursive function \(g\) satisfying the condition \(g(x) \geq x+1\); more precisely, the steps of the Hydra Game, originally of type \(\alpha_{f\!,i+1}= \alpha_{f\!,i}[1+f(i)]\), are now of the form \(\alpha^{f\!,g}_{i+1}=\alpha^{f\!,g}_{i}[1+f(g^{i-1}(1))]\), while the steps of Goodstein sequences are changed from \(m_{f\!,i+1}=m_{f\!,i}\left(1+f(i) \mapsto 1+f(i+1)\right) -1\) to \(m^{f\!,g}_{i+1}=m^{f\!,g}_i\left(1+f(g^{i-1}(1)) \mapsto 1+f(g^{i}(1))\right) -1\). The new phase transition thresholds incorporate the starting function \(g\). These findings also allow a generalization of the phase transition threshold for Ackermannian functions [1] and fit within a rich literature regarding phase transitions in provability [3,4,5].
Bibliography
- E. Omri, A. Weiermann,Classifying the phase transition threshold for Ackermannian functions,Journal of Pure and Applied Logic,Vol. 158, (2009), pp. 156–162.
- F. Meskens, A. Weiermann,Classifying phase transition thresholds for Goodstein sequences and Hydra games,Gentzen’s Centenary,Springer International Publishing, Cham, (2015), pp. 455–478.
- L. Carlucci, G. Lee, A. Weiermann,Sharp thresholds for hypergraph regressive Ramsey numbers,Journal of combinatorial theory. Series A,Vol. 118(2), (2011), pp. 558–585.
- M. De Smet, A. Weiermann,Sharp Thresholds for a Phase Transition Related to Weakly Increasing Sequences,Journal of logic and computation,Vol. 22(2), (2012), pp. 207–211.
- L. Gordeev, A. Weiermann,Phase transitions in Proof Theory,Discrete Mathematics and Theoretical Computer Science,(Proceedings), (2010), pp. 343–358.