Infinite computations with random oracles

DOI10.1215/00294527-3832619zbMATH Open1417.03243arXiv1307.0160OpenAlexW2166732718MaRDI QIDQ2364653FDOQ2364653

Authors: Merlin Carl, Philipp Schlicht 

Publication date: 21 July 2017

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

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.

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

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

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)

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
• Title not available (Why is that?)
• ITRM-recognizability from random oracles
• 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)