Decision times of infinite computations

DOI10.1215/00294527-2022-0012OpenAlexW3104510769MaRDI QIDQ2153830

Philipp Schlicht, Merlin Carl, Philip D. Welch

Publication date: 13 July 2022

Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2011.04942

zbMATH Keywords

infinite time Turing machinesdecision algorithmshalting timesstable ordinals

Mathematics Subject Classification ID

Descriptive set theory (03E15) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and normal form theorems
• Recursion theory week. Proceedings of a conference held in Oberwolfach, Germany, March 19-25, 1989
• Ordinal computability. An introduction to infinitary machines
• Bounding lemmata for non-deterministic halting times of transfinite Turing machines
• Recursive well-orderings
• Hyperarithmetical quantifiers
• Π₁¹ Borel sets
• The Length of Infinite Time Turing Machine Computations
• Infinite time Turing machines
• Eventually infinite time Turing machine degrees: infinite time decidable reals
• Set Theory
• Provident sets and rudimentary set forcing
• Space and time complexity for infinite time Turing machines
• A complete classification of the Δ₂¹-functions

This page was built for publication: Decision times of infinite computations