This comes from the same dev known for the 128-language quine relay, where each of the 128 languages prints a program in the next one, looping all the way to the original one. In alphabetical order and as ASCII art, no less.
This project has always fascinated me, so I tried making a tiny uroboros quine with Python -> Javascript -> Python -> etc. I started with a quine for each language, and tried inserting them into each other, but the output always grew exponentially.
So I checked how it's done in the Github repo[1], but the language snippets only seemed to be quoting and printing without any self-references like you'd expect in a quine...
Then it hit me. You only need the quine machinery in one language. If I can make a Python script that has a string with its own source code, then the Javascript code will simply be `console.log(py_source)`, no manipulation necessary.
If there were more languages, then it'd be `console.log("System.out.println({python_source})")`, etc. The problem then becomes escaping inner quotes, and escaping the escape characters themselves. I managed to sidestep the issue by using two types of quotes, and relying on Python's `repr` also giving valid JS strings, but if I had to add just one more language I'd need a lot more scaffolding.
I still think the Quine Relay is a tour de force, but now for different reasons. It's not 128 quines in different languages, but an incredibly robust system for escaping strings in 128 wildly different languages.
> and to even know if such a thing is possible before pursuing it
I'm not the creator of that magnificent piece of programmatical art. But I can take a stab at this. As long as the languages are Turing complete it is possible.
Any Turing machine can simulate any other Turing machine so once you step up to that level the challenge is keeping your head through the maze of nuances between many of those languages. I think the logic behind it goes something like this, if a language is complete (eg in the Gödel sense) then you can have it produce things that are nonsense in its own language.
Anyways I would expect the bulk of the work to be making those incremental step of going from each language to the next. In terms of data shape, I am thinking a linked list. So the final step is to call them all in a nested fashion, bootstrapping each up onto the top of that stack as you go.
The quines are not simulating each other, they are just printing a string after some formatting (which usually involves embedding a copy of the string into itself). There's no Turing completeness needed (most of the quines don't even have branches), much less Gödel encodings.
He's got a book! ...in Japanese. I hope someone can help him translate it into English so more people can learn about this kind of thing and he can be rewarded for his adventures.
> Prepare a script that deletes one character randomly:
Hmm, but can it also deal with general bit flips? Because that's usually what radiation does not delete characters. The only case it would delete a character with a bit flip on the data would be causing the DEL char 0x7F i think, which 7 ASCII chars have a 1 in 8 chance of mutating into (because we have 8 actual bits but only 7 are used for ASCII): ~}{wo_?
There are 96 ASCII characters that might be used in source code naively assuming equal character probability that's 7/96 * 1/8 = 0.9% chance of a bit flip deleting a character by mutating into 0x7F. There's also a chance of a character mutating into a non-printable character (0-31), only the 2nd and 3rd column of ASCII can mutate into this by ending up with both high bits off, so there are 64/96 chars with a 1/8 chance that's an 8.3% chance of mutating into a non-printable control char etc (i'm ignoring LF because it displaces DEL). If the 8th bit flips into a one on any char then we get extended ASCII I think, that's 96/96 * 1/8 = 12.5% chance. That leaves 78.3% chance of mutating into another regular printable ASCII character. Apologies for any bad math.
There are a lot of possible affects on the interpreter when it sees any of those characters, the control chars could be particularly troublesome.
Possible -- depends on the rules of the specific challenge. Most of the time it's edits, deletes, or some combination. Sometimes the score depends on how many edits your code can withstand.
Ah, I wasn't aware it was the name of a common code golf challenge, I do code golfing myself but apparently not enough :)
I guess it makes sense people would frame the game that way, arbitrary bit flips seems way too hard, I'm not even sure it's possible for a program to cope on it's own.
Physics guy here. Isn't the solution to simply duplicate the code and compare it before execution? Do it 3 times and use the majority. This could be the preamble to any quine. (I realize though that, like most physics people, I enjoy waltzing into a specialized domain that I know nothing about and reduce it to first principles. But hey, it's who I am.)
Yes, triple redundancy is nice, but then the problem becomes how to make the code that checks the code also tipple redundant and checked without creating another layer to deal with.
Most software that does this simply tries to make the test code as small and reliable as possible. But it's an interesting challenge to make the test code somehow self checking with the same properties.
Well, physically, you really need three independent machines. Which means three copies of the file, three processes, three verifications, and so on, and a way for those processes to communicate with each other and "vote". Then you run into the problem of definition - is a cluster a quine? Note that most of the "primordial bit flip" problems go away if you make N >> 3 and design each machine to "fail fast".
> Isn't the solution to simply duplicate the code and compare it before execution? Do it 3 times and use the majority
Yes, voting is a common way to deal with radiation or critical software. There are of course also complications about the voting software itself needing to also be redundant. Some can be done with hardware, or you can just radiation harden parts of the system (reducing overall cost).
This is definitely one of those problems where at a quick glance it seems like there's a few simple solutions that can resolve 90% of issues but when you dig into the weeds you find out that 20% dictates most of the outcomes and there's at most a 10% overlap with your quick/obvious solutions.
Hardware radiation hardening techniques have existed for a long time, and are applied commonly in space, satellites, nuclear power, military.
Roughly speaking it breaks down into a couple categories including the manufacturing of electronics and chips themselves, including everything from substrate differences to using entirely different types of RAM and block storage [0], to the higher level strategies employed by many generations of space probes where a variety of total system redundancy is employed, e.g the Voyager probes used discrete component level redundancy, and most modern probes use almost full system redundancy where they run 3 complete computers in lock step, the idea being that triple redundancy is the minimum needed to detect which computer is wrong.
Another potential strategy not so commonly applied for this purpose is software resilience, such as the techniques applied by the Minix3 microkernel, the idea being to minimise the critical kernel code to be so small that it's unlikely to have bugs or be affected by hardware level affects, then everything else underneath can be kept alive by the kernel, even block device drivers, by employing triple redundancy and a "resurrection server". This was intended to protect against bugs in critical software like device drivers and hardware/firmware bugs rather than radiation, but it could be similarly effective especially as a layered strategy.
See also the International Obfuscated C Code Contest. [0]
This program [1], for example. It just accepts some input on stdin and returns the same input, but mirrored along the diagonal. So the first row of the input becomes the first column of the output, second row becomes second column, etc. But the program is functionally invariant when given itself as input. In other words, you can flip the source code of the program along its diagonal and the result is a program which has the same functionality - it flips stdin.
Or this one [2], which parodies java in C. It's functional C code that looks like Java, including the
class LameJavaApp
{
/** The infamous Long-Winded Signature From Hell. */
public static void main(String[] args)
...
Or this one [3] that calculates pi by estimating its own surface area.
Or this one [4]. It's a lovers quarrel, written simultaneously in C and English. It's incredible, seriously, read it.
At the most basic, you just have N+1 copies of the program, and run whichever one is longest, since that must be the one with no missing characters.
The program itself then prints N+1 copies of itself...
You just need a little care about the start of the first program, since that is the 'entry point' - it needs to fall through to the 2nd program if the first is damaged.
There's a great video recently by Kurzgesagt video recently[0] on just how hard the immune system works to identify and kill any cell that is not cooperating anymore.
In a nutshell, the DNA fails at protecting from changes all the time, and the immune system is constantly checking for that and killing off those cells.
It pretty much is, but it's not rad hard in the sense that you can change or delete any one letter. Well, maybe in animals and plants, since we have at least two copies of most genes.
DNA doesn't make a copy of itself, the cell makes a copy of the DNA. DNA doesn't really do anything, it requires RNA and proteins to actually do anything.
There's a definitional problem here. Would a book with instructions for how to order additional copies be a quine? What's the difference? I don't know exactly.
I guess the right question to ask about DNA is, does it contain all the instructions required to produce a copy of the DNA itself? DNA translation involves a bunch of RNA, sure. But DNA copying is mostly done by DNA polymerases, which are typical peptide based proteins encoded in the DNA itself, right?
So in a real sense, the DNA contains the blueprint for the machinery to copy the DNA itself, but not the instructions for building that machine from the blueprint, the same way a software quine doesn't necessarily include the source code for a compiler.
Definitely a definitional problem, but that's my shot at resolving it a bit.
Then again, DNA polymerase is not perfect, and DNA is not immune to single nucleotide changes having a real effect, so it's only a quine in the "spherical cow" way of looking at it anyway. But it's certainly the most "quinish" thing in nature that I can think of.
I just don't think it's accurate to say DNA has instructions in the same way a computer does. It's more like a recipe for a chemical reaction. If we expand the definition of a quine away from being self reproducing code and to self reproducing chemical reaction, it seems like things like crystalization or fire could be considered a quine.
But I may have been a bit unclear about my mapping of computer and biology terminology to this question.
I tend to think of a computer programs as being mathematical machines, and proteins as being molecular/chemical machines. Motor proteins "walking" along microtubules is the most vivid example of this.
I'm sort of torn between both worlds here, honestly. I like both perspectives. Viruses especially have a very quinish quality to them in that they're stripped down to just enough stuff to get a host cell to make more viruses.
DNA includes instructions for how to build all the machinery needed to make a copy of itself, including the surrounding cell, and RNA, and proteins, and the organism that is capable of gathering food/fuel to obtain the all the raw materials to build everything.
No it doesn't, it holds a recipe for creating proteins under specific chemical and biological conditions. If you put human DNA in a chicken egg, it wouldn't hatch a human.
And if you write a quine computer program on a piece of paper, it won't create a copy of itself further down the page.
Or if you put a fully-functional cell in the vacuum of space, or the heart of a star, it won't replicate either.
All replicators need a suitable environment to replicate in. The fact that inhospitable/non-viable environments exist does not negate the fact that they are actually replicators.
The program doesn't make a copy of itself, the runtime makes a copy of the program. Program doesn't really do anything, it requires runtime and cpu to actually do anything.
In some cases, this is in fact a useful way to look at it.
The DDC model[0] proposes that one of the drivers of evolutionary change is polyploidy, where after an organism has multiple copies of the genome, genes are free to drift into new functions.
An organism with four copies of a gene instead of the usual two is more rad-hardened than the basal non-ploid organism.
I think it’s just aesthetically reminiscent of radiation hardening. Pretty sure protecting agains arbitrary bit flips is impossible. If the MSB of the first character gets flipped, the code is illegal no matter what you do.
The author of this quine (Yusuke Endoh) has a Github repository which encodes a program in the Github contributions graph. I have no idea what the program does but here is a link to the start of it:
Not sure about “e xit” off the top of my head, this isn't one of my “natural” languages, but I assume breaking eval is protected against by the multiple invocations and the fact that assignment is an operator that returns its result as well as setting the target variable. If one of the evals is broken (or one of the =s between is removed) it just becomes a variable that is assigned to and the result is passed along. Three evals is enough to give the “any single character deleted” survivability, for “any two characters” you would need five (and many of the other tricks would need to be altered/expanded also).
There would also be a difference between deletion and replacing with a space character. Ie shorten the program file by one char (however many bytes depending on encoding). Can anyone explain what deletion means in this useage?
I'm quite confident I understand what is going on with such things, so it isn't black magic to me, but I doubt I'd be able to implement these tricks to do something like this myself in any practical amount of time.
Any known issues when radiation deleted (instead of altering) any characters? Deleting something is introducing significantly more entropy than altering because it alters the length of the array of text, but altering the array requires recalculating of the rest of the array which is impossible outcome of radiation.
There are multiple versions in the repo. The first one is essentially just two copies, the second was an improved design from someone else and the last was an ASCII-art version (of the radiation symbol) that was based off the second.
What are the advantages to radiation hardening software? In the cases I've run into the thinking has been "if you can't trust the hardware then you're already lost".
Defense in depth. Like the Space Shuttle that had four rad hardened processors. And a voting system to reject anomalous outputs. With two you don't know which one is right. With three you're OK. Four allows for one to permanently fail and still leave three.
This is analogous to having at least three NTP servers. Or filesystem level checksums on top of ECC RAM and LDPC in the SSD. Or TCP checksum on IPv4 header checksum on Ethernet/LTE/Wi-Fi checksum.
Protecting against cosmic bitflips for example, relevant if you write software that ends up on airplanes/space crafts. Also if you just want resilient software that work even though hardware is starting to fail. See https://en.wikipedia.org/wiki/Soft_error
https://github.com/mame/quine-relay