16
$\begingroup$

Two angels in heaven want to play a game. One of them comes up with an arbitrary, computable function from the integers to the integers. The other angel has to guess what it is. The second angel can either give an integer, which the first angel gives an input to their function and responds with the output, or a computable function, which the first angel says is either correct or incorrect. (The angels know an oracle who can tell them if two functions are equivalent in finite time.) The game continues until the second angel guesses the function.

The angels only want to play the game if they know it will end. It doesn't matter how long it takes because since they're in heaven, they'll have an infinite amount of time to do other things whenever the game ends. However, if the game will never end, the angels don't want to play it. What should they do? If they play the game, what is the smallest number of integers the second angel will need to check to be sure of eventually guessing the correct function, and what is the second angel's optimal strategy?

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ Seems like the angels should use a strategy similar to formulaic "guess the next number" sequences. Create a function that describes the sequence so far, guess it, and if wrong, ask for another number in the sequence and repeat. Game should end because the set of functions from integers to integers is countable. $\endgroup$
    – Trenin
    Commented Mar 9, 2015 at 16:34
  • 4
    $\begingroup$ @Trenin: The set of functions from integers to integers is uncountable as it is a superset of the set of functions from integers to $\{0,1\}$. We need to invoke a definition of computable to get a countable set of functions. $\endgroup$
    – Ross Millikan
    Commented Mar 9, 2015 at 16:41
  • 12
    $\begingroup$ Since the set of computable functions is countable, can't the second angel pick an enumeration of the functions and guess them one by one (without ever asking for an output value)? $\endgroup$
    – Julian Rosen
    Commented Mar 9, 2015 at 16:50
  • 4
    $\begingroup$ Joke answer: the angels can use the oracle to find a proof in ZFC answering this question. $\endgroup$
    – Lopsy
    Commented Mar 9, 2015 at 17:58
  • 3
    $\begingroup$ It's fine with me. Math questions borderline to puzzle (with interesting answers) are better than crap-easy/boring questions. I wouldn't vote off-topic, but I think it is very much borderline to hard core maths. But I very much liked the answer of Rex. Surprisingly 'simple' argument.... $\endgroup$
    – BmyGuest
    Commented Mar 9, 2015 at 23:01

5 Answers 5

Reset to default
16
$\begingroup$

The angels should play the game, as long as the formula for the computable function must be fixed in advance and finite.

Proof: let F be the shortest encoding of the formula (length l(F)) using a set of symbols S of size n(S). Then the guessing angel can simply count up from 0 in base n(S), and some time before n(S)l(F) they will encounter the formula.

