论文标题
可计算性问题的组合等效性
The combinatorial equivalence of a computability theoretic question
论文作者
论文摘要
我们表明，米勒和所罗门的一个问题 - 是否存在着色$ c：d^{<ω} \ rightarrow k $，不承认$ c $ - 可变性的可变单词无限解决方案，等于一个自然的，非琐事的组合问题。组合问题询问是否有一个无限的整数序列，以使其每个初始段都满足拉姆斯类型的属性。这是已知的第一个可计算性理论问题，其等效于一个不关心复杂性概念的自然，非平凡的问题。事实证明，组合问题的否定是对Hales-Jewett定理的概括。我们解决了组合问题的一些特殊情况，并在某些特定参数上获得了Hales-Jewett定理的概括。
We show that a question of Miller and Solomon -- that whether there exists a coloring $c:d^{<ω}\rightarrow k$ 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.
