𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Turing degrees of points in computable topology

✍ Scribed by Iraj Kalantari; Larry Welch


Publisher
John Wiley and Sons
Year
2008
Tongue
English
Weight
169 KB
Volume
54
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis


Abstract

This paper continues our study of computable point‐free topological spaces and the metamathematical points in them. For us, a point is the intersection of a sequence of basic open sets with compact and nested closures. We call such a sequence a sharp filter. A function f~F~ from points to points is generated by a function F from basic open sets to basic open sets such that sharp filters map to sharp filters. We restrict our study to functions that have at least all computable points in their domains.

We follow Turing's approach in stating that a point is computable if it is the limit of a computable sharp filter; we then define the Turing degree Deg(x) of a general point x in an analogous way. Because of the vagaries of the definition, a result of J. Miller applies and we note that not all points in all our spaces have Turing degrees; but we also show a certain class of points do. We further show that in ℝ^n^ all points have Turing degrees and that these degrees are the same as the classical Turing degrees of points defined by other researchers.

We also prove the following: For a point x that has a Turing degree and lies either on a computable tree T or in the domain of a computable function f~F~, there is a sharp filter on T or in dom(F) converging to x and with the same Turing degree as x. Furthermore, all possible Turing degrees occur among the degrees of such points for a given computable function f~F~ or a complete, computable, binary tree T. For each x ∈ dom(f~F~) for which x and f~F~ (x) have Turing degrees, Deg(f~F~ (x)) ≀ Deg(x). Finally, the Turing degrees of the sharp filters convergent to a given x are closed upward in the partial order of all Turing degrees. (Β© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)


πŸ“œ SIMILAR VOLUMES


On the complexity of categoricity in com
✍ Walker M. White πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 192 KB

## Abstract We investigate the computational complexity the class of Γ‐categorical computable structures. We show that hyperarithmetic categoricity is Ξ ^1^~1~‐complete, while computable categoricity is Ξ ^0^~4~‐hard. (Β© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)

N Degrees of Separation: Influences of D
✍ Art Lew πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 71 KB

Bellman's dynamic programming methodology can be applied to a wide range of computer science optimization problems. Some of these applications are briefly reviewed here. This work has led to advances in numerous other areas of computer science, including programming languages, computer simulation, a

Managing the Topological Expansion of Co
✍ Debashis Saha; Amitava Mukherjee πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 453 KB πŸ‘ 2 views

This article describes a subgradient-based near-optimal heuristic algorithm designed for minimizing the search of links that need to be added to an existing telecommunications network to enhance the survivability and routability of the network.

On the Detection of Unusual Points in Re
✍ Prof. S. R. Paul πŸ“‚ Article πŸ“… 1987 πŸ› John Wiley and Sons 🌐 English βš– 284 KB πŸ‘ 2 views

Some prooednws, based on studentized residuals and the diagonal elements of the 'hat' matrix, for the detection of unusual points in regreeeion are discussed. Them procedurea are quite simple but effective to uncover unusual structure of the date. Some examplee are given.