3 ms·
Fundamentally, it never will be able to do this. The reason is because a hash is a galois field, or finite field which has no unique solutions. Turning a file
by than3 4y ago
Fundamentally, it never will be able to do this.
The reason is because a hash is a galois field, or finite field which has no unique solutions.
Turning a file into a string is simple, and only has one correct answer in that direction.
Turning a string into the same file mentioend previously is impossible, because there are multiple correct answers given any string, and the context had been discarded. There is no determinable way to rebuild the context, its a guess.
In one direction you have a unique answer, in the other you have a many to one answer. Determinism which is the property needed by computers to do work requires that there be a 1:1 solution otherwise you run into issues with the halting problem, and other non-deterministic behaviors that don't lend themselves to anything useful.
https://en.wikipedia.org/wiki/Theory_of_computation https://en.wikipedia.org/wiki/Theory_of_computation
Fundamentally if determinism is not present, a turing machine can't solve those classes of problems. Its a fundamental in the theory of computation. Yet so many people subscribe to magical thinking about computers because they do not understand this.
If you could preserve the context for a single file, then you could get the same file back, but special handling would be needed to switch between conflicts with determinism (which isn't possible for turing machines, halting problem) and for a general solution you would have to save the context of every single possible file (an infinite solution requiring an infinite amount of memory).
It can attempt to make an approximation, but that approximation in functions like hashes is so chaotic it will never get close to a general approximation.
It must get infinitely close, and as it works the memory required grows up to the size of the unique domain for the output function, at which point you run into the halting problem where determinism breaks. From that point it grows infinitely from there in a non-deterministic way.
Given the constraints imposed on the design of current day computers, more likely it will simply only map to the first unique answer within the space despite there being other possible answers because after that it has no way to know when it should halt, nor will it ever.
There are limits to the types of problems computers can solve.
Edit: clarified language
- hugh-avherald 4y agoI don't think Galois fields have anything to do with it. It's just hash functions on files are not typically injective. Perfect hash functions are injective though so can be inverted (but AI is not necessary).
- than3 4y agoI tailored my response so someone without a rigorous math background could come to a useful understanding of the limitations of computers. Most of the arbitrary length input to fixed output hashing for non-randomized data that I've seen use modulo p primes which compose a Galois field. More specifically this is done to reduce collisions and so they do not cluster with non-random input data, randomized data doesn't have this problem. Its done so those output keys are uniformly distributed across the fixed space as modular arithmetic tends to cluster around the divisors. Perfect hash functions are injective by definition and they maintain the same properties determinism requires (1:1 mapping) but they also require fixed input and fixed output. They do work but have fairly narrow and limited practical use and I don't see how they are particularly relevant to OP's question, it seems like unnecessary academic rigor that gets in the way of the intuitive point. OP's question involved hashing algorithms that have collisions, perfect hash function guarantees no collisions. I hope that clarifies the extent of how Galois fields relate to this. There are of course hash functions that are not Galois fields that have collisions, and you are right they do not meet that 1:1 mapping required for both injective functions and determinism system properties, those reduce to a Turing machine halting problem axiom and a violation of determinism when 1 state corresponds to many potential states. I mentioned Galois fields simply because they are often and historically have been commonly used for their useful properties.
- graderjs 4y agoI like your super foundational “theory of computation” approach! Really clear!