CODEWITHSUNDEEP
compressionbzip2turing-complete
SoniEx2
SoniEx2

Reputation: 2034

Is bzip2 turing complete?

Or any other compression algorithm, for that matter.

(Then again, if there was a turing-complete compression algorithm, would it still be considered a compression algorithm, rather than a programming language?)

Upvotes: 2

Views: 327

Answers (1)

Mark Adler
Mark Adler

Reputation: 112189

The question might almost make sense if you had asked about the de-compressor, as opposed to the compressor. The job of a compressor is effectively to write a program to be executed by the decompressor that will recreate the original file being compressed. The program is written in the language that is the compressed data format.

The answer to that question is no, the bzip2 decompressor is not Turing complete, since it has no way to loop or recurse. Nor does the decompressor for any other standard compression format that I am aware of.

Update:

It appears to have since been deprecated due to security concerns, but apparently WinRAR had a post-processing language built into the decompressor called RarVM, which was a Turing-complete machine for implementing arbitrarily complex pre-compression filters for data.

Upvotes: 4

Related Questions