Hostname: page-component-7b7567c8c-w7t8q Total loading time: 0 Render date: 2026-11-17T23:45:09.084Z Has data issue: false hasContentIssue false

Nonexistence of minimal pairs for generic computability

Published online by Cambridge University Press:  12 March 2014

Gregory Igusa*
Affiliation:
Department of Mathematics, University of California, Berkeley, 970 Evans Hall, Berkeley, CA 94720-3840, USA, E-mail:igusa@math.berkeley.edu

Abstract

A generic computation of a subset A of ℕ consists of a computation that correctly computes most of the bits of A, and never incorrectly computes any bits of A, but which does not necessarily give an answer for every input. The motivation for this concept comes from group theory and complexity theory, but the purely recursion theoretic analysis proves to be interesting, and often counterintuitive. The primary result of this paper is that there are no minimal pairs for generic computability, answering a question of Jockusch and Schupp.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable