5 ms·
Makes me wonder what are the implication of the halting problem for compression formats
by raverbashing 12y ago
Makes me wonder what are the implication of the halting problem for compression formats
- whatshisface 12y agoThe halting problem only applies to full Turing machines, and their equivalents. So, a compression algorithm based on x86 assembly is uncheckable, but one based on a restricted format like .zip would be fine. Or, you could just give it a time limit.
- caspianm 12y agoI made the file DanBC referred to above, and wondered about how much computation you could do with iterated decompression (specifically, deflate-type decompression). Could you make a zip file representing a Turing machine, so that after unzipping it it represented the machine after one step of processing, and after unzipping the result, represented the machine after a second step, etc. Or if not a direct translation of a Turing machine, then some other Turing complete system. As far as I know, no one has done this, but if it is possible, one implication would be that you couldn't prove whether the process of recursively unzipping a file could continue forever, or would halt.