No, compression formats are not Turing-complete. You control the code interpreti... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

kam on April 29, 2025 | parent | context | favorite | on: I use zip bombs to protect my server

No, compression formats are not Turing-complete. You control the code interpreting the compressed stream and allocating the memory, writing the output, etc. based on what it sees there and can simply choose to return an error after writing N bytes.

eru on April 30, 2025 [–]

Yes, and even if they were Turing complete, you could still run your Turing-machine-equivalent for n steps only before bailing.

Consider applying for YC's Fall 2026 batch! Applications are open till July 27.
Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact