pith. sign in

arxiv: 1307.0160 · v4 · pith:4TNYDXBYnew · submitted 2013-06-29 · 🧮 math.LO

Infinite computations with random oracles

classification 🧮 math.LO
keywords machinesinfinitetimeanswercomputableconsidermeasureoracles
0
0 comments X
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.