# Would this potential post be a math puzzle or math problem?

I am considering posting the following puzzle. I'm aware that there's been a lot of discussion about what makes a high-quality math puzzle, as opposed to a an off-topic math problem, and I'm not sure whether the question would be on-topic or not. Can you please tell me whether this potential puzzle would be acceptable?

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 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 the game. Should they play it? If they should, what is the smallest number of integers the second angel will need to check to be sure of eventually guessing the correct function?

I do know the solution to the question, although I won't post it here (unless you believe it is relevant).

• I think the question would be clearer if "infinite" was "unlimited" or "arbitrarily high", and if you specified that the guessing angel plays optimally, i.e. that you're asking whether there exists a strategy that is guaranteed to win a finite number of steps.
– xnor
Mar 7, 2015 at 9:49
• I think it is on-topic, but I can't give a definitive answer. Mar 8, 2015 at 2:27
• The main mathematical problem with you puzzle is that it does not say how computable functions are specified, or compared. Testing two algorithms (Turing machines) for (extensional) equality as functions is undecidable. Specifying a function on the natural numbers by tabulating its values would take infinite time for a single comparison of functions (even for angels). Mar 8, 2015 at 6:03
• @ghosts_in_the_code, I'm 99% sure that this would be closed as off topic within ten minutes on codegolf.stackexchange. Mar 9, 2015 at 14:26
• I posted my puzzle here, taking into account Marc van Leeuwen's feedback: puzzling.stackexchange.com/questions/10009/… Mar 9, 2015 at 16:20