0
$\begingroup$

Is there a combinatorially defined, nonempty effectively closed set $Q\subseteq 2^\omega$ such that all members of $Q$ are incomputable?

Combinatorially defined means that the definition of $Q$ does not involve any logic or computability theoretic notion. This excludes those effectively closed sets defined by PA degree, 1-randomness etc. Effectively closed set means the set $\{\rho\in 2^{<\omega}:[\rho]\cap Q=\emptyset\}$ is comuptably enumerable.

$\endgroup$
5
  • $\begingroup$ What does "combinatorially defined" mean? $\endgroup$ Commented Feb 26, 2020 at 16:02
  • $\begingroup$ It's explained @NoahSchweber. I'd also be happy to see an algebrically defined one~ $\endgroup$
    – Jiayi Liu
    Commented Feb 27, 2020 at 4:21
  • $\begingroup$ It doesn't seem to have anything to do with combinatorics - at present, all you're asking for is a non-"logic-y" example? $\endgroup$ Commented Feb 27, 2020 at 4:27
  • $\begingroup$ You can think of it that way. A "naturally" defined (for non logicians) $Q$. $\endgroup$
    – Jiayi Liu
    Commented Feb 27, 2020 at 13:35
  • $\begingroup$ I think it's a very interesting question. So basically is there something like Hilbert's 10th problem but as a set of reals instead of a set of integers. $\endgroup$ Commented Feb 27, 2020 at 13:54

1 Answer 1

3
$\begingroup$

The answer is yes.

Let me first describe a general method. Fix any c.e. computably inseparable pair $A$ and $B$. These are computably enumerable sets having no computable separation. There are diverse examples of such pairs of sets. Let $Q$ be the set of sequences $s$ separating $A$ and $B$, that is, for which $s(n)=1$ whenever $n\in A$ and $s(n)=0$ whenever $n\in B$. By assumption, there are no computable elements of $Q$. The set is effectively closed, because we can recognize nonmembers of $Q$ in finite time, simply by waiting for the elements of $A$ and $B$ to emerge and observing whether the membership requirements for $Q$ were followed or not.

Next, let me complete the answer by mentioning that there are numerous examples of computably inseparable pairs, including examples that I would think of as combinatorial.

  • Let $A$ be the set of Turing machine programs $p$ that halt on empty input with output $0$, and let $B$ be the set of programs that do so with output $1$.

  • Let $A$ be the set of theorems of PA and $B$ the set of negations of theorems of PA.

  • Let $A$ be the set of finite Game-of-Life positions that lead eventually to square $1$ turning on before square $2$ (using two fixed squares that makes this example work) and $B$ the set of positions in which $2$ turns on before $1$. This is computably inseparable, because Game-of-Life can simulate Turing machines, and we can pick the squares so that square $1$ corresponds to accept and square $2$ corresponds to reject.

  • For a particular finite set $\Gamma$ of rational polygonal tiles (or Wang tiles, if you prefer), let $A$ be the set of finite additional possible tiles of a particular form, which admit no tiling of the plane when added to $\Gamma$, and let $B$ be the set of such augmented tile sets of another particular form that admit no tiling when added to $\Gamma$. Since the tiling problem is Turing complete, I can make an example of this form, where the additional tiles of $A$ correspond to halting with output $1$ and those of $B$ correspond to halting with output $0$, but there is no need to talk about Turing computation to describe the actual tiles.

  • Let $A$ be the set of Post correspondence problems (of a certain form) that admit a solution ending with the symbol $0$ and $B$ the set of such problems admitting a solution ending with the symbol $1$. Since the Post correspondence problem can simulate Turing computation, this example can be created from the first example above.

I think one could create many more examples of a combinatorial nature, simply using the fact that combinatorial questions are often Turing complete and can encode Turing computations.

$\endgroup$
8
  • 2
    $\begingroup$ I suspect that this won't match the OP's criterion of "combinatorially defined" (although it's unclear what that means right now). $\endgroup$ Commented Feb 26, 2020 at 18:35
  • $\begingroup$ It seems perfectly combinatorial to my way of thinking, since it is about the nature of a finitary discrete process. I suppose one could ask what are the most natural computably inseparable sets? Another good example is where A is the set of theorems of PA (or consistent c.e. theory of arithmetic) and B is the set of negations of theorems. $\endgroup$ Commented Feb 26, 2020 at 20:22
  • 2
    $\begingroup$ I mean, I would agree, but I find all computability to be combinatorial. :) $\endgroup$ Commented Feb 26, 2020 at 20:44
  • 1
    $\begingroup$ I don't object - I didn't downvote after all - I only meant to get ahead of what I suspect will be the OP's response. $\endgroup$ Commented Feb 26, 2020 at 21:05
  • 1
    $\begingroup$ I'm guessing that "naturally occurring in mathematics" can substitute for "combinatorial". In that case, arguably separating A and B is not natural, since what we really want to do is compute A and B themselves. $\endgroup$ Commented Feb 28, 2020 at 1:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .