compression - bzip2图灵完备吗？

Question

或任何其他压缩算法，就此而言。

（话又说回来，如果有一个图灵完备的压缩算法，它还会被认为是一种压缩算法，而不是一种编程语言吗？）

Answer 1

如果您询问的是解压缩器而不是压缩器，这个问题可能几乎是有道理的。压缩器的工作实际上是编写要由解压缩器执行的程序，该程序将重新创建被压缩的原始文件。该程序是用压缩数据格式的语言编写的。

这个问题的答案是否定的，bzip2 解压缩器不是图灵完备的，因为它无法循环或递归。我知道的任何其他标准压缩格式的解​​压缩器也没有。

更新：

由于安全问题，它似乎已被弃用，但显然 WinRAR 在解压缩器中内置了一种称为RarVM的后处理语言，这是一个图灵完备的机器，用于实现任意复杂的数据预压缩过滤器。