On a metric generalization of the tt-degrees and effective dimension theory

DOI10.1017/JSL.2019.18zbMATH Open1455.03055arXiv1803.03753OpenAlexW2963018489WikidataQ128224671 ScholiaQ128224671MaRDI QIDQ5222533FDOQ5222533

Authors: Takayuki Kihara 

Publication date: 6 April 2020

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Abstract: In this article, we study an analogue of $tt$-reducibility for points in computable metric spaces. We characterize the notion of the metric $tt$-degree in the context of first-level Borel isomorphism. Then, we study this concept from the perspectives of effective topological dimension theory and of effective fractal dimension theory.

Full work available at URL: https://arxiv.org/abs/1803.03753

Recommendations

• Effective dimension in some general metric spaces
• Effective Hausdorff dimension in general metric spaces
• Effective zero-dimensionality for computable metric spaces
• Computability on computable metric spaces
• Constructive Dimension and Weak Truth-Table Degrees

zbMATH Keywords

effective dimensioncomputable metric spaceBorel isomorphismSchnorr dimensiontruth table degree

Mathematics Subject Classification ID

Computation over the reals, computable analysis (03D78) Descriptive set theory (topological aspects of Borel, analytic, projective, etc. sets) (54H05) Models of arithmetic and set theory (03C62) Other degrees and reducibilities in computability and recursion theory (03D30)

Cites Work

• Algorithmic randomness and complexity.
• Title not available (Why is that?)
• The infinite-dimensional topology of function spaces
• Title not available (Why is that?)
• Title not available (Why is that?)
• Unified characterizations of lowness properties via Kolmogorov complexity
• Dimension theory and forcing
• On Borel mappings and \(\sigma\)-ideals generated by closed sets
• Reconciling Data Compression and Kolmogorov Complexity
• Classical recursion theory. The theory of functions and sets of natural numbers
• Title not available (Why is that?)
• First level Borel functions and isomorphisms
• Piece-wise closed functions
• Dimensions of Points in Self-Similar Fractals
• Turing Computability
• Title not available (Why is that?)
• Title not available (Why is that?)
• Degrees of unsolvability of continuous functions
• Approximately differentiable functions: The r-topology
• On scatteredly continuous maps between topological spaces
• Randomness for non-computable measures
• Computable metrization
• Bounding the dimension of points on a line
• A relationship between packing and topological dimensions
• Characterizing the continuous degrees
• Borel isomorphisms at the first level—I
• Dimension spectra of lines
• Baire isomorphisms at the first level and dimension
• Title not available (Why is that?)
• Point Degree Spectra of Represented Spaces
• Uniform Kurtz randomness
• Borel isomorphisms at the first level, II
• Turing degrees in Polish spaces and decomposability of Borel functions
• Effective zero-dimensionality for computable metric spaces

Cited In (3)

• \(K\)-triviality in computable metric spaces
• The metric dimension of sunflower, \(t\)-fold wheel, and \(K_1+(P_n \odot P_m)\)
• Point Degree Spectra of Represented Spaces

This page was built for publication: On a metric generalization of the \(tt\)-degrees and effective dimension theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5222533)