Skip to main content
replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link

In this questionthis question the following observation was made:

Consider a sequence of boxes numbered 0, 1, ... each containing one real number. The real number cannot be seen unless the box is opened.

Define a play to be a series of steps followed by a guess. A step opens a set of boxes. A guess guesses the contents of an unopened box. A strategy is a rule that determines the steps and guess in a play, where each step or guess depends only on the values of the previously opened boxes of that play.

Then for every positive integer $k$, there is a set $S$ of $k$ strategies such that, for any sequence of (closed) boxes, there is at at most one strategy in $S$ that guesses incorrectly.

My question is this: Can $k$ be countably infinite (instead of a positive integer)? If not, is there a proof?

[Edit: the original question also asked whether $k$ can be uncountable; this was answered by Dan Turetsky in the negative in comments].

The best I have been able to show is that, if the function $f:\mathbb{N}\to\mathbb{R}$ defined by the contents of the initial sequence of boxes is recursive (viewing elements of $\mathbb{R}$ as binary sequences), then $k$ can be countably infinite. To see this, call a subset $X$ of $\mathbb{N}$ signature if two recursive functions on $\mathbb{N}$ that eventually agree on $X$ also eventually agree on $\mathbb{N}$. (Two functions "eventually agree" if they differ in finitely many places). Call two Turing Machines equivalent if their associated functions on $\mathbb{N}$ are equivalent (that is, eventually agree). A diagonalization argument on the class representatives of the Turing Machines yields an infinite partition $U$ of $\mathbb{N}$ into signature subsets. The $i$'th strategy in $S$ first opens all the boxes whose indices are not in the $i$'th element $U_i$ of $U$, determines the class representative Turing Machine T that generates the resulting values on the opened boxes for boxes whose indices are greater than $N$ (for some positive $N$), and guesses that a box with index greater than $N$ and in $U_i$ has a value specified by $T$.

However, I have not been able to modify this for the non-computable case.

In this question the following observation was made:

Consider a sequence of boxes numbered 0, 1, ... each containing one real number. The real number cannot be seen unless the box is opened.

Define a play to be a series of steps followed by a guess. A step opens a set of boxes. A guess guesses the contents of an unopened box. A strategy is a rule that determines the steps and guess in a play, where each step or guess depends only on the values of the previously opened boxes of that play.

Then for every positive integer $k$, there is a set $S$ of $k$ strategies such that, for any sequence of (closed) boxes, there is at at most one strategy in $S$ that guesses incorrectly.

My question is this: Can $k$ be countably infinite (instead of a positive integer)? If not, is there a proof?

[Edit: the original question also asked whether $k$ can be uncountable; this was answered by Dan Turetsky in the negative in comments].

The best I have been able to show is that, if the function $f:\mathbb{N}\to\mathbb{R}$ defined by the contents of the initial sequence of boxes is recursive (viewing elements of $\mathbb{R}$ as binary sequences), then $k$ can be countably infinite. To see this, call a subset $X$ of $\mathbb{N}$ signature if two recursive functions on $\mathbb{N}$ that eventually agree on $X$ also eventually agree on $\mathbb{N}$. (Two functions "eventually agree" if they differ in finitely many places). Call two Turing Machines equivalent if their associated functions on $\mathbb{N}$ are equivalent (that is, eventually agree). A diagonalization argument on the class representatives of the Turing Machines yields an infinite partition $U$ of $\mathbb{N}$ into signature subsets. The $i$'th strategy in $S$ first opens all the boxes whose indices are not in the $i$'th element $U_i$ of $U$, determines the class representative Turing Machine T that generates the resulting values on the opened boxes for boxes whose indices are greater than $N$ (for some positive $N$), and guesses that a box with index greater than $N$ and in $U_i$ has a value specified by $T$.

However, I have not been able to modify this for the non-computable case.

In this question the following observation was made:

Consider a sequence of boxes numbered 0, 1, ... each containing one real number. The real number cannot be seen unless the box is opened.

