Infinite computations with random oracles

DOI10.1215/00294527-3832619MaRDI QIDQ2364653zbMATH OpenOpenAlexFDO

Authors Merlin Carl, Philipp Schlicht

Publication date 21 July 2017

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

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

zbMATH Keywords

randomnessadmissible setsconstructibilitygeneralized recursion theoryinfinitary computations

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Descriptive set theory (03E15) Consistency and independence results (03E35) Higher-type and set recursion theory (03D65)

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.

Recommendations

• Infinite time Turing machines
• Ordinal computability
• The Length of Infinite Time Turing Machine Computations
• RANDOMNESS VIA INFINITE COMPUTATION AND EFFECTIVE DESCRIPTIVE SET THEORY
• Infinite time computable model theory

Cited in

(10)

• Computing with Infinite Terms and Infinite Reductions
• On slow minimal reals I
• Genericity and randomness with ITTMs
• Computability with an oracle in both classical and alternative infinity
• ITRM-recognizability from random oracles
• scientific article; zbMATH DE number 1531927 (Why is no real title available?)
• RANDOMNESS VIA INFINITE COMPUTATION AND EFFECTIVE DESCRIPTIVE SET THEORY
• Infinite time computable model theory
• Recognizable sets and Woodin cardinals: computation beyond the constructible universe
• Computations with oracles that measure vanishing quantities

This page was built for publication: Infinite computations with random oracles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2364653)