(If the angels are allowed something really weird such as infinite "computable" functions, then no, they should not play the game: there is infinite information in the formula, and it could be constructed so that you are required to know at least one new bit for each next number, so there's no way to know it in finite time.)

Improve this answer
$\endgroup$
10
  • $\begingroup$ Good explanation. $\endgroup$
    – A E
    Commented Mar 9, 2015 at 20:02
  • 2
    $\begingroup$ It amuses me to note we don't even have to solve the halting problem here. Presumably the first angel has to prove that the particular Turing machine chosen halts so that it represents a function. The second can just guess strings of characters in the proper format that they might be halting Turing machines. The second will come onto the correct string after some finite time. $\endgroup$
    – Ross Millikan
    Commented Mar 9, 2015 at 20:28
  • 2
    $\begingroup$ The guessing angel can only guess coputable functions, yes? Then wouldn't he/she/it have to decide whether a given string of symbols represents a machine that halts before guessing that string? $\endgroup$
    – QuadmasterXLII
    Commented Mar 10, 2015 at 0:22
  • 3
    $\begingroup$ @Kevin: that’s not quite right. It’s true that by definition, any computable function can be represented by a finite string. But most encodings are partial. Under the original Gödel numbering, most strings don’t represent anything at all (i.e. they have “syntax errors”). Under more careful encodings, every string can be meaningful, but in general strings will denote partial computable functions — i.e. programs which may fail to terminate on some inputs. So this answer works if the guesser is allowed to guess partial computable functions, not just total computable functions. [cont’d] $\endgroup$
    – Peter LeFanu Lumsdaine
    Commented Mar 10, 2015 at 2:16
  • 2
    $\begingroup$ Also, the answer works if the guesser is a mathematical “oracle”, and knows the answers to non-computable questions like “is such-and-such partial computable function total?” However, if the angel can only guess computable functions that are actually total, then for this answer to work, one would have to know that the total computable functions are recursively enumerable, or equivalently if totality of p.c.f’s is semi-decidable. I don’t know if this is the case; it doesn’t seem trivial either way. $\endgroup$
    – Peter LeFanu Lumsdaine
    Commented Mar 10, 2015 at 2:20
8
$\begingroup$

The guessing angel can win in finite time with 0 integer queries.

The computable functions are countable. Enumerate them and guess them in order.

Improve this answer
$\endgroup$
5
$\begingroup$

Update: this answer is partly/mostly wrong, see Rex's answer. But it's not bad for a wild guess, I feel. The set of possible formulae is infinite but because it's countably infinite, the second angel can keep counting until he/she/it arrives at the answer. :)

The key point (to my mind) being that although there are an infinite number of possibilities for the first angel to choose from, once they've chosen a specific one it takes a finite amount of time for angel 2 to 'count up' until they get to it - which they don't have to go through all the infinite possibilities to do.

For any finite known set of mappings, inputs to outputs, there can always be more than one function which could apply.

So if the angels are partway through the game and have a set of mappings

{a, b, c, ...} ---> {d, e, f, ...}

then that isn't enough information for the second angel to know that there can only be one possible function that could produce that mapping.

So the second angel will need to ask for more information.... but no amount of information will ever be enough for total certainty, because there will always be more than one possible function that could apply.

(Alternatively the second angel could guess a function without being totally certain that they're right, but then it would be possible for them - by chance - to always guess wrongly, so the game could still go on forever).

So the angels shouldn't play the game - they should watch England lose at cricket instead, because that always happens within a finite time.

One way to prove me wrong here would be to come up with a set of mappings (inputs to outputs) which can only be produced by one single function - I don't think that any such exists. If it does then I'm wrong and the angels should play the game.

Example:

The sequence is:

{1, 2, 3, 4, 5} ---> {1, 2, 3, 4, 5}

This function could apply:

f(x) = x

but then so could this one:

f(x) = x < 6 ? x : 2*x

and so could any function in this infinite set of functions (where k is any integer):

f(x) = x < 6 ? x : kx

Improve this answer
$\endgroup$
10
  • 1
    $\begingroup$ You are correct - there is no such unique mapping. You could always define a new mapping as 'the same as that other one, except switch the outputs for input values of 1,000,000 and 1,000,001.' Or any other pair of arbitrarily large numbers. $\endgroup$
    – frodoskywalker
    Commented Mar 9, 2015 at 17:36
  • $\begingroup$ @frodoskywalker, exactly. In fact I think for any set of mappings there's an infinite number of functions that could apply. $\endgroup$
    – A E
    Commented Mar 9, 2015 at 17:40
  • 1
    $\begingroup$ Your example would not fail that test because it is computable. The program if(x<6) return x; else return 2*x; represents it in a Turing-complete programming language. But a completely random mapping of integers would almost certainly not be, because there is no way to represent it with a finite computer program or Turing machine. $\endgroup$
    – Kevin
    Commented Mar 9, 2015 at 17:49
  • 2
    $\begingroup$ Incidentally, any mapping of integers can be represented as a simple polynomial function using curve fitting. For example, [1,2,3,4,5] maps to [1,2,3,4,100] using the equation 95/24*(x^4) -475/12*(x^3) + 3325/24*(x^2) -2363/12*x + 95. $\endgroup$
    – Kevin
    Commented Mar 9, 2015 at 18:14
  • 3
    $\begingroup$ Other Kevin and A E, you're both right that there are an infinite number of possible functions. (I wasn't aware that any arbitrary mapping of integers could be represented using curve fitting, but I believe that doesn't change the math I used to come up with my strategy.) The thing is, there are only a countably infinite number of computable functions, which allows us to come up with a finite-time (unbounded, but finite) strategy. $\endgroup$
    – Kevin
    Commented Mar 9, 2015 at 18:34
4
$\begingroup$

It depends on the interpretation of the question.

As per Rex Kerr’s answer and xnor’s answer, if the guesser is allowed completely arbitrary strategies, then they should play.

However, if the guesser can only play computably, then they should not play. That is: given any computable strategy for the guesser, there is some total computable function which it will fail to guess.

Proof: let $\sigma$ be any computable strategy for the guesser: i.e. a computable function which, given a finite number of input-output pairs (the state of play so far), returns a computable function (the next guess). Then define the computable function $g_\sigma$ by a diagonalisation argument:

  • to compute $g_\sigma(n)$, first compute all the earlier values of $g_\sigma$. Then enumerate all the subsets $S \subseteq \{0,\ldots,n-1\}$ (there are finitely many, and they are easy to enumerate computably); for each of these, look at the function $\sigma(g\!\upharpoonright_S)$, i.e. the guess that the strategy would make, given the values of $g$ on $S$. Now take $g_\sigma(n)$ to be the maximum of the values $\sigma(g_\sigma\!\upharpoonright_S)(n)$, plus one. (This is computable since $\sigma$ is, and so is each $\sigma(\sigma)$, and we know the values of $g_\sigma$ on all inputs below $n$.)

Then $\sigma$ can never guess $g_\sigma$. For every guess $\sigma(f)$ it can make (where $f$ is some finite known set of values), $g_\sigma(n)$ will be strictly greater than $\sigma(f)(n)$ on any input $n$ greater than the inputs included in $f$, since the computation of $g_\sigma(n)$ will include $\sigma(f)(n)$ in the set it maximises over.

So we have: given any computable strategy for the guesser, there is some computable function on which it will fail.

Indeed, this can be strengthened a bit to cover non-deterministic strategries. If the guesser has access to a finite amount of nondeterminism each turn (e.g. can flip a coin or roll a dice at each guess, but otherwise must work computably), then still, there is no unbeatable computable strategy. Essentially, the same construction works, but the maximisation has to be over not just sets $S$, but also over all possible dice rolls for each guess — but this set is still finite and computable.

So in summary: if the guesser must play computably, or computably modulo some finite amount of nondeterminism, then they cannot be sure the game will end.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I like snow as much as anyone (except for Elsa of Arendelle, perhaps), but it doesn't appear in my name. Also, your diagonalization yields an infinite computable function (which I alluded to in my answer: you added a specific strategy for implementation). If you are restricted to any finite length in advance, angel two will eventually hit your formula. $\endgroup$
    – Rex Kerr
    Commented Mar 10, 2015 at 7:36
  • $\begingroup$ Oops, my bad on your name! I think the slip came from reading too much Game of Thrones last night. But the function I construct is not “infinite” — it is finitely specified, as any computable function must be by definition; for each $\sigma$, the length of the specification of $g_\sigma$ is fixed. This doesn’t contradict your answer, it just shows that any winning strategy for the guesser must be non-computable. $\endgroup$
    – Peter LeFanu Lumsdaine
    Commented Mar 10, 2015 at 7:47
  • 1
    $\begingroup$ Yes, that's correct as you've described it (accepting the constraint that the function must only return computable functions). $\endgroup$
    – Rex Kerr
    Commented Mar 10, 2015 at 7:56
  • 2
    $\begingroup$ Rex's answer is a computable strategy though I believe? The difference is Rex's strategy computably enmuerates partial computable functions, which the oracle we're assuming can cope with. This diagonalisation argument seems to show that it's not possible to computably enumerate total computable functions. Subtle difference, depending on how the question is interpreted.... $\endgroup$
    – David E
    Commented Mar 10, 2015 at 15:56
  • $\begingroup$ Great observation. At first, I had trouble reconciling it with a version of my and Rex Kerr's answer that seems computable: take the well-formed Turing machines in lexicographic order, and output the functions they compute, allowing repeats. But I see now there's an issue that a TM might not halt on an input, so some of these do not represent computable functions, and you cannot compute which ones. David E.'s answer explains this well. $\endgroup$
    – xnor
    Commented Mar 10, 2015 at 20:14
3
$\begingroup$

I really enjoyed this question, so as a summary over all possible interpretations/answers, we have the following:

Case 1: The oracle accepts descriptions of partial computable functions

You should play the game: You can (computably) enumerate all partial functions by just enumerating all programs with proper syntax. See Rex's Answer.

Case 2: The oracle requires all descriptions to be total computable functions

Case 2.1: Your strategy is required to be computable

You shouldn't play the game: See Peter's answer - there is no computable enumeration of total computable functions.

Case 2.2: Your strategy is allowed to not be computable

You should play the game. The total computable functions are a subset of the partial computable functions, and hence countable, so enumerable, though not computably so. See Xnor's answer.

Personally, I think a more interesting game is one in which angel 2 is only allowed to guess the function / consult the oracle $< K$ times for some fixed natural number $K$.

Claim: Such a game should not be played

Similar to A E's answer - for any finite number of known (input, output) pairs, there are an infinite number of possible total computable functions that give such an output. (Note these are still [non-computably] enumerable as earlier, ie I can find a list such that any given function appears at a finite place in my list).

BUT at any finite time, I have not nailed down the given output for definite, and still have an infinite number of possibilities. So I cannot win.

To explain the conceptual difference between these games / these answers, consider this analogy:

Instead, angel one proposes "I am thinking of a fixed natural number $N$. At each step, you're allowed to either ask for the digit at position $p \in \{0, 1, \dots \}$ (ie, the digit representing the number of $10^p$s in my number); OR guess the number. Can you guess my number correctly in a finite number of steps?"

If angel two just guesses digits, they get nowhere: there are always an infinite number of possible numbers out there fitting the information they have received. But if instead they just start guessing possibilities, they could simply ask "Is 1 right? Is 2 right? Is 3 right?..." and definitely win in finite time.

Extensions:

It's a different question working out fast strategies to guess $N$. The above method takes $N$ turns. But you could also you could instead at every $n=2k\,$th step, ask for the $k\,$th digit, $d_k$, of the number, and at every $n=2k+1\,$th step, ask if the number is $d_k d_{k-1} \dots d_1 d_0$. This finds the number in $O(\log(N))$ steps.

  • Challenge 1: Is it possible to do any better in terms of the running time of angel 2's algorithm? (for this new problem?)

  • Challenge 2: In the original question (assuming the interpretation as in Case 1), if angel one chooses a partial computable function $\{N\}$ (ie with Gödel number $N$), does there exists / can you create a general algorithm for angel 2 which improves on the trivial worst-case run time of $O(N)$ (like we have done for the analogous problem above)?

I don't actually know the answer to either of these questions... Might think about them if I have a little longer.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Very nice summary, and interesting extensions of the question! $\endgroup$
    – Peter LeFanu Lumsdaine
    Commented Mar 11, 2015 at 2:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.