logoalt Hacker News

bingobangobungoyesterday at 10:05 PM2 repliesview on HN

I was thinking in specifically the positive, would compression or encoding potentially allow for more compact representation of programs. Like Kolmogorovs


Replies

inigyouyesterday at 10:26 PM

No not really. It's a thing you can do just because you can, like writing a book without the letter "e". Closer to the context of computation, it's like building a computer using only NAND gates. Or, given how restrictive the S combinator supposedly is, using only AND and OR gates. It won't make an efficient computer because your design is convoluted to all hell to make up for your choice to never use a NOT gate. Even the one made from NAND isn't efficient, because even though NAND can make any circuit without being too convoluted, it's not the most efficient way to make all circuits.

messeyesterday at 10:29 PM

If anything, this would be a less compact representation.