# Checking for finite fibers in hash functions

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?

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.