# Data compression with Turing Machine

For traditional algorithms compressed data may vary, while decompression algorithm is always the same. Are there any approaches, when (de)compression algorithm is also changing to provide best compression level? One can think about splitting data as small chunks and for each small chunk iterate all possible (de)compression codes to get best compression. Is there any research or existing algorithms, utilizing ideas like that?

• If there are multiple decompression algorithms, then how do I know which algorithm to use when given some compressed data? May 22, 2018 at 17:56
• This makes sense for lossy compression, but not for lossless compression. May 22, 2018 at 18:05
• Probably you can store decompression algorithm code along with compressed data. May 22, 2018 at 19:47

Suppose the first byte of the compressed file indicates which decompression algorithm to use, and then you use that algorithm to decompress the rest. Sure, you could do that. Absolutely. Some compression formats already do exactly this.

That said, it's also possible to view this as a single decompression algorithm. The master algorithm looks at the first byte of the file and then branches to a subroutine that handles the rest of the file. That can be considered a single algorithm. So at a fundamental level there is no fundamental distinction that can be drawn.

DEFLATE the stock standard compression algorithm will do exactly that. There are 3 type of blocks differentiated by a 2 bit value at the start of each block:

1. the raw bytes for when the other two won't make it any smaller
2. compressed with a fixed huffman encoding when the custom tree would take too much space for what it would save
3. compressed with a supplied huffman encoding

The size of each block is free to choose the compressor as it sees fit.

It is possible to find a Turing machine program that generates a particular output and treat that as the compressed form of the output data given the description of the Turing machine.

This is a standard way to estimate the Kolmogorov Complexity using Levin's Coding Theorem Method (CTM). However, it is intractable for binary strings beyond a few bits (the ACSS package has a 13 bits database using a supercomputer).

As you mentioned, it is possible to break a long binary string down to blocks of e.g. 13 and then aggregate the program for each block that is a compressed representation of the data. This is called the Block Decomposition Method.

Check the resources on this site for more details: https://complexitycalculator.com/