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?



Checking for finite fibers in hash functions
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.


