Skip to main content
added 26 characters in body
Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

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 possiblyfinite 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 tilessuch 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.

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 possibly additional tiles of a particular form, which admit no tiling of the plane when added to $\Gamma$, and let $B$ be the set of tiles 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.

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.

added 2158 characters in body
Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

YesThe answer is yes. 

Let $Q$ be the set of sequences that separateme first describe a fixedgeneral 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 as the set $A$pairs of programs that halt with outputsets. Let $0$ and$Q$ be the set $B$ of programs that halt with outputsequences $1$. There is no computable separation of$s$ separating $A$ and $B$, that is, for which $s(n)=1$ whenever $n\in A$ and so all elements of $Q$ are noncomputable$s(n)=0$ whenever $n\in B$. By assumption, butthere are no computable elements of $Q$. The set is effectively closed, because a finite sequence has no extension inwe can recognize nonmembers of $Q$ just in case it places a $0$finite time, simply by waiting for an elementthe elements of $A$ or aand $1$$B$ to emerge and observing whether the membership requirements for an element of $B$$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 possibly additional tiles of a particular form, which admit no tiling of the plane when added to $\Gamma$, and let $B$ be the set of tiles 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 this can be recognized in finite timeencode Turing computations.

Yes. Let $Q$ be the set of sequences that separate a fixed computably inseparable pair $A$ and $B$, such as the set $A$ of programs that halt with output $0$ and the set $B$ of programs that halt with output $1$. There is no computable separation of $A$ and $B$, and so all elements of $Q$ are noncomputable, but $Q$ is effectively closed, because a finite sequence has no extension in $Q$ just in case it places a $0$ for an element of $A$ or a $1$ for an element of $B$, and this can be recognized in finite time.

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 possibly additional tiles of a particular form, which admit no tiling of the plane when added to $\Gamma$, and let $B$ be the set of tiles 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.

added 3 characters in body
Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

Yes. Let $Q$ be the set of sequences that separate a fixed computably inseparable pair $A$ and $B$, such as the set $A$ of programs that halt with output $0$ and the set $B$ of programs that halt with output $1$. There is no computable separation of $A$ and $B$, and so all elements of $Q$ are noncomputable, but $Q$ is effectively closed, because a finite sequence has no extension in $Q$ just in case it places a $0$ for an element of $A$ or a $1$ for an element of $B$, and this can be recognized in finite time.

Yes. Let $Q$ be the set of sequences that separate a fixed computably inseparable pair $A$ and $B$, such as the set $A$ of programs that halt with output $0$ and the set $B$ of programs that halt with output $1$. There is no computable separation of $A$ and $B$, and so all elements of $Q$ are noncomputable, but $Q$ is effectively closed, because a finite sequence has no extension in $Q$ just in case it places a $0$ for an element of $A$ or a $1$ for an element of $B$, and this can recognized in finite time.

Yes. Let $Q$ be the set of sequences that separate a fixed computably inseparable pair $A$ and $B$, such as the set $A$ of programs that halt with output $0$ and the set $B$ of programs that halt with output $1$. There is no computable separation of $A$ and $B$, and so all elements of $Q$ are noncomputable, but $Q$ is effectively closed, because a finite sequence has no extension in $Q$ just in case it places a $0$ for an element of $A$ or a $1$ for an element of $B$, and this can be recognized in finite time.

Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k
Loading