The combinatorial equivalence of a computability theoretic question

arXiv2012.13588MaRDI QIDQ6356944FDOQ6356944

Authors: Lu Liu 

Publication date: 25 December 2020

Abstract: We show that a question of Miller and Solomon -- that whether there exists a coloring $c:d^{<omega}ightarrowk$ that does not admit a $c$-computable variable word infinite solution, is equivalent to a natural, nontrivial combinatorial question. The combinatorial question asked whether there is an infinite sequence of integers such that each of its initial segment satisfies a Ramsian type property. This is the first computability theoretic question known to be equivalent to a natural, nontrivial question that does not concern complexity notions. It turns out that the negation of the combinatorial question is a generalization of Hales-Jewett theorem. We solve some special cases of the combinatorial question and obtain a generalization of Hales-Jewett theorem on some particular parameters.

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80)

This page was built for publication: The combinatorial equivalence of a computability theoretic question

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