0
$\begingroup$

Is it correct to say that since the SHA256 function domain is finite (as reported here) we can build a DFA that calculates this function (i.e. trivially a giant lookup table)?

Furthermore, if we eliminate the limitation on the length of the input, is it correct to say that SHA256 function belongs to the class of $\mathcal{PR}$ primitive recursive functions?

$\endgroup$
  • $\begingroup$ I kindly request you to revise your question inline with community guidelines. $\endgroup$ – quintumnia Sep 4 '18 at 14:13
  • 3
    $\begingroup$ @quintumnia I kindly request you to be more specific if you're going to complain about new users' posts. Your comment isn't remotely helpful. $\endgroup$ – David Richerby Sep 4 '18 at 14:15
1
$\begingroup$

Is it correct to say that since the SHA256 function domain is finite we can build a DFA that calculates this function (i.e. trivially a giant lookup table)?

Theoretically, yes, that's correct. It would require a lookup table of $2^{2^{64}}$ entries, roughly, encoded as a DFA.

To be more picky, it depends on the notion of "DFA calculating a partial function". In particular, on what we require the DFA to do outside the domain of the function.

If we require non-termination, as we do for TMs, then a DFA can never implement a non-total function since it can not diverge. So, no DFA can compute SHA256.

If we instead only require to reach an "error" state outside the domain (or no requirement at all), then a DFA can compute SHA256.

I'd lean towards the latter interpretation, but here we need indeed to be a little careful with words.

Furthermore, if we eliminate the limitation on the length of the input, is it correct to say that SHA256 function belongs to the class of $\mathcal{PR}$ primitive recursive functions?

That's correct.

As a general "cannon" result, if an algorithm $A$ has a complexity function which is bounded above by some $\mathcal{PR}$ function $f$, then $A$ implements a function which belongs to $\mathcal{PR}$.

This is because in $\mathcal{PR}$ we can realize the single-step function for TM, mapping a TM configuration to its next one. Then we can recurse on the single-stepping function $f(n)$ times, and read the result in the final configuration.

Corollary: $TIME(O(2^{2^{2^{2^n}}})) \subseteq \mathcal{PR}$.

The unlimited SHA256 surely falls in that obscene time bound.

$\endgroup$
  • $\begingroup$ To be nitpicky, I would say "since the SHA256 function codomain (or range) is finite we can build a DFA that calculates this function (i.e., trivially a giant lookup table since its domain is also finite)". $\endgroup$ – Apass.Jack Sep 4 '18 at 15:52
  • 1
    $\begingroup$ @Apass.Jack Uh, no: the halting function returns 0 or 1 depending on its input TM, so it has a finite range, but that does not imply that we can implement it with a DFA. It is not even computable! So, we need a finite domain here, not merely finite range. (Also note that finite domain implies finite range) $\endgroup$ – chi Sep 4 '18 at 15:55
  • $\begingroup$ To be nitpicky again, do you imply the halting function restricted to any finite domain can be implemented with a DFA? $\endgroup$ – Apass.Jack Sep 4 '18 at 16:11
  • $\begingroup$ @Apass.Jack It depends on the meaning of "implemented". If by that we intend that we must observe non-termination outside the finite domain, then "no" since a DFA can not achieve non-termination. If we only care about the DFA behavior inside the domain, then "yes". I agree that here one must indeed be picky :) $\endgroup$ – chi Sep 4 '18 at 16:26
  • $\begingroup$ By the way, when I said finite codomain I was preparing for a DFA that computes (an extension of) SHA256 when we eliminate the limitation on the length of the input. Anyway, as you have noted, finite range is implied by finite domain and, hence, the initial statement is completely fine. $\endgroup$ – Apass.Jack Sep 4 '18 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.