- Submit
-
Browse
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- More
Switch to: References
Citations of:
Add citations
You must login to add citations.
|
|
|
We use the Low Basis Theorem of Jockusch and Soare to show that all computable algebraic fields are d-computably categorical for a particular Turing degree d with d' = θ", but that not all such fields are 0'-computably categorical. We also prove related results about algebraic fields with splitting algorithms, and fields of finite transcendence degree over ℚ. |
|
|
Khutoretskii's Theorem states that the Rogers semilattice of any family of c.e. sets has either at most one or infinitely many elements. A lemma in the inductive step of the proof shows that no Rogers semilattice can be partitioned into a principal ideal and a principal filter. We show that such a partitioning is possible for some family of d.c.e. sets. In fact, we construct a family of c.e. sets which, when viewed as a family of d.c.e. sets, has (up (...) |
|
|
|
|
|
We prove that all infinite Boolean rings have the property P ≠ NP according to the digital nondeterminism. |
|
|
A strong reducibility relation between partial numberings is introduced which is such that the reduction function transfers exactly the numbers which are indices under the numbering to be reduced into corresponding indices of the other numbering. The degrees of partial numberings of a given set with respect to this relation form an upper semilattice.In addition, Ershov’s completion construction for total numberings is extended to the partial case: every partially numbered set can be embedded in a set which results from the (...) |
|
|
In examples like the total recursive functions or the computable real numbers the canonical indexings are only partial maps. It is even impossible in these cases to find an equivalent total numbering. We consider effectively given topological T 0 -spaces and study the problem in which cases the canonical numberings of such spaces can be totalized, i.e., have an equivalent total indexing. Moreover, we show under very natural assumptions that such spaces can effectively and effectively homeomorphically be embedded into a (...) |
|
|
|
|
|
|
|
|
|
|
|
We present a simple proof of a Theorem of Khutoretskij on the number of incomparable one-one numberings of an r.e. family of r.e. sets. The proof directly generalizes to effective domains. In the second part, applying a Theorem of Goncharov, we show that for anyk≧ there exist total recursive functions having exactlyk recursive isomorphism classes. Using a Theorem of Selivanov, it is shown that a certain notion of computability via gödelization is different from Lacombe's notion ofV-recursiveness. Finally, we discuss the (...) |
|
|
Let K be a family of structures, closed under isomorphism, in a fixed computable language. We consider effective lists of structures from K such that every structure in K is isomorphic to exactly one structure on the list. Such a list is called a computable classification of K, up to isomorphism. Using the technique of Friedberg enumeration, we show that there is a computable classification of the family of computable algebraic fields and that with a 0'-oracle, we can obtain similar (...) |
|
|
We investigate properties of universal numberings of finite families of d.c.e. sets. We show different cases of finite families of d.c.e. sets for which there is a universal numbering and for which there is not. |
|
|
A metric space is said to be locally non-compact if every neighborhood contains a sequence that is eventually bounded away from every element of the space, hence contains no accumulation point. We show within recursive mathematics that a nonvoid complete metric space is locally non-compact iff it is without isolated points.The result has an interesting consequence in computable analysis: If a complete metric space has a computable witness that it is without isolated points, then every neighborhood contains a computable sequence (...) |
|
|
On countable structures computability is usually introduced via numberings. For uncountable structures whose cardinality does not exceed the cardinality of the continuum the same can be done via representations. Which representations are appropriate for doing real number computations? We show that with respect to computable equivalence there is one and only one equivalence class of representations of the real numbers which make the basic operations and the infinitary normed limit operator computable. This characterizes the real numbers in terms of the (...) |
|
|
Limitwise monotonic sets and functions constitute an important tool in computable structure theory. We investigate limitwise monotonic numberings. A numbering ν of a family is limitwise monotonic (l.m.) if every set is the range of a limitwise monotonic function, uniformly in k. The set of all l.m. numberings of S induces the Rogers semilattice. The semilattices exhibit a peculiar behavior, which puts them in‐between the classical Rogers semilattices (for computable families) and Rogers semilattices of ‐computable families. We show that every (...) |
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-6f97f49787-r597v uwo