数学学报：英文版, ISSN 1439-8516, 2017, Volume 33, Issue 9, pp. 1184 - 1192

In this paper, we prove that if a c.e. Turing degree d is non-low2, then there are two left-c.e, reals β0,β1 in d, such that, if β0 is wtt-reducible to a...

03D30 | computable Lipschitz (cl) reducibility | complex | 03D25 | Mathematics, general | Mathematics | 03D32 | Non-low 2 | 68Q30 | Non-low | RANDOMNESS | MATHEMATICS | MATHEMATICS, APPLIED

03D30 | computable Lipschitz (cl) reducibility | complex | 03D25 | Mathematics, general | Mathematics | 03D32 | Non-low 2 | 68Q30 | Non-low | RANDOMNESS | MATHEMATICS | MATHEMATICS, APPLIED

Journal Article

Monatshefte für Mathematik, ISSN 0026-9255, 2/2018, Volume 185, Issue 2, pp. 167 - 188

We generalize the classical theorem by Jarnik and Besicovitch on the irrationality exponents of real numbers and Hausdorff dimension and show that the two...

Diophantine approximation | Mathematics, general | Cantor sets | Mathematics | 11J83 | 03D32 | 11J82 | Effective Hausdorff dimension | MATHEMATICS | ORDER | KOLMOGOROV COMPLEXITY | APPROXIMATION | NUMBERS | SETS

Diophantine approximation | Mathematics, general | Cantor sets | Mathematics | 11J83 | 03D32 | 11J82 | Effective Hausdorff dimension | MATHEMATICS | ORDER | KOLMOGOROV COMPLEXITY | APPROXIMATION | NUMBERS | SETS

Journal Article

Mathematical Logic Quarterly, ISSN 0942-5616, 05/2013, Volume 59, Issue 3, pp. 206 - 218

We investigate a directed metric on the space of infinite binary sequences defined by...

Metric | Hausdorff | Packing Dimension | Kolmogorov Complexity | msc 03D32

Metric | Hausdorff | Packing Dimension | Kolmogorov Complexity | msc 03D32

Journal Article

Notre Dame Journal of Formal Logic, ISSN 0029-4527, 2010, Volume 51, Issue 2, pp. 279 - 290

We study the Turing degrees which contain a real of effective packing dimension one. Downey and Greenberg showed that a c.e. degree has effective packing...

MATHEMATICS | effective dimension | PHILOSOPHY | Turing degrees | 03D32

MATHEMATICS | effective dimension | PHILOSOPHY | Turing degrees | 03D32

Journal Article

5.
Full Text
Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs

Archive for Mathematical Logic, ISSN 0933-5846, 8/2015, Volume 54, Issue 5, pp. 615 - 629

Miller (J Symb Log 69(3):907–913, 2004, http://projecteuclid.org/euclid.jsl/1096901774 ) and independently Nies et al. (J Symb Log 70(2):515–535, 2005) gave a...

Martin–Löf randomness | Algebra | 2-randomness | Randomness deficiency | Kolmogorov complexity | Computableanalysis | Mathematics, general | Mathematics | 03D32 | Mathematical Logic and Foundations | RANDOMNESS | MATHEMATICS | Martin-Lof randomness | LOGIC

Martin–Löf randomness | Algebra | 2-randomness | Randomness deficiency | Kolmogorov complexity | Computableanalysis | Mathematics, general | Mathematics | 03D32 | Mathematical Logic and Foundations | RANDOMNESS | MATHEMATICS | Martin-Lof randomness | LOGIC

Journal Article

The Journal of Symbolic Logic, ISSN 0022-4812, 9/2013, Volume 78, Issue 3, pp. 824 - 836

We prove that RCA₀ + $RRT_2^3$ Y̵ ACA₀ where $RRT_2^3$ is the Rainbow Ramsey Theorem for 2-bounded colorings of triples. This reverse mathematical result is...

Reverse mathematics | Mathematical theorems | Logical theorems | Axioms | Mathematical induction | Mathematical logic | Recursion theory | Computability | Arithmetic | MATHEMATICS | LOGIC | 03B30, 03F35, 03D32, 03D80

Reverse mathematics | Mathematical theorems | Logical theorems | Axioms | Mathematical induction | Mathematical logic | Recursion theory | Computability | Arithmetic | MATHEMATICS | LOGIC | 03B30, 03F35, 03D32, 03D80

Journal Article

Notre Dame Journal of Formal Logic, ISSN 0029-4527, 2014, Volume 55, Issue 1, pp. 63 - 73

We show that being low for difference tests is the same as being computable and therefore lowness for difference tests is not the same as lowness for...

Difference tests | Lowness | Difference randomness | Algorithmic randomness | lowness | RANDOMNESS | MATHEMATICS | algorithmic randomness | PHILOSOPHY | difference tests | LOGIC | difference randomness | 03D32

Difference tests | Lowness | Difference randomness | Algorithmic randomness | lowness | RANDOMNESS | MATHEMATICS | algorithmic randomness | PHILOSOPHY | difference tests | LOGIC | difference randomness | 03D32

Journal Article

Notre Dame Journal of Formal Logic, ISSN 0029-4527, 2009, Volume 50, Issue 4, pp. 445 - 452

We prove that superhigh sets can be jump traceable, answering a question of Cole and Simpson. On the other hand, we show that such sets cannot be weakly...

Truth-table degrees | Highness and lowness notions | Algorithmic randomness | Turing degrees | MATHEMATICS | EVERYWHERE DOMINATION | algorithmic randomness | highness and lowness notions | PHILOSOPHY | truth-table degrees | Mathematics - Logic | 03D28 | 03D32 | 68Q30

Truth-table degrees | Highness and lowness notions | Algorithmic randomness | Turing degrees | MATHEMATICS | EVERYWHERE DOMINATION | algorithmic randomness | highness and lowness notions | PHILOSOPHY | truth-table degrees | Mathematics - Logic | 03D28 | 03D32 | 68Q30

Journal Article

NOTRE DAME JOURNAL OF FORMAL LOGIC, ISSN 0029-4527, 2016, Volume 57, Issue 1, pp. 73 - 93

This paper presents a refinement of a result by Conidis, who proved that there is a real X of effective packing dimension 0 < alpha < 1 which cannot compute...

MATHEMATICS | complexity | KOLMOGOROV COMPLEXITY | effective packing dimension | pruned clumpy trees | INFORMATION | PHILOSOPHY | limit-computable approximation | LOGIC | EFFECTIVE HAUSDORFF DIMENSION | 03D32 | 68Q30

MATHEMATICS | complexity | KOLMOGOROV COMPLEXITY | effective packing dimension | pruned clumpy trees | INFORMATION | PHILOSOPHY | limit-computable approximation | LOGIC | EFFECTIVE HAUSDORFF DIMENSION | 03D32 | 68Q30

Journal Article

Notre Dame Journal of Formal Logic, ISSN 0029-4527, 2014, Volume 55, Issue 1, pp. 1 - 10

We study pairs of reals that are mutually Martin-Lof random with respect to a common, not necessarily computable probability measure. We show that a...

C.e. sets | PA degrees | Van Lambalgen's theorem | Independence | Algorithmic randomness | MATHEMATICS | algorithmic randomness | PHILOSOPHY | c.e. sets | independence | van Lambalgen's theorem | LOGIC | Mathematics - Logic | 03D32 | van Lambalgen’s theorem

C.e. sets | PA degrees | Van Lambalgen's theorem | Independence | Algorithmic randomness | MATHEMATICS | algorithmic randomness | PHILOSOPHY | c.e. sets | independence | van Lambalgen's theorem | LOGIC | Mathematics - Logic | 03D32 | van Lambalgen’s theorem

Journal Article

Archive for Mathematical Logic, ISSN 0933-5846, 8/2014, Volume 53, Issue 5, pp. 525 - 538

We introduce a notion of description for infinite sequences and their sets, and a corresponding notion of complexity. We show that for strict process machines,...

Algebra | Mathematics, general | Mathematics | Process complexity | 03D32 | Mathematical Logic and Foundations | Computability | Algorithmic randomness | MATHEMATICS | SEQUENCES | DIMENSION | LOGIC | Machinery | Magneto-electric machines | Logic | Computational mathematics | Mathematical logic | Sequences | Archives | Complexity

Algebra | Mathematics, general | Mathematics | Process complexity | 03D32 | Mathematical Logic and Foundations | Computability | Algorithmic randomness | MATHEMATICS | SEQUENCES | DIMENSION | LOGIC | Machinery | Magneto-electric machines | Logic | Computational mathematics | Mathematical logic | Sequences | Archives | Complexity

Journal Article

Frontiers of Mathematics in China, ISSN 1673-3452, 12/2014, Volume 9, Issue 6, pp. 1309 - 1323

We study the strength of some combinatorial principles weaker than Ramsey theorem for pairs over RCA0. First, we prove that Rainbow Ramsey theorem for pairs...

thin set | Reverse mathematics | Erdős-Moser theorem | 03D80 | Mathematics, general | free set | 03F35 | Mathematics | 03D32 | Rainbow Ramsey theorem | Erdo{double acute}s-Moser theorem

thin set | Reverse mathematics | Erdős-Moser theorem | 03D80 | Mathematics, general | free set | 03F35 | Mathematics | 03D32 | Rainbow Ramsey theorem | Erdo{double acute}s-Moser theorem

Journal Article

Archive for Mathematical Logic, ISSN 0933-5846, 2/2014, Volume 53, Issue 1, pp. 1 - 10

Polynomial clone reducibilities are generalizations of the truth-table reducibilities. A polynomial clone is a set of functions over a finite set X that is...

03D30 | Algebra | Turing reducibility | Polynomial clones | Mathematics, general | Mathematics | 03D32 | Mathematical Logic and Foundations | Computability | Algorithmic randomness | 68Q30 | MATHEMATICS | LOGIC | Cloning | Algorithms | Polynomials | Logic | Mathematical analysis

03D30 | Algebra | Turing reducibility | Polynomial clones | Mathematics, general | Mathematics | 03D32 | Mathematical Logic and Foundations | Computability | Algorithmic randomness | 68Q30 | MATHEMATICS | LOGIC | Cloning | Algorithms | Polynomials | Logic | Mathematical analysis

Journal Article

Archive for Mathematical Logic, ISSN 0933-5846, 11/2013, Volume 52, Issue 7, pp. 847 - 869

Let a trace be a computably enumerable set of natural numbers such that $${V^{[m]} = \{n : \langle n, m\rangle \in V \}}$$ V [ m ] = { n : 〈 n , m 〉 ∈ V } is...

Algebra | Traces | Lattices | 03D25 | Mathematics, general | Mathematics | Computably enumerable sets | 03D32 | Mathematical Logic and Foundations | Algorithmic randomness | 03G10 | MATHEMATICS | LOGIC | Mathematical functions | Algorithms | Lattice theory | Mathematical analysis

Algebra | Traces | Lattices | 03D25 | Mathematics, general | Mathematics | Computably enumerable sets | 03D32 | Mathematical Logic and Foundations | Algorithmic randomness | 03G10 | MATHEMATICS | LOGIC | Mathematical functions | Algorithms | Lattice theory | Mathematical analysis

Journal Article

Foundations of Computational Mathematics, ISSN 1615-3375, 4/2012, Volume 12, Issue 2, pp. 229 - 262

Let us assume that f is a continuous function defined on the unit ball of ℝ d , of the form f(x)=g(Ax), where A is a k×d matrix and g is a function of k...

Stability bounds for invariant subspaces of singular value decompositions | Economics general | 60G50 | Linear and Multilinear Algebras, Matrix Theory | 60B20 | Mathematics | High-dimensional function approximation | Numerical Analysis | Math Applications in Computer Science | Applications of Mathematics | 65D15 | Computer Science, general | 03D32 | Chernoff bounds for sums of positive semidefinite matrices | Compressed sensing | 68Q30 | MATHEMATICS | MATHEMATICS, APPLIED | RIDGE FUNCTIONS | APPROXIMATION | MATRICES | EQUATIONS | COMPUTER SCIENCE, THEORY & METHODS | Linear systems | Functions, Continuous | Approximation theory | Research | Algorithms | Approximation | Computation | Mathematical analysis | Mathematical models | Matrices | Sampling | Invariants

Stability bounds for invariant subspaces of singular value decompositions | Economics general | 60G50 | Linear and Multilinear Algebras, Matrix Theory | 60B20 | Mathematics | High-dimensional function approximation | Numerical Analysis | Math Applications in Computer Science | Applications of Mathematics | 65D15 | Computer Science, general | 03D32 | Chernoff bounds for sums of positive semidefinite matrices | Compressed sensing | 68Q30 | MATHEMATICS | MATHEMATICS, APPLIED | RIDGE FUNCTIONS | APPROXIMATION | MATRICES | EQUATIONS | COMPUTER SCIENCE, THEORY & METHODS | Linear systems | Functions, Continuous | Approximation theory | Research | Algorithms | Approximation | Computation | Mathematical analysis | Mathematical models | Matrices | Sampling | Invariants

Journal Article

Notre Dame Journal of Formal Logic, ISSN 0029-4527, 2011, Volume 52, Issue 1, pp. 95 - 112

The stable Ramsey's theorem for pairs has been the subject of numerous investigations in mathematical logic. We introduce a weaker form of it by restricting...

Effective measure theory | Reverse mathematics | Ramsey's theorem | MATHEMATICS | LOGIC | PHILOSOPHY | effective measure theory | reverse mathematics | 05D10 | 03D80 | 03F35 | 03D32

Effective measure theory | Reverse mathematics | Ramsey's theorem | MATHEMATICS | LOGIC | PHILOSOPHY | effective measure theory | reverse mathematics | 05D10 | 03D80 | 03F35 | 03D32

Journal Article

The Journal of Symbolic Logic, ISSN 0022-4812, 3/2013, Volume 78, Issue 1, pp. 334 - 344

A seminal theorem due to Weyl [14] states that if (an) is any sequence of distinct integers, then, for almost every x ∈ ℝ, the sequence (anx) is uniformly...

Integers | Mathematical intervals | Mathematical sequences | Real numbers | Logical theorems | Lebesgue measures | Randomness | Null set | Fractions | Absolute value | MATHEMATICS | LOGIC | Theorems (Mathematics) | Analysis | Numbers, Real | 03D32, 11K06

Integers | Mathematical intervals | Mathematical sequences | Real numbers | Logical theorems | Lebesgue measures | Randomness | Null set | Fractions | Absolute value | MATHEMATICS | LOGIC | Theorems (Mathematics) | Analysis | Numbers, Real | 03D32, 11K06

Journal Article

Notre Dame Journal of Formal Logic, ISSN 0029-4527, 2013, Volume 54, Issue 1, pp. 105 - 123

This paper continues the study of the metric topology on 2(N) that was introduced by S. Binns. This topology is induced by a directional metric where the...

Computability theory | Effective metric | Effective packing dimension | Kolmogorov complexity | Effective Hausdorff dimension | MATHEMATICS | complexity | effective Hausdorff dimension | effective metric | effective packing dimension | DIMENSION | PHILOSOPHY | Kolmogorov | LOGIC | computability theory | 03D32 | 68Q30

Computability theory | Effective metric | Effective packing dimension | Kolmogorov complexity | Effective Hausdorff dimension | MATHEMATICS | complexity | effective Hausdorff dimension | effective metric | effective packing dimension | DIMENSION | PHILOSOPHY | Kolmogorov | LOGIC | computability theory | 03D32 | 68Q30

Journal Article

Tohoku Mathematical Journal, Second Series, ISSN 0040-8735, 2011, Volume 63, Issue 4, pp. 489 - 517

The study of mass problems and Muchnik degrees was originally motivated by Kolmogorov's non-rigorous 1932 interpretation of intuitionism as a calculus of...

degrees of unsolvability | algorithmic randomness | resourse-bounded computational complexity | intuitionism | unsolvable problems | Kolmogorov complexity | Muchnik degrees | Mass problems | recursively enumerable degrees | symbolic dynamics | hyperarithmetical hierarchy | proof theory | Symbolic dynamics | Hyperarithmetical hierarchy | Degrees of unsolvability | Recursively enumerable degrees | Intuitionism | Proof theory | Resourse-bounded computational complexity | Unsolvable problems | Algorithmic randomness | NUMBERS | THEOREM | TILINGS | MATHEMATICS | MEDVEDEV | PSEUDO-JUMP OPERATORS | PI CLASSES

degrees of unsolvability | algorithmic randomness | resourse-bounded computational complexity | intuitionism | unsolvable problems | Kolmogorov complexity | Muchnik degrees | Mass problems | recursively enumerable degrees | symbolic dynamics | hyperarithmetical hierarchy | proof theory | Symbolic dynamics | Hyperarithmetical hierarchy | Degrees of unsolvability | Recursively enumerable degrees | Intuitionism | Proof theory | Resourse-bounded computational complexity | Unsolvable problems | Algorithmic randomness | NUMBERS | THEOREM | TILINGS | MATHEMATICS | MEDVEDEV | PSEUDO-JUMP OPERATORS | PI CLASSES

Journal Article

The Bulletin of Symbolic Logic, ISSN 1079-8986, 6/2013, Volume 19, Issue 2, pp. 199 - 215

A Martin-Löf random sequence is an infinite binary sequence with the property that every initial segment σ has prefix-free Kolmogorov complexity K(σ) at least...

Integers | Mathematical sequences | Legal proceedings | Lexicography | Real numbers | Randomness | Hausdorff dimensions | Mathematical logic | Mathematical functions | Oracles | phrases Kolmogorov complexity | subshifts | Martin-Löf randomness | MATHEMATICS | LOGIC | Martin-Lof randomness | Kolmogorov complexity | 03D28 | 03D32 | 68Q30

Integers | Mathematical sequences | Legal proceedings | Lexicography | Real numbers | Randomness | Hausdorff dimensions | Mathematical logic | Mathematical functions | Oracles | phrases Kolmogorov complexity | subshifts | Martin-Löf randomness | MATHEMATICS | LOGIC | Martin-Lof randomness | Kolmogorov complexity | 03D28 | 03D32 | 68Q30

Journal Article

No results were found for your search.

Cannot display more than 1000 results, please narrow the terms of your search.