# Two Puzzles in Recursion Theory: Verbose Sets and Terse Sets

Let $K$ be the set of all $n$ such that the $n$th Turing machine halts. (For these puzzles, we will assume that Turing machines are always run on a blank initial state, i.e., they take no input.) Recall that $K$ is computably enumerable, but not decidable.

Puzzle #1. Describe a winning strategy for the following game: You are given three numbers $x_1, x_2, x_3$. You must correctly say for each number whether or not it is in $K$. You are allowed to ask (and receive a truthful answer to) two questions of the form “Is $n$ in K?” for any $n$.

Puzzle #2. Show that there is no winning strategy for the game which is the same as that in Puzzle #1 except you are given two numbers and may ask only one question. (Even stronger, show that if $S\subset \mathbb{N}$ is a set such that you can win that game, then $S$ must be decidable.)

These puzzles are special cases of more general questions answered in Terse sets, superterse sets, and verbose sets by Richard Beigel, William Gasarch, John Gill, and James Owings. I also suggest looking at Richard Beigel’s page of online papers, which has a lot of interesting stuff.

Answer #1. The first thing to do is to find out how many of $x_1, x_2, x_3$ are in $K$. To do this, let $n_1$ be such that the $n_1$th Turing machine simulates the $x_1$th, $x_2$th and $x_3$th Turing machines in parallel, and halts after any two of them halt.

By asking if $n_1$ is in $K$, you will find out either that there are two or more or that there are one or less of $x_1, x_2, x_3$ in $K$. Use a similar second question to find out exactly how many of $x_1, x_2, x_3$ are in $K$.

Once you know how many of $x_1, x_2, x_3$ are in $K$, just run the $x_1$th, $x_2$th, and $x_3$th Turing machines in parallel, and wait until all the ones that are going to halt do halt. Then you will know which of them are in $K$.

Answer #2. Suppose that you have a winning strategy, and I’ll show how to compute $S$. Let $f^x_{\text{no}}(x,y)$ be the function which, given $x$ and $y$, returns the guess for whether or not $x$ is in $S$, supposing that you received a “no” answer to whatever question your strategy decided to ask. Similarly define $f^y_{\text{no}}$, $f^x_{\text{yes}}$, and $f^y_{\text{yes}}$.

Either it is the case that for all $x$ there is a $y$ such that $f_{\text{no}}^x(x,y) = f_{\text{yes}}^x(x,y)$ or it isn’t. Suppose first that it is. Then given $x$, we may compute whether or not is in $S$ by searching for such a $y$ and computing $f_{\text{no}}^x(x,y)$ (which equals $f_{\text{yes}}^x(x,y)$). This must be the correct guess since either “yes” or “no” must be the correct answer to whatever question the strategy asked.

Now suppose that there is an $x$ such that for all $y$, $f_{\text{no}}^x(x,y)\ne f_{\text{yes}}^x(x,y)$. Since $x$ is just a single number, we can assume that we know whether or not it’s in $S$. Then, given any $y$, since $f_{\text{no}}^x(x,y)\ne f_{\text{yes}}^x(x,y)$ we know which of them is correct, hence we know whether “yes” or “no” is the correct answer to the question that the strategy would pose. Hence we can compute its correct guess as to whether or not $y$ is in $S$.

Additional Results. The paper linked above gives generalizations of both puzzles: You can find out whether any set of $2^n - 1$ numbers is in $K$ by asking $n$ questions (by the same strategy of determining how many of them are in $K$), and, for any $S$, if you can determine whether any set of $2^n$ numbers is in $S$ by asking $n$ questions then $S$ is decidable.

The authors call a set verbose if it is such that you can determine whether any set of $2^n -1$ numbers is in that set by asking $n$ questions. They call it terse if you need $n$ questions to determine whether or not $n$ numbers are in the set. They are show a number of interesting results about these, mainly along the lines that (very roughly) lots of both kinds exist, and in lots of different places.

## 2 thoughts on “Two Puzzles in Recursion Theory: Verbose Sets and Terse Sets”

1. Kenny Easwaran says:

You seem to switch from running Turing machines on their own codes as input in the posing of the puzzles to running Turing machines with no input in the solution – I assume that some sort of diagonalization or recursion theorem trickery means that this is an inessential point?

Also, it’s pretty funny that “Possible related posts” corrently includes “Strategies for Adjusting to Puberty?”

2. mkoconnor says:

Whoops, thanks. I fixed it so that the Turing machines in the posing of the problem also take no input.

You’re right, though, it’s inessential: Let $K_0$ be the set of Turing machines which halt with no input (say they start on a blank tape or something) and $K_1$ be the set of Turing machines which halt when given their own code as put. Then there are computable functions $f$ and $g$ such that for all $n$, $n\in K_0$ iff $f(n)\in K_1$ and $n\in K_1$ iff $g(n) \in K_0$.

There’s not even really any fancy trickery going on here. Just let the $f(n)$th Turing machine erase whatever input its given and then simulate the $n$th Turing machine, and let the $g(n)$th Turing machine first write $n$ on the input tape and then simulate the $n$th Turing machine.