Checking for finite fibers in hash functions

Question

Let $\{0,1\}^{<\omega}$ denote the collection of finite binary sequences. By a hash function we mean a computable map $$h: \{0,1\}^{<\omega} \to \{0,1\}^n$$ for some fixed $n\in\omega$. Define $\text{Fib}(h) = \{h^{-1}(\{y\}) : y \in \{0,1\}^n\}$ to be the set of fibers of $h$. (That is, every element of $\text{Fib}(h)$ is the set of inputs being mapped to some fixed $y\in\{0,1\}^n$.)

It is clear that some elements of $\text{Fib}(h)$ will be infinite. Given a hash function $h: \{0,1\}^{<\omega} \to \{0,1\}^n$ is the problem to decide whether all members of $\text{Fib}(h)$ are infinite, computable?

Answer 1

This is not computable, even for $n=1$.

Let $h_k(x)=1$ if $x$ is odd or if the $k$th Diophantine equation has no solutions of size less than $x$. Let $h_k(x)=0$ If $x$ is even and the $k$th Diophantine equation has a solution of size less than $x$.

So computing whether the fibers of $h_k$ are all infinite is computing whether the $k$th Diophantine equation has a solution, which is impossible by the Matiyasevich-Davis-Putnam-Robinson solution to Hilbert’s 10th problem.

Answer 2

Assuming hash functions can be partial (so that the domain of our decision problem is decidable), this is undecidable by Rice's theorem. If you insist that hash functions are total so that we are working with a promise problem as defined here, the answer is still no, again following from Rice's theorem.