Define a play to be a series of steps followed by a guess. A step opens a set of boxes. A guess guesses the contents of an unopened box. A strategy is a rule that determines the steps and guess in a play, where each step or guess depends only on the values of the previously opened boxes of that play.

Then for every positive integer $k$, there is a set $S$ of $k$ strategies such that, for any sequence of (closed) boxes, there is at at most one strategy in $S$ that guesses incorrectly.

My question is this: Can $k$ be countably infinite (instead of a positive integer)? If not, is there a proof?

[Edit: the original question also asked whether $k$ can be uncountable; this was answered by Dan Turetsky in the negative in comments].

The best I have been able to show is that, if the function $f:\mathbb{N}\to\mathbb{R}$ defined by the contents of the initial sequence of boxes is recursive (viewing elements of $\mathbb{R}$ as binary sequences), then $k$ can be countably infinite. To see this, call a subset $X$ of $\mathbb{N}$ signature if two recursive functions on $\mathbb{N}$ that eventually agree on $X$ also eventually agree on $\mathbb{N}$. (Two functions "eventually agree" if they differ in finitely many places). Call two Turing Machines equivalent if their associated functions on $\mathbb{N}$ are equivalent (that is, eventually agree). A diagonalization argument on the class representatives of the Turing Machines yields an infinite partition $U$ of $\mathbb{N}$ into signature subsets. The $i$'th strategy in $S$ first opens all the boxes whose indices are not in the $i$'th element $U_i$ of $U$, determines the class representative Turing Machine T that generates the resulting values on the opened boxes for boxes whose indices are greater than $N$ (for some positive $N$), and guesses that a box with index greater than $N$ and in $U_i$ has a value specified by $T$.

However, I have not been able to modify this for the non-computable case.

added 21 characters in body
Source Link
user44653
  • 271
  • 1
  • 6

In this question the following observation was made:

Consider a sequence of boxes numbered 0, 1, ... each containing one real number. The real number cannot be seen unless the box is opened.

Define a $play$play to be a series of $steps$steps followed by a guess. Each step eitherA (a)step opens a subsetset of boxes; orboxes. A (b) if it is the last step,guess guesses the contents of an unopened box. A A strategy is a rule that determines the steps and guess in a play, where each step or guess depends only on the values inof the previously opened boxes of that strategyplay.

Then for every positive integer $k$, there is a set $S$ of $k$ strategies such that, for any initial sequence of (closed) boxes, there is at at most one strategy in $S$ that guesses incorrectly.

My question is this: Can $k$ be countably infinite (instead of a positive integer)? If not, is there somea proof that k cannot be countably infinite? For that matter, if k is uncountable, can

[Edit: the number of wrong guessesoriginal question also asked whether $k$ can be bounded?uncountable; this was answered by Dan Turetsky in the negative in comments].

The best I have been able to show is that, if the function $f:\mathbb{N}\to\mathbb{R}$ defined by the contents of the initial sequence of boxes is recursive (viewing elements of $\mathbb{R}$ as binary sequences), then $k$ can be countably infinite. To see this, call a subset $X$ of $\mathbb{N}$ signature if two recursive functions on $\mathbb{N}$ that eventually agree on $X$ also eventually agree on $\mathbb{N}$. (Two functions "eventually agree" if they differ in finitely many places). Call two Turing Machines equivalent if their associated functions on $\mathbb{N}$ are equivalent (that is, eventually agree). A diagonalization argument on the class representatives of the Turing Machines yields an infinite partition $U$ of $\mathbb{N}$ into signature subsets. The $i$'th strategy in $S$ first opens all the boxes whose indices are not in the $i$'th element $U_i$ of $U$, determines the class representative Turing Machine T that generates the resulting values on the opened boxes for boxes whose indices are greater than $N$ (for some positive $N$), and guesses that a box with index greater than $N$ and in $U_i$ has a value specified by $T$.

However, I have not been able to modify this for the non-computable case.

In this question the following observation was made:

Consider a sequence of boxes numbered 0, 1, ... each containing one real number. The real number cannot be seen unless the box is opened.

Define a $play$ to be a series of $steps$. Each step either (a) opens a subset of boxes; or (b) if it is the last step, guesses the contents of an unopened box. A strategy is a rule that determines the steps in a play, where each step depends only on the values in the previously opened boxes of that strategy.

Then for every positive integer $k$, there is a set $S$ of $k$ strategies such that, for any initial sequence of boxes, there is at at most one strategy in $S$ that guesses incorrectly.

My question is this: Can $k$ be countably infinite (instead of a positive integer)? If not, is there some proof that k cannot be countably infinite? For that matter, if k is uncountable, can the number of wrong guesses be bounded?

The best I have been able to show is that, if the function $f:\mathbb{N}\to\mathbb{R}$ defined by the contents of the initial sequence of boxes is recursive (viewing elements of $\mathbb{R}$ as binary sequences), then $k$ can be countably infinite. To see this, call a subset $X$ of $\mathbb{N}$ signature if two recursive functions on $\mathbb{N}$ that eventually agree on $X$ also eventually agree on $\mathbb{N}$. (Two functions "eventually agree" if they differ in finitely many places). Call two Turing Machines equivalent if their associated functions on $\mathbb{N}$ are equivalent (that is, eventually agree). A diagonalization argument on the class representatives of the Turing Machines yields an infinite partition $U$ of $\mathbb{N}$ into signature subsets. The $i$'th strategy in $S$ first opens all the boxes whose indices are not in the $i$'th element $U_i$ of $U$, determines the class representative Turing Machine T that generates the resulting values on the opened boxes for boxes whose indices are greater than $N$ (for some positive $N$), and guesses that a box with index greater than $N$ and in $U_i$ has a value specified by $T$.

However, I have not been able to modify this for the non-computable case.

In this question the following observation was made:

Consider a sequence of boxes numbered 0, 1, ... each containing one real number. The real number cannot be seen unless the box is opened.

Define a play to be a series of steps followed by a guess. A step opens a set of boxes. A guess guesses the contents of an unopened box. A strategy is a rule that determines the steps and guess in a play, where each step or guess depends only on the values of the previously opened boxes of that play.

Then for every positive integer $k$, there is a set $S$ of $k$ strategies such that, for any sequence of (closed) boxes, there is at at most one strategy in $S$ that guesses incorrectly.

My question is this: Can $k$ be countably infinite (instead of a positive integer)? If not, is there a proof?

[Edit: the original question also asked whether $k$ can be uncountable; this was answered by Dan Turetsky in the negative in comments].

The best I have been able to show is that, if the function $f:\mathbb{N}\to\mathbb{R}$ defined by the contents of the initial sequence of boxes is recursive (viewing elements of $\mathbb{R}$ as binary sequences), then $k$ can be countably infinite. To see this, call a subset $X$ of $\mathbb{N}$ signature if two recursive functions on $\mathbb{N}$ that eventually agree on $X$ also eventually agree on $\mathbb{N}$. (Two functions "eventually agree" if they differ in finitely many places). Call two Turing Machines equivalent if their associated functions on $\mathbb{N}$ are equivalent (that is, eventually agree). A diagonalization argument on the class representatives of the Turing Machines yields an infinite partition $U$ of $\mathbb{N}$ into signature subsets. The $i$'th strategy in $S$ first opens all the boxes whose indices are not in the $i$'th element $U_i$ of $U$, determines the class representative Turing Machine T that generates the resulting values on the opened boxes for boxes whose indices are greater than $N$ (for some positive $N$), and guesses that a box with index greater than $N$ and in $U_i$ has a value specified by $T$.

However, I have not been able to modify this for the non-computable case.

edited title
Link
user44653
  • 271
  • 1
  • 6

Hidden boxes puzzle bounds Can an infinite number of mathematicians guess the number in a box with only one error?

Source Link
user44653
  • 271
  • 1
  • 6
Loading