In my statistical programming work, I have run into a computational problem that I am unfamiliar with. Although my problem is a bit more detailed, it can be boiled down to the following. Suppose we have an arbitrary black-box function $f: \mathbb{Z} \rightarrow \{ 0,1 \}$ and we want to find the preimage:
$$f[1] = \{ x \in \mathbb{Z} | f(x) = 1 \}.$$
Suppose that we restrict attention to functions which give a preimage that is a finite union of connected intervals (so that the bounds of each interval can be written out). By "find the preimage" here, I have in mind computing an output that would tell the user the bounds of each of the intervals --- for example:
FIND_PREIMAGE(f)
Preimage of the function f
-Inf..-806, -720..-43, 12..14, 85..9015, 60478..101056
Now, suppose we have programmed the function $f$ and so for any input $x$ we can compute $f(x)$ in a finite number of operations. Intuitively, it seems to me that even with such a function available, it is impossible to find an algorithm that could compute the above output (for an arbitrary function of this kind) in a finite number of operations. Unless I am mistaken, the set of all functions of this kind is cardinally equivalent to the real numbers, so it seems to me that computing the image set for any function would require an infinite number of operations.
Unfortunately, all this is just my intuition, and this is a problem that is well outside my own field. I do not know if this problem has a name in the computation literature, or if there is an existing proof that this is impossible to compute. This seems like a problem that is sufficiently simple and fundamental that it is probably well-known.
My Question: Does the above computational problem (or something similar) have a name/literature? Is there an existing proof of that this cannot be computed in a finite number of operations?
In fact, the set of all such functions is countable: note that every function is given by the finitely many values $i$ for which $f(i) = 1$, and we could associate to each such function $f$ the number $$ q(f) = \sum_{i \in \mathbb Z : f(i) = 1} 2^i, $$ and this will be a rational number, because there are only finitely many binary digits after the "decimal" point.
However, your intuition that this is not computable is correct. Because the input function is treated as a black box, we do not even need the machinery of computability (the halting problem, etc.) here. The proof is simpler. Suppose that you could compute the preimage in finitely many operations for each $f$, and let's denote the algorithm by the letter $A$. Then consider the function $f_0$ with $f_0(0) = 1$, while $f_0(n) = 0$ for all $n \neq 0$. Now $A(f_0)$ only calls the function $f_0$ finitely many times, because it gets the result in finitely many operations. So suppose it calls $f_0(n_1), f_0(n_2), \cdots, f_0(n_k)$. Write $m = \max(n_1, \ldots, n_k)$. Then let the function $f$ be given as follows: we define $f(0) = f(m+1) = 1$, and $f(n) = 0$ if $n \notin \{0, m+1\}$. Then in the computation of $A(f)$, the algorithm must do the exact same thing as it did to $A(f_0)$, because for the purposes of the computation, $f, f_0$ are indistinguishable. Thus the output for both will be the same, but $f \neq f_0$. Thus such an $A$ cannot exist.