4
$\begingroup$

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).

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – xnor
    Commented Mar 7, 2015 at 9:49
  • $\begingroup$ I think it is on-topic, but I can't give a definitive answer. $\endgroup$
    – QuyNguyen2013
    Commented Mar 8, 2015 at 2:27
  • $\begingroup$ 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). $\endgroup$
    – Marc van Leeuwen
    Commented Mar 8, 2015 at 6:03
  • $\begingroup$ @ghosts_in_the_code, I'm 99% sure that this would be closed as off topic within ten minutes on codegolf.stackexchange. $\endgroup$
    – Peter Taylor
    Commented Mar 9, 2015 at 14:26
  • $\begingroup$ I posted my puzzle here, taking into account Marc van Leeuwen's feedback: puzzling.stackexchange.com/questions/10009/… $\endgroup$
    – Kevin
    Commented Mar 9, 2015 at 16:20

3 Answers 3

Reset to default
6
$\begingroup$

To me, this seems on topic. It looks like a puzzle, it smells like a puzzle, so it's probably a puzzle.

I do think it's an edge case, though, and it could go either way, depending on how it's written. I personally think it's fine as-is, though.

$\endgroup$
3
$\begingroup$

Having confirmed the answer has made me see it as more of a math problem rather than a puzzle, even though it did not seem so from the question.

(Spoilered)

Answering basically just requires seeing that there are countably many computable functions. If you know this mathematical fact, there is little to solve. If not, you could cobble together an argument for it, but that too has the style of a textbook math problem. The game is puzzley, but it's basically a red herring, as querying integers isn't needed, nor is adapting to replies.

$\endgroup$
2
$\begingroup$

I can't speak for anyone else but I wouldn't vote to close. Decidability is interesting.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .