A Cardinality Version of Biegel's Nonspeedup Theorem

Owings, James C.

J. Symbolic Logic, Tome 54 (1989) no. 1, p. 761-767 / Harvested from Project Euclid

Résumé

If $S$ is a finite set, let $|S|$ be the cardinality of $S$. We show that if $m \in \omega, A \subseteq \omega, B \subseteq \omega$, and $|\{i: 1 \leq i \leq 2^m \& x_i \in A\}|$ can be computed by an algorithm which, for all $x_1,\ldots,x_{2^m}$, makes at most $m$ queries to $B$, then $A$ is recursive in the halting set $K$. If $m = 1$, we show that $A$ is recursive.

Publié le : 1989-09-14
Classification:

@article{1183743014,
     author = {Owings, James C.},
     title = {A Cardinality Version of Biegel's Nonspeedup Theorem},
     journal = {J. Symbolic Logic},
     volume = {54},
     number = {1},
     year = {1989},
     pages = { 761-767},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183743014}
}

Owings, James C. A Cardinality Version of Biegel's Nonspeedup Theorem. J. Symbolic Logic, Tome 54 (1989) no. 1, pp.  761-767. http://gdmltest.u-ga.fr/item/1183743014/