Infinite computations with random oracles
classification
🧮 math.LO
keywords
machinesinfinitetimeanswercomputableconsidermeasureoracles
read the original abstract
We consider the following problem for various infinite time machines. If a real is computable relative to large set of oracles such as a set of full measure or just of positive measure, a comeager set, or a nonmeager Borel set, is it already computable? We show that the answer is independent from ZFC for ordinal time machines (OTMs) with and without ordinal parameters and give a positive answer for most other machines. For instance, we consider, infinite time Turing machines (ITTMs), unresetting and resetting infinite time register machines (wITRMs, ITRMs), and \alpha-Turing machines for countable admissible ordinals \alpha.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.