Diagonalizing Through the $ω$-Chain: Iterated Self-Certification on Bounded Turing Machines and its Least Fixed Point
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917317913346048 |
|---|---|
| author | Sung, Miara |
| author_facet | Sung, Miara |
| contents | Bounded self-certification in Turing machines fails because self-simulation necessarily incurs a strictly positive temporal overhead. We translate this operational constraint into a domain-theoretic framework, defining an operator that advances a finite halting observation from time bound $i$ to $i+1$. While no bounded machine can achieve a fixed point under this operator, the iterative process forms an ascending $ω$-chain. The Scott limit of this chain resolves to the least fixed point of the operator, representing an unbounded computation that fully captures the machine's halting behavior. Our construction provides a novel perspective on the halting problem, framing the transition from finite observability to the least fixed point as the continuous deferral of the diagonal. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_06012 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Diagonalizing Through the $ω$-Chain: Iterated Self-Certification on Bounded Turing Machines and its Least Fixed Point Sung, Miara Logic in Computer Science Bounded self-certification in Turing machines fails because self-simulation necessarily incurs a strictly positive temporal overhead. We translate this operational constraint into a domain-theoretic framework, defining an operator that advances a finite halting observation from time bound $i$ to $i+1$. While no bounded machine can achieve a fixed point under this operator, the iterative process forms an ascending $ω$-chain. The Scott limit of this chain resolves to the least fixed point of the operator, representing an unbounded computation that fully captures the machine's halting behavior. Our construction provides a novel perspective on the halting problem, framing the transition from finite observability to the least fixed point as the continuous deferral of the diagonal. |
| title | Diagonalizing Through the $ω$-Chain: Iterated Self-Certification on Bounded Turing Machines and its Least Fixed Point |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2603.06012 |