4 ms·

Could you really do general compression in this language? I was under the impression that the output is always the same size or larger than the input.

thomasmg 6mo ago
Yes you can do compression, if the text is compressible. The playground [1] has a "run length encoding" example. Maybe you meant sorting. You can implement sorting algorithms, as long as you store the information which entries were swapped. (To "unsort" the entries when running in reverse). So, an array that is already sorted doesn't need much additional information; one that is unsorted will require a lot of "undo" space. I think this is the easiest example to see the relation between reversible computing and thermodynamics: in thermodynamics, to bring "order" to a system requires "unorder" (heat) somewhere else. There are also examples for encryption / decryption, but I find compression and sorting more interesting. [1] https://topps.diku.dk/pirc/?id=janusP https://topps.diku.dk/pirc/?id=janusP
- lostmsu 6mo ago
  He meant lossy compression
evanb 6mo ago
You could package all your data into a zip using this language but you would also have a worthless stretch of memory seemingly filled with noise / things you’re not interested in.
- thomasmg 6mo ago
  Why do you think so? The code example shows that you can do RLE (run length encoding) without noise / additional space. I'm pretty sure you can do zip as well. It would just be very hard to implement, but it wouldn't necessarily require that the output contains noise. [1] https://topps.diku.dk/pirc/?id=janusP https://topps.diku.dk/pirc/?id=janusP
  - evanb 6mo ago
    Hmm. As a physicist my intuition is that information-preserving transformations are unitary (unitary transformations are 1-to-1). If a compression algorithm is going to yield a bit string (the zip file, for example) shorter than the original it can't be 1-to-1. So it must yield the zip file and some other stuff to make up for the space saved by the compression.

thomasmg 6mo ago

Yes you can do compression, if the text is compressible. The playground [1] has a "run length encoding" example. Maybe you meant sorting. You can implement sorting algorithms, as long as you store the information which entries were swapped. (To "unsort" the entries when running in reverse). So, an array that is already sorted doesn't need much additional information; one that is unsorted will require a lot of "undo" space. I think this is the easiest example to see the relation between reversible computing and thermodynamics: in thermodynamics, to bring "order" to a system requires "unorder" (heat) somewhere else. There are also examples for encryption / decryption, but I find compression and sorting more interesting. [1] https://topps.diku.dk/pirc/?id=janusP https://topps.diku.dk/pirc/?id=janusP

lostmsu 6mo ago
He meant lossy compression

evanb 6mo ago

You could package all your data into a zip using this language but you would also have a worthless stretch of memory seemingly filled with noise / things you’re not interested in.

thomasmg 6mo ago
Why do you think so? The code example shows that you can do RLE (run length encoding) without noise / additional space. I'm pretty sure you can do zip as well. It would just be very hard to implement, but it wouldn't necessarily require that the output contains noise. [1] https://topps.diku.dk/pirc/?id=janusP https://topps.diku.dk/pirc/?id=janusP
- evanb 6mo ago
  Hmm. As a physicist my intuition is that information-preserving transformations are unitary (unitary transformations are 1-to-1). If a compression algorithm is going to yield a bit string (the zip file, for example) shorter than the original it can't be 1-to-1. So it must yield the zip file and some other stuff to make up for the space saved by the compression.