Checking for finite fibers in hash functions

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.


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.