Hacker News new | past | comments | ask | show | jobs | submit login

> Computations consume and produce strings.

Really? What's so special about strings? Perhaps I want computations to consume and produce trees. It seems like you've picked an arbitrary setting for computation and said "Look! My constructions which are naturally suited to this setting are naturally suited to this setting!".




Like entropy, computational/informational content is absolute. Strings have higher entropy. If I say, "I'll hand you a piece of fruit", that statement objectively has less information (and therefore smaller computational complexity to verify), then if I said, "I'll hand you an apple". A tree really is inherently more complex than a string. It's like an RNA molecule being more likely to be naturally synthesized in the primordial soup than, say, a cat. Of course, an unspecified "tree" could be as "entropic" as an unspecified string, but my guess is that you mean something more specific.

So there's a real difference between various configurations of gas molecules in a box, and a real difference in the computational cost of representing them. Your statement is not unlike saying, "oh, so you've picked a high-entropy configuration, how convenient! What's so special about high entropy?" High entropy and low entropy aren't symmetrical. It takes more energy to move in one direction than the other.

Again, you shouldn't be surprised by this at all (I'd think it's rather obvious). Since typed formulations do proof work in their validation step (that can be Turing-complete in some cases), obviously that means that there is more complexity in their representation, otherwise, you'd have computation for free.

You can choose whatever representations you like. But representations that express more information, come at a higher computational cost.


> Again, you shouldn't be surprised by this at all (I'd think it's rather obvious).

I'm not sure why you think that I'm surprised, or even why you think that I disagree with your overall argument. I'm just trying to help you build your argument by pointing out the most obvious aspects which need more careful elucidation.

So your claim is that in the physical world strings are more fundamental than trees. Good to know. In fact I think there's an even simpler reason than the one you give of "entropy". That is, trees require space which grows exponentially in their depth, and thus they can't even be represented in the physical world.


I gave a more specific explanation in another comment: trees are more complex because they require nodes to be connected and each node to have no more than one parent. A string is any stream of measurements. The exponential growth of trees doesn't bother me, because you can have a natural encoding that doesn't grow exponentially, and doesn't increase interpretation cost exponentially.


And I gave a more specific objection there too.

A string is quite different from a stream. A string is typically considered random access, for a start.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: