Zobrazeno 1 - 10
of 27
pro vyhledávání: '"Jockusch Jr, Carl G."'
The coarse similarity class $[A]$ of $A$ is the set of all $B$ whose symmetric difference with $A$ has asymptotic density 0. There is a natural metric $\delta$ on the space $\mathcal{S}$ of coarse similarity classes defined by letting $\delta([A],[B]
Externí odkaz:
http://arxiv.org/abs/2106.13118
This paper concerns algorithms that give correct answers with (asymptotic) density $1$. A dense description of a function $g : \omega \to \omega$ is a partial function $f$ on $\omega$ such that $\left\{n : f(n) = g(n)\right\}$ has density $1$. We def
Externí odkaz:
http://arxiv.org/abs/1811.07172
Autor:
Csima, Barbara F., Dzhafarov, Damir D., Hirschfeldt, Denis R., Jockusch, Jr., Carl G., Solomon, Reed, Westrick, Linda Brown
Hindman's Theorem (HT) states that for every coloring of $\mathbb N$ with finitely many colors, there is an infinite set $H \subseteq \mathbb N$ such that all nonempty sums of distinct elements of $H$ have the same color. The investigation of restric
Externí odkaz:
http://arxiv.org/abs/1804.09809
Autor:
Jockusch Jr., Carl G., Schupp, Paul E.
In this article we survey the development of generic and coarse computability and the main results on how classical asymptotic density interacts with the theory of computability.
Comment: 20 pages
Comment: 20 pages
Externí odkaz:
http://arxiv.org/abs/1610.06504
We consider the strength and effective content of restricted versions of Hindman's Theorem in which the number of colors is specified and the length of the sums has a specified finite bound. Let $\mathsf{HT}^{\leq n}_k$ denote the assertion that for
Externí odkaz:
http://arxiv.org/abs/1603.08249
A coarse description of a subset A of omega is a subset D of omega such that the symmetric difference of A and D has asymptotic density 0. We study the extent to which noncomputable information can be effectively recovered from all coarse description
Externí odkaz:
http://arxiv.org/abs/1505.01707
For $r \in [0,1]$ we say that a set $A \subseteq \omega$ is \emph{coarsely computable at density} $r$ if there is a computable set $C$ such that $\{n : C(n) = A(n)\}$ has lower density at least $r$. Let $\gamma(A) = \sup \{r : A \hbox{ is coarsely co
Externí odkaz:
http://arxiv.org/abs/1505.01901
We study connections between classical asymptotic density and c.e. sets. We prove that a c.e. Turing degree d is not low if and only if d contains a c.e. set A of density 1 which has no computable subsets of density 1, giving a natural characterizati
Externí odkaz:
http://arxiv.org/abs/1307.0040
Autor:
Jockusch Jr., Carl G., Schupp, Paul E.
Generic computability has been studied in group theory and we now study it in the context of classical computability theory. A set A of natural numbers is generically computable if there is a partial computable function f whose domain has density 1 a
Externí odkaz:
http://arxiv.org/abs/1010.5212
Autor:
Hirschfeldt, Denis R.1 drh@math.uchicago.edu, Jockusch Jr., Carl G.2 jockusch@math.uiuc.edu, McNicholl, Timothy H.1 mcnichol@iastate.edu, Schupp, Paul E.2 schupp@illinois.edu
Publikováno v:
Computability. 2016, Vol. 5 Issue 1, p13-27. 15p.
