Infinite Time Turing Machines for elementary proofs on recursive reals - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Preprints, Working Papers, ... Year : 2023

Infinite Time Turing Machines for elementary proofs on recursive reals

Abstract

A famous theorem of recursion theory by Joseph Harrison published in 1967 states the existence of sneaky recursive non-well-orders of which the well-ordered initial segment is longer than any recursive ordinal. This result is quite intriguing because it proves that some recursive orders are quite good at hiding their infinite descending chains. The proofs given by J. Harrison and others from the 60s reside typically in $\text{ATR}_0$ (second order logic on integers). With the development of transfinite computational models, namely Infinite Time Turing Machines in the 2000s, and the evolution of ordinal computability theory over the past 23 years, we seized the opportunity of giving this result a more elementary proof using ITTMs. From a reverse mathematics perspective, it is interesting to present a proof assuming as little logical requirements of the arithmetical hierarchy as possible and our proof is in $ \text{ACA}_0$. Moreover, our work paves the way for an explicit construction of such orders.
Fichier principal
Vignette du fichier
article1_segments_init.pdf (108.79 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-04509148 , version 1 (18-03-2024)

Identifiers

  • HAL Id : lirmm-04509148 , version 1

Cite

Kenza Benjelloun, Bruno Durand. Infinite Time Turing Machines for elementary proofs on recursive reals. 2023. ⟨lirmm-04509148⟩
2 View
4 Download

Share

Gmail Facebook X LinkedIn More