Universality and almost decidability

DOI10.3233/FI-2015-1199zbMATH Open1335.68086arXiv1505.01340MaRDI QIDQ2805447FDOQ2805447

Damien Desfontaines, Cristian S. Calude

Publication date: 11 May 2016

Published in: Fundamenta Informaticae (Search for Journal in Brave)

Abstract: We present and study new definitions of universal and programmable universal unary functions and consider a new simplicity criterion: almost decidability of the halting set. A set of positive integers S is almost decidable if there exists a decidable and generic (i.e. a set of natural density one) set whose intersection with S is decidable. Every decidable set is almost decidable, but the converse implication is false. We prove the existence of infinitely many universal functions whose halting sets are generic (negligible, i.e. have density zero) and (not) almost decidable. One result - namely, the existence of infinitely many universal functions whose halting sets are generic (negligible) and not almost decidable - solves an open problem in [9]. We conclude with some open problems.

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

Recommendations

• The halting problem is decidable on a set of asymptotic probability one
• On the strongly generic undecidability of the halting problem
• Generic complexity of undecidable problems
• scientific article; zbMATH DE number 1114344
• Inaccessibility and undecidability in computation, geometry, and dynamical systems

zbMATH Keywords

densityuniversal functionhalting setalmost decidable setgeneric and negligible sets

Mathematics Subject Classification ID

Turing machines and related notions (03D10)

Cited In (5)

• Deciding Universality of ptNFAs is PSpace-Complete
• Universal Induction and True Universal Arithmetic
• Universal abstract consistency class and universal refutation
• Universality of Regular Realizability Problems
• Universality Results for Models in Locally Boolean Domains

This page was built for publication: Universality and almost decidability

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