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?
Answer
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.)
No comments:
Post a Comment