Two Puzzles in Recursion Theory: Verbose Sets and Terse Sets

Let K be the set of all n such that the nth 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.

I read about this first in Piergiorgio Odifreddi’s book “Classical Recursion Theory, Volume 1.”

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_1th Turing machine simulates the x_1th, x_2th and x_3th 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_1th, x_2th, and x_3th 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.

About these ads

2 Comments

Filed under Puzzles

2 responses to “Two Puzzles in Recursion Theory: Verbose Sets and Terse Sets

  1. 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. 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 nth Turing machine, and let the g(n)th Turing machine first write n on the input tape and then simulate the nth Turing machine.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s