Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-23T06:04:09.925Z Has data issue: false hasContentIssue false
  • English
  • Français

Nonexistence of minimal pairs for generic computability

Published online by Cambridge University Press:  12 March 2014

Gregory Igusa
Gregory Igusa*
Affiliation:
Department of Mathematics, University of California, Berkeley, 970 Evans Hall, Berkeley, CA 94720-3840, USA, E-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

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.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 78 , Issue 2 , June 2013 , pp. 511 - 522
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.)

References

REFERENCES

[1] Downey, Rod, Jockusch, Carl G. Jr., and Schupp, Paul, Asymptotic density and computably enumerable sets, submitted for publication.CrossRefGoogle Scholar
[2] Figueira, Santiago, Miller, Joseph S., and Nies, André, Indifferent sets, Journal of Logic and Computation, vol. 19 (2009), no. 2, pp. 425–443.CrossRefGoogle Scholar
[3] Gurevich, Y., Average case completeness, Journal of Computer and System Science, vol. 42 (1991), pp. 346–398.CrossRefGoogle Scholar
[4] Jockusch, Carl and Schupp, Paul, Generic computability, Turing degrees, and asymptotic density, Journal of the London Mathematical Society, vol. 85 (2012), no. 2, pp. 472–490.CrossRefGoogle Scholar
[5] Kapovich, Ilya, Miasnikov, Alexei, Schupp, Paul, and Shpilrain, Vladimir, Generic-case complexity, decision problems in group theory and random walks, Journal of Algebra, vol. 264 (2003), pp. 665–694.CrossRefGoogle Scholar
[6] Levin, L., Average case complete problems, SIAM Journal of Computing, vol. 15 (1986), pp. 285–286.CrossRefGoogle Scholar
[7] Soare, R., Recursively enumerable sets and degrees. Springer-Verlag, Berlin, 1987.CrossRefGoogle Scholar