5 ms·

Since we're in a whimsical mood: "There’s a function called Hash in the Wolfram Language, and for example applying it to the previous paragraph of text gives 8

Since we're in a whimsical mood: "There’s a function called Hash in the Wolfram Language, and for example applying it to the previous paragraph of text gives 8643827914633641131." I was a bit saddened to see that this was not "applying it to this paragraph of text gives…", which would have been quite the party trick.

l9k 9y ago
Would it be possible?
- Smaug123 9y ago
  Probably. There are only 2^64 possible hash values (Mathematica's Hash function, with no method specified, produces a 32- or 64-bit output depending on platform), and there are many more strings than that which could reasonably be called a "paragraph". It's pretty reasonable to hope that there's a self-describing paragraph out there somewhere.
  - repsilat 9y ago
    Hah, "could in theory" vs "could in practice" -- depending on the hash function, it could take hundreds or thousands of processor-years. Maybe Google could do it. http://m.wolframalpha.com/input/?i=2%5E64+things+%2F+%281+billion+things+%2F+second%29+in+years http://m.wolframalpha.com/input/?i=2%5E64+things+%2F+%281+bi...
  - bluesign 9y ago
    Actually for any given paragraph, probabilty of hash(paragraph+hash) = hash is pretty high.
    - svantana 9y ago
      You mean that there exists at least one hash such that hashFunc(paragraph+hash) = hash? Yup, that probability converges to 1-exp(-1) = 63%. So it's no guarantee, but if you have some wiggle room in the paragraph (change the wording slightly etc) you can probably make it work.
- notfed 9y ago
  It looks that the default Hash implementation depends on whether the system is 32-bit or 64-bit [1]. It's also not clearly documented what the default implementation of Hash really is. On a 32-bit system, yes, someone could probably do it. [1] https://mathematica.stackexchange.com/a/124340 https://mathematica.stackexchange.com/a/124340
- xamuel 9y ago
  Given that they control the hash function, it would be trivial: hard-code a special exception value for exactly that purpose.
wackspurt 9y ago
What you are describing sounds similar to a "quine". A quine is a non-empty computer program which takes no input and produces a copy of its own source code as its only output. https://en.wikipedia.org/wiki/Quine_(computing) https://en.wikipedia.org/wiki/Quine_(computing) Here is an example: s = 's = %r\nprint(s%%s)' print(s%s)
- Smaug123 9y ago
  It is very similar, except this one is computationally difficult to achieve if the hash function is worth its salt ;)
- angel_j 9y ago
  are there any practical uses of quine?
  - grzm 9y ago
    As a distraction it can make a nice tonic on a stressful day.
  - Smaug123 9y ago
    Yes: hiding malware. https://softwareengineering.stackexchange.com/questions/111351/are-quines-useful-as-anything-more-than-a-programming-puzzle https://softwareengineering.stackexchange.com/questions/1113... More generally, https://stackoverflow.com/a/1764933/1462221 https://stackoverflow.com/a/1764933/1462221 points out that DNA implements a very big and complicated quine.
    - angel_j 9y ago
      I feel that a groundbreaking use of quines is simply yet to be realized. I have a feeling they will show up in AI (if not intentionally!). Does DNA encode it's own logic? That seems testable.
    - isthatart 9y ago
      One of the answers from your first link gives a link to this excellent article https://link.springer.com/chapter/10.1007%2F978-3-540-92273-5_2 https://link.springer.com/chapter/10.1007%2F978-3-540-92273-... on "autocatalitic quines". The Introduction section explains very nice the history of uses of quines in artificial life. There are some weird parts though in all this, namely that we may think about different life properties in terms of quines: 1) Metabolism, where you take one program, consume it and produce the same program 2) Replication, where you take one program, consume it and produce two copies. But what about 3) Death I thought about this a lot during my chemlambda alife project, where I have a notion of a quine which might be interesting, seen the turn of these comments. A chemlambda molecule is a particular trivalent graph (imagine a set of real molecules, the graphs don't have to be connected), chemical reactions are rewrites, like in reality, when if there is a certain pattern detected (by an enzyme, say) then the patern is rewritten. There are two extremes in the class of possible algorithms. One extreme is the deterministic one, where rewrites are done whenever possible, in the order of preference from a list, so that the possible conflicting patterns are always solved in the same way. The other extreme is the purely random one, where patterns are randomly detected and then executed or not acording to a coin toss. Now, a quine in this world is by definition a graph which has a periodic evolution under the deterministic algorithm. The interesting thing is that a quine, under the random algorithm, has some nice properties, among them that it has a metabolism, can self-replicate and it can also die. Here is how a quine dies. Simple situation. Take a chemlambda quine of period 1. Suppose that there are two types of rewrites, the (+) one which turns a pattern of 2 nodes into a pattern of 4 nodes, the other (-) which turns a pattern of 2 nodes into a pattern of 0 nodes (by gluing the 4 remaining dangling links in the graph). Then each (+) rewrite gives you 4 possible new patterns (one/node) and each (-) rewrite gives you 2 possible new patterns (because you glued two links). Mind that you may get 0 new patterns after a (+) or (-) rewrite, but if you think that a node has an equal chance to be in a (+) pattern or in a (-) pattern, then there is twice as possible that a new pattern comes from a (+) rewrite than from a (-) rewrite. Suppose that in the list of preferences you always put the (+) type in front of the (-) one. It looks that in this way graphs will tend to grow, right? No! In a quine of period 1 the number of (+) patterns = number of (-) patterns. Hence, if you use the random algorithm, the non execution of a (+) rewrite is twice more probable to affect future available rewrites than the non-execution of a (-) rewrite. In experiments, I noticed lots of quines which die (there are no more rewrites available after a time), some which seem immortal, and no example of a quine which thrives.

l9k 9y ago

Would it be possible?

Smaug123 9y ago
Probably. There are only 2^64 possible hash values (Mathematica's Hash function, with no method specified, produces a 32- or 64-bit output depending on platform), and there are many more strings than that which could reasonably be called a "paragraph". It's pretty reasonable to hope that there's a self-describing paragraph out there somewhere.
- repsilat 9y ago
  Hah, "could in theory" vs "could in practice" -- depending on the hash function, it could take hundreds or thousands of processor-years. Maybe Google could do it. http://m.wolframalpha.com/input/?i=2%5E64+things+%2F+%281+billion+things+%2F+second%29+in+years http://m.wolframalpha.com/input/?i=2%5E64+things+%2F+%281+bi...
- bluesign 9y ago
  Actually for any given paragraph, probabilty of hash(paragraph+hash) = hash is pretty high.
  - svantana 9y ago
    You mean that there exists at least one hash such that hashFunc(paragraph+hash) = hash? Yup, that probability converges to 1-exp(-1) = 63%. So it's no guarantee, but if you have some wiggle room in the paragraph (change the wording slightly etc) you can probably make it work.
notfed 9y ago
It looks that the default Hash implementation depends on whether the system is 32-bit or 64-bit [1]. It's also not clearly documented what the default implementation of Hash really is. On a 32-bit system, yes, someone could probably do it. [1] https://mathematica.stackexchange.com/a/124340 https://mathematica.stackexchange.com/a/124340
xamuel 9y ago
Given that they control the hash function, it would be trivial: hard-code a special exception value for exactly that purpose.

wackspurt 9y ago

What you are describing sounds similar to a "quine". A quine is a non-empty computer program which takes no input and produces a copy of its own source code as its only output. https://en.wikipedia.org/wiki/Quine_(computing) https://en.wikipedia.org/wiki/Quine_(computing) Here is an example: s = 's = %r\nprint(s%%s)' print(s%s)

Smaug123 9y ago
It is very similar, except this one is computationally difficult to achieve if the hash function is worth its salt ;)
angel_j 9y ago
are there any practical uses of quine?
- grzm 9y ago
  As a distraction it can make a nice tonic on a stressful day.
- Smaug123 9y ago
  Yes: hiding malware. https://softwareengineering.stackexchange.com/questions/111351/are-quines-useful-as-anything-more-than-a-programming-puzzle https://softwareengineering.stackexchange.com/questions/1113... More generally, https://stackoverflow.com/a/1764933/1462221 https://stackoverflow.com/a/1764933/1462221 points out that DNA implements a very big and complicated quine.
  - angel_j 9y ago
    I feel that a groundbreaking use of quines is simply yet to be realized. I have a feeling they will show up in AI (if not intentionally!). Does DNA encode it's own logic? That seems testable.
  - isthatart 9y ago
    One of the answers from your first link gives a link to this excellent article https://link.springer.com/chapter/10.1007%2F978-3-540-92273-5_2 https://link.springer.com/chapter/10.1007%2F978-3-540-92273-... on "autocatalitic quines". The Introduction section explains very nice the history of uses of quines in artificial life. There are some weird parts though in all this, namely that we may think about different life properties in terms of quines: 1) Metabolism, where you take one program, consume it and produce the same program 2) Replication, where you take one program, consume it and produce two copies. But what about 3) Death I thought about this a lot during my chemlambda alife project, where I have a notion of a quine which might be interesting, seen the turn of these comments. A chemlambda molecule is a particular trivalent graph (imagine a set of real molecules, the graphs don't have to be connected), chemical reactions are rewrites, like in reality, when if there is a certain pattern detected (by an enzyme, say) then the patern is rewritten. There are two extremes in the class of possible algorithms. One extreme is the deterministic one, where rewrites are done whenever possible, in the order of preference from a list, so that the possible conflicting patterns are always solved in the same way. The other extreme is the purely random one, where patterns are randomly detected and then executed or not acording to a coin toss. Now, a quine in this world is by definition a graph which has a periodic evolution under the deterministic algorithm. The interesting thing is that a quine, under the random algorithm, has some nice properties, among them that it has a metabolism, can self-replicate and it can also die. Here is how a quine dies. Simple situation. Take a chemlambda quine of period 1. Suppose that there are two types of rewrites, the (+) one which turns a pattern of 2 nodes into a pattern of 4 nodes, the other (-) which turns a pattern of 2 nodes into a pattern of 0 nodes (by gluing the 4 remaining dangling links in the graph). Then each (+) rewrite gives you 4 possible new patterns (one/node) and each (-) rewrite gives you 2 possible new patterns (because you glued two links). Mind that you may get 0 new patterns after a (+) or (-) rewrite, but if you think that a node has an equal chance to be in a (+) pattern or in a (-) pattern, then there is twice as possible that a new pattern comes from a (+) rewrite than from a (-) rewrite. Suppose that in the list of preferences you always put the (+) type in front of the (-) one. It looks that in this way graphs will tend to grow, right? No! In a quine of period 1 the number of (+) patterns = number of (-) patterns. Hence, if you use the random algorithm, the non execution of a (+) rewrite is twice more probable to affect future available rewrites than the non-execution of a (-) rewrite. In experiments, I noticed lots of quines which die (there are no more rewrites available after a time), some which seem immortal, and no example of a quine which thrives.