News for hackers. Stuff that matters.
Re:Is this c/10 spaceship known? by heavenlyhash on Wednesday March 09, 2016 @04:29PM (#11255863)
That's a beautifully concise numbering system for sharing being used there.

Now if only we had descriptions of chemistry that were this terse. Imagine if this kind of problem solving, collaboration, simulation, and instant verification were the norm for synthetic chem. One of the comments -- "[Let's] use gencols to rub the ship against gliders and *WSSs to see whether there is a useful collision to maybe build a puffer" -- just blew me away. If this were chemistry, that commentator would have been suggesting automatic nanomachine factory discovery.

(InChI appears to be close. But vast amounts of data are locked up in obtuse formats are either Assigned-Names-And-Numbers style formats which are useless to indexing and similarity searches, or formats that embed non-relative coordinates in 3d space, etc, in such a way that computing a deterministic ID for sharing is practically a nonstarter.)

Re:Is this c/10 spaceship known? by dalke on Wednesday March 09, 2016 @06:35PM (#11256443)
InChI is not designed as, nor can used for, what you propose. Last I checked, conversion from an InChI to a structure format was not a supported option, and only exists for testing purposes. Which is not to say that people don't use for that. (Also, last I checked, there are inputs which cause InChI to segfault. And there's no spec for how to interpret InChIs other than to run the reference code.)

The InChI normalization step may also change the chemistry. For example, it may put things into a preferred tautomer form or charge state. This is essential for its goal of linking disparate records, but it is not chemistry preserving, and can be worse than passing an SD file to your nanomachine factory.

It was designed as "deterministic ID for sharing", yes, but not for sharing structure information but rather information related to the structure.

The most "concise" solution is to record the positions of the nuclei and the total charge. Then any quantum mechanics program will be able to reconstruct (to the desired level of approximation) the electron density of the molecule. This is the one you reject.

For good reasons. As you say, you want a nomenclature that can help with identity and similarity, and electron density is a very slow way to do that.

But such nomenclature is driven by human concepts. Fundamentally, there are different reaction rates depending on the relative orientation of two molecules. We see this in molecular beam experiments. For example, from 1979, http://www.sciencedirect.com/science/article/pii/00092614798... "Molecular beam reaction of K atoms with sideways oriented CF3I".

InChI doesn't have a special name for "sideways oriented CF3I", even though a complete, concise system would have to be able to provide a name for it.

Instead, we've come up with concise approximations - a SMILES string, a bitstring fingerprint, etc. - which are tractable for the purposes you want, so long as we stay within relatively normal chemistry. But it's still humans who categorize things into, say, "aromatic" or "chiral", so our approximate nomenclature has to partially encode how humans think of chemistry.

The Game of Life is much simpler than the Reality of Life.

Re:Is this c/10 spaceship known? by heavenlyhash on Wednesday March 09, 2016 @08:31PM (#11256903)
All of this is true. The word "close" was chosen very, very deliberately.

Though the Game of Life is surely simpler than the Reality of Life... if one were to flat out name the core concept as "godel numbers for chemical formations", it's certainly possible, don't you think? InChI isn't it, I agree; just wanted to toss the seed of the idea out there, with an example that's a lot "closer" to the target semiotics than a bunch of unnormalized floating point coordinates drifting around in xml.

"good enough is the enemy of good" can apply in spades here, so I appreciate your thorough analysis of specific weak points in InChI.

Re:Is this c/10 spaceship known? by dalke on Wednesday March 09, 2016 @09:15PM (#11257054)
InChI is not closer but actually further than SMILES or SD files for many of the use cases you wanted. It is not a supported capability to turn an InChI into a structure, which makes it hard to generate, say, a fingerprint for a Tanimoto search system. (Yes, the command-line tools and its wrappers support that, but the InChI developers do not condone its use. Even if you do so, the output may differ from your input structure in ways you disagree with.)

InChI is only closer for the classical purpose of chemical documentation - record association and text-based search. That is not a bad thing, but given the entirety of your goals, it is equally correct to use "close" for SMILES, SLN, SD, Mol2, etc.

Re:Is this c/10 spaceship known? by jonlawlor on Thursday March 10, 2016 @10:34AM (#11259753)
Side question: are there any open source synthetic chemistry projects that I can look at to get an idea of the techniques and problems encountered? I try to learn about a new non work related subject every few years and it piqued my interest but I haven't been able to find anything but textbooks - code is easier for me to understand.
Re:Is this c/10 spaceship known? by dalke on Thursday March 10, 2016 @02:27PM (#11261517)
I don't know enough about that topic to provide any sort of guidance. I don't even know who does, other than to ask on the Blue Obelisk mailing list at https://sourceforge.net/p/blueobelisk/mailman/blueobelisk-sm... .
Re:Is this c/10 spaceship known? by jonlawlor on Friday March 11, 2016 @09:12AM (#11266673)
Thanks, I've been having trouble finding a good place to start (looking) as well.
Re:Is this c/10 spaceship known? by david-given on Wednesday March 09, 2016 @05:08PM (#11256066)
It does help that Game of Life physics is somewhat simpler than Real Life physics. Of course, Real Life physics is a little less apt to collapse into a seething mass of undifferentiated matter of you poke it in the wrong place.

This is the slowest spaceship known, right? (Which isn't a machine made out of other parts?)

Re:Is this c/10 spaceship known? by Rangi42 on Wednesday March 09, 2016 @05:24PM (#11256134)
"A seething mass of undifferentiated matter" describes runaway exothermic reactions fairly well.

It also helps that Games of Life can be saved and reloaded. If your lab bench explodes, too bad, start over from scratch (assuming you're uninjured).

Re:Is this c/10 spaceship known? by heavenlyhash on Wednesday March 09, 2016 @05:28PM (#11256153)
Oh, of course, simulations without perfect replays would be an abomination! Not even worth mentioning! -- What are we, heathens who can't even manage the basics of reproducible builds?

(cough)

Re:Is this c/10 spaceship known? by kordless on Thursday March 10, 2016 @01:04AM (#11257586)
Hypothesis: We don't have perfect replays because there are multiple players.
Re:Is this c/10 spaceship known? by NoMoreNicksLeft on Wednesday March 09, 2016 @05:15PM (#11256098)
> It does help that Game of Life physics is somewhat simpler than Real Life physics.

Are we sure of that yet?

> Real Life physics is a little less apt to collapse into a seething mass of undifferentiated matter of you poke it in the wrong place.

Are we sure of that yet?

Re:Is this c/10 spaceship known? by dalke on Wednesday March 09, 2016 @06:52PM (#11256517)
Yes, GoL physics is simpler than Real Life physics.

RL follows quantum mechanics. As far as we know, its state cannot be recorded perfectly.

GoL is a Turing Machine. Its state can be recorded perfectly.

RL follows relativity. There is no equivalent in GoL.

Hashlife gives a method to compute GoL boards faster than processing each cell, and gives an exact answer. There is no equivalent for RL. At best there are probabilistic predictions. (There might be a 1E-50000 chance that the Sun won't rise tomorrow because all of the atoms in the Sun fuse at the same time and it blows up.)

Re:Is this c/10 spaceship known? by zardo on Thursday March 10, 2016 @10:08AM (#11259574)
I don't think we do know that. Maybe relativity and quantum mechanics are still 10 layers of complicated structures up from a far simpler ruleset.
Re:Is this c/10 spaceship known? by grkvlt on Wednesday March 09, 2016 @08:00PM (#11256778)
> RL follows relativity. There is no equivalent in GoL

Of course there is an equivalent of relativity! There's a fixed, ultimate speed-limit (i.e. c) of once-cell/time-step. It is not possible to transmit information faster than this in GoL.

Re:Is this c/10 spaceship known? by Dylan16807 on Wednesday March 09, 2016 @08:33PM (#11256908)
You can have C without relativity. There are no relative reference frames in GoL. Reactions only work at specific absolute speeds, and most of them only work at absolute speed 0.
Re:Is this c/10 spaceship known? by goldenkey on Wednesday March 09, 2016 @09:23PM (#11257079)
Relativity can exist in an absolute environment like GoL if you consider the momentum of the quantum vacuum virtual particles. Look it up :-)
Re:Is this c/10 spaceship known? by goldenkey on Thursday March 10, 2016 @07:36AM (#11258798)
Seriously guys. Downvotes for talking about digital physics? Sad me.

https://en.wikipedia.org/wiki/Superfluid_vacuum_theory#Relat...

"Relativistic quantum field theory"

Re:Is this c/10 spaceship known? by NoMoreNicksLeft on Thursday March 10, 2016 @10:42AM (#11259815)
Downvotes for asking whether we're certain of some rather ignorant assumptions. -4 for me.
Re:Is this c/10 spaceship known? by goldenkey on Thursday March 10, 2016 @12:08PM (#11260397)
Um, my first comment was just referring to the fact that in an absolutely framed turing-complete environment. One can sprout a quantum vacuum full of constant noise, ie. constant producing and annihilating structures(analagous to virtual particles.)

This is already experimentally observed in our own universe. Quantum noise exists in vacuums.

If you look at C in GoL as the fastest an actual black square can propagate, then of course you'll validate your naive assumptions that our universe could never be digitally replicated by GoL. But if you take the idea of implementing a primordial sea of quantum noise, and looking at the GoL board not as physical particles directly, but as a deeper construct. Then you can actually replicate relativity.

http://arxiv.org/pdf/physics/9902034.pdf

Re:Is this c/10 spaceship known? by forgotpwtomain on Thursday March 10, 2016 @12:33AM (#11257523)
> (There might be a 1E-50000 chance that the Sun won't rise tomorrow because all of the atoms in the Sun fuse at the same time and it blows up.)

To estimate probability of an event you must have a sample were both have occurred, to provide a probability for something like the Sun not rising tomorrow is pure non-sense.

Re:Is this c/10 spaceship known? by inimino on Thursday March 10, 2016 @02:21AM (#11257758)
You can easily calculate the probability of flipping heads a million times in a row, even though this also has never happened.
Re:Is this c/10 spaceship known? by trentlott on Thursday March 10, 2016 @03:04AM (#11257866)
Because we have sampled all states of the hypothetical quarter, and are constricting many, many values concerned with flipping.

The same can't be said for the atoms in the sun.

Re:Is this c/10 spaceship known? by lmm on Thursday March 10, 2016 @04:23AM (#11258118)
We have complete, verified descriptions of what the possible states look like. You can predict precisely how long it will take a cannonball to fall to the ground (at least in a vacuum), even if you've never dropped it from exactly that particular height before.
Re:Is this c/10 spaceship known? by dalke on Thursday March 10, 2016 @11:18AM (#11260052)
"Precise" - to within some tolerance. At some point you reach the uncertainty limits allowed by quantum mechanics.

You also have to make an arbitrary decision about when the cannonball touches the ground. How much interaction is needed between the atoms of the cannonball and ground before you say there's contact?

These issues don't exist in the GoL universe.

Re:Is this c/10 spaceship known? by eru on Wednesday March 09, 2016 @05:36PM (#11256187)
We are sure that Game of Life physics is simpler than Real Life _chemistry_. There, fixed that for you.
Re:Is this c/10 spaceship known? by Rhapso on Wednesday March 09, 2016 @05:49PM (#11256260)
It also helps that we GoL comes with the capacity to instantiate the universe in any configuration we wish, rather than being forced to coerce it into that state from scratch.
Re:Is this c/10 spaceship known? by eru on Wednesday March 09, 2016 @06:45PM (#11256478)
Not from scratch, but from inside!
Re:Is this c/10 spaceship known? by onnoonno on Thursday March 10, 2016 @05:08AM (#11258254)
Inside? Tell me what the outside is, then :)
Re:Is this c/10 spaceship known? by eru on Thursday March 10, 2016 @06:38AM (#11258590)
Outside the Game of Life is easy to tell.

Outside the universe ain't. But even though, I can confidently say that we are definitely inside.

Re:Is this c/10 spaceship known? by onnoonno on Friday March 11, 2016 @12:56AM (#11264896)
But does it make sense to even talk about inside and outside then when talking about the universe?
Re:Is this c/10 spaceship known? by Rhapso on Friday March 11, 2016 @04:53PM (#11269818)
It makes about as much as uncountable infinite numbers. I can say everything in the universe is within a countably infinite distance of me. Thus, anything an uncountable infinite distance from me is outside the universe.

Not a very tangible idea, but not useless of purpose of reasoning about the affairs of things.

Re:Is this c/10 spaceship known? by eru on Saturday March 12, 2016 @09:39PM (#11275879)
It's a bit of an abuse of notation. Talking about the inside definitely makes sense. (Talking about the outside is a bit like talking about the empty set.)
Re:Is this c/10 spaceship known? by lmm on Thursday March 10, 2016 @04:25AM (#11258126)
Yes. Real Life physics has been proven to be either nonlocal or nondeterministic (Bell inequalities). Life physics is both local and deterministic.
Re:Is this c/10 spaceship known? by scythe on Wednesday March 09, 2016 @07:03PM (#11256558)
Topologically, encoding a 2D structure into a 1D line of text is dramatically simpler than encoding a 3D structure into a 1D line of text. To motivate this simply, recall that no graph whose minors include K5 or K3,3 can be drawn in the plane, whereas any graph can be drawn in 3D. It gets even simpler because all GoL graphs are confined to a grid.

tl;dr: easier problem is easier!

Re:Is this c/10 spaceship known? by dclowd9901 on Thursday March 10, 2016 @01:53AM (#11257703)
3D software development does it with tuples all day long.
Re:Is this c/10 spaceship known? by creshal on Wednesday March 09, 2016 @05:32PM (#11256167)
> Now if only we had descriptions of chemistry that were this terse.

Chemistry is dealing with a lot, lot more of concepts than the study of the Game of Life. Brevity only works when you have few enough information that you can map it to only concise words.

(Entropy strikes again, even if it's information entropy for a change.)

Re:Is this c/10 spaceship known? by zrm on Wednesday March 09, 2016 @07:23PM (#11256630)
> (Entropy strikes again, even if it's information entropy for a change.)

Information entropy and physics entropy are actually the same thing. You can measure heat capacity in bits.

Re:Is this c/10 spaceship known? by creshal on Thursday March 10, 2016 @04:09AM (#11258077)
…huh. That's neat.
Re:Is this c/10 spaceship known? by pervycreeper on Wednesday March 09, 2016 @05:36PM (#11256189)
IUPAC names are needlessly verbose and insufficiently descriptive.
Re:Is this c/10 spaceship known? by theophrastus on Wednesday March 09, 2016 @06:32PM (#11256434)
if InChI doesn't do it for you, i suppose SMILES[1] isn't sufficient either? By-the-bye, you're not ever going to be able to "concisely" encode 3d (or even 2d coordinate) structures, because there isn't just one such. They're a thermally sampled average of structures.

[1] https://en.wikipedia.org/wiki/Simplified_molecular-input_lin...

Re:Is this c/10 spaceship known? by dalke on Wednesday March 09, 2016 @07:07PM (#11256573)
heavenlyhash wants three things: 1) pass structure information around so it can be simulated or reproduced, 2) a deterministic ID for sharing and linking chemical information, and 3) viable methods for determining identity and similarity from the cloud of all chemical configurations.

SMILES is better at #1 than InChI, but not as good as a 3D structure representation. But the 3D structure isn't as compact, and offers few advantages for structure identity for small molecules where the 3D configuration is more easily predicted from geometry.

InChI is better for #2 than SMILES because different tools generate a different canonical structure, and because general purpose text search engines like Google don't do so well with SMILES as InChI keys.

Fingerprints, either binary or count, are more often used for the similarity aspect of #3, than n-gram solutions using the SMILES directly (like LINGO), or any method based on InChI. Also common are 3D shape and electrostatics comparison methods, with attempts to sample configuration space.

And for certain chemical structures other approximations are even more important. DNA similarity is based on very different principles than used for small molecules.

Re:Is this c/10 spaceship known? by theophrastus on Wednesday March 09, 2016 @07:28PM (#11256649)
In my humble experience "1)" and "2)" are sufficiently overlapping as to be indistinguishable. Whereas "3)...identity" only demands that the same system be used for both the search compound and the database ("cloud"). For that, a particular implementation of "canonical SMILES" is perfectly respectable. But it's a notably different world once one gets into "3)...similarity". With that you've opened a vast library of doctoral theses, commercial promises, and ingenuity, (and essentially my entire career). And yes, as you suggest, DNA similarity is a wholly different beast.
Re:Is this c/10 spaceship known? by heavenlyhash on Wednesday March 09, 2016 @08:57PM (#11256992)
Taking dalke's enumeration and running with it... I'd support that "1)" and "2)" are ever so slightly different: defining a serialized form that can reheat to a consistent snapshotted simulation state is one thing; and is necessary but not quite sufficient for "2)". Defining the serialized form to be deterministic is quite an important next step, because that makes a lot of things go from `O(some)` to `O(1)`.

Very close, yes. But if we compare to, say, reproducible builds (because it's also dear to my heart), the consequences of that difference are legion. For example: the `tar` command can definitely extract you a filesystem, yes, absolutely. However: whether or not two `tar` implementations (or even the same implementation, run twice in a row) produce the same byte stream is make-or-break for whether someone else can follow your procedure and get the same result.

If the process is deterministic, the identity check is cheap: hash it. If the process requires unpacking again to do semantic checks on the contents, the amount of time is... well, if we're hand-waving on the format, essentially unbounded.

So... yeah, "canonical SMILES" is a valid answer; that "canonical" part is just really important.

Re:Is this c/10 spaceship known? by dalke on Wednesday March 09, 2016 @09:03PM (#11257012)
InChI Key is an example of #2 that does not imply #1.

For a variation on the theme, if we all agreed on a canonical SMILES method, then the SHA256 of that could be used as a key to connect records, without revealing what the underlying structure is.

This is done now, with InChI Key, when two companies want to compare overlap without sharing information about internal compounds. (There was a paper about this last year or so, but I can't find it.)

I also pointed out that InChI Keys are better for text-based search engines. As an extreme example, I could produce a line notation which uses only the characters "(", ")", ".", and "-". It would be fine for #1, but poor for #2 for any database search engine which expects some concept of "words" made of letters.

This is why I distinguish #1 from #2, even though they are indeed close.

Re:Is this c/10 spaceship known? by dalke on Wednesday March 09, 2016 @09:19PM (#11257068)
As a structural biochemist, you may have use some of the software I've helped write or contributed to. ;)
Re:Is this c/10 spaceship known? by dnautics on Wednesday March 09, 2016 @08:43PM (#11256941)
Chemistry isn't even fully expressible using naive graph structures (atoms = vertices, bonds = edges), for example, eta-2 metal-pi bonds where the chemical bond is between an atom and another bond.
Re:Is this c/10 spaceship known? by duaneb on Wednesday March 09, 2016 @05:36PM (#11256188)
The terseness vanishes when considering the complexities of interactions and possible classifications. In fact, I'd say that the above terseness is only possible because it's about half of ALL the interesting effects possible in the game of life.
Re:Is this c/10 spaceship known? by theoh on Wednesday March 09, 2016 @07:12PM (#11256587)
Given that what's being shared is a very small bitmap, wouldn't hex would be more concise?