Register | Sign In


Understanding through Discussion


EvC Forum active members: 65 (9162 total)
9 online now:
Newest Member: popoi
Post Volume: Total: 915,815 Year: 3,072/9,624 Month: 917/1,588 Week: 100/223 Day: 11/17 Hour: 0/0


Thread  Details

Email This Thread
Newer Topic | Older Topic
  
Author Topic:   The Minkowski's challenge
Barbarian
Inactive Member


Message 6 of 120 (352120)
09-25-2006 2:13 PM
Reply to: Message 1 by Albert Godwin
09-25-2006 11:37 AM


Albert,
although it has been a while since I last had to I proofread 16 bit Intel assembly and QBasic of MSDOS 5.x fame, I am pretty comfortable telling you that the code has unnecessary built-in limitations which make its "macroevolution" impossible.
(a) The virus code is severely limiting the potential length of the resulting code. It can generate extra bytes at the end of the code, but the resulting byte sequence is truncated to the original file size when written out. There is simply no room for any novel functionality to arise in those fourteen extra bytes available for growth.
If you remove this limitation, it becomes possible for the copier to replace the whole code with a totally different program, although the probability of it happening would be minuscule. Note that this is not how evolution works in the wild, this is how tornadoes assembling JumboJets in junkyards would work.
(b) The selector is deterministic, i.e. it always kills a virus if it finds one. This makes it necessary for the whole new functionality to evolve in a single jump, already with its effects / encryption? / showing in the code, or else the selector finds it and eliminates it, resetting the evolutionary clock. Real NS is more stochastic: bad design is not immediately eliminated, it has a higher probability to disappear over generations. So if the selector was a bit more lax (more in line with real NS), it would allow imperfect new functions to survive for the next round of replication.
With those two restrictions removed, it is possible to evolve any program at all from the original replicator, as long as all versions along the path can replicate themselves. This is no restriction at all: you could grow the new program at the end of the copying code and lead execution flow through it only after it is complete.
This is not how real evolution would work, though. For a better analogy, you could for instance have functional blocks in the code, which can be duplicated as a whole and then one of the duplicates hijacked for the new functionality, presumably somehow related to its previous functionality and thus requiring fewer mutations. You could have a notion of fitness of functionality, allowing barely better functionality to confer a reproductive advantage over minimally worse functionality <-- junkyards.
Check Avida for an example how does this work in a correct simulation.

This message is a reply to:
 Message 1 by Albert Godwin, posted 09-25-2006 11:37 AM Albert Godwin has not replied

  
Barbarian
Inactive Member


Message 10 of 120 (352337)
09-26-2006 8:51 AM
Reply to: Message 7 by Albert Godwin
09-26-2006 3:30 AM


quote:
You are all trying to convince me that forcing a small stupid self replicator to evolve encryption is harder than the whole evolution of men?
I do not see it this way. I am trying to convince you that forcing this particular small stupid self-replicator to evolve any significant new functionality is flat out impossible because of built-in unnatural limitations, enumerated under (a) and (b) above.
quote:
Dear Barbarian,
I am not assembly expert, but please notice that the least mutation in biological systems is disastrous as well. so this program is no difference.
I disagree: the program is an exceptional case, and its failure to evolve novel functionality has no bearing to the feasibility of biological evolution. The program is limited to create offspring with the same size as itself. Since it is impossible to fit the mechanism needed to evade detection into that size, and the selector immediately kills all offspring with a less than perfect evasion mechanism, we can conclude that there is no evolutionary pathway starting from GEN.COM and resulting in a virus with detection evasion mechanisms because of these design decisions.
As for biological systems being brought down by mutations, I am no biologist, but genetic mechanisms look to me like they are padded with redundancy and loose coupling of functionality all over the place. IOW they are suboptimal in terms of representation of offspring-building code, and therefore point-changes have a hard time to bring them down. The problem is with the human frog-perspective on replicators or indeed on iterative systems: if we need a mental image, we build a minimal one, and that is prone to be locally optimal as a side effect of being kept simple. A locally optimal replicator could indeed admit harmful point-mutations only, but these replicators we build for easy illustration, like the program in the OP, are in no way representative to biological replicators. In fact, by saying that all mutations need to be harmful, you say that all replicators, at all times, are locally optimal. Given that the environment keeps changing and renders even optimal solutions moot, this cannot be the case in the real world.
I also would like to urge you again to check out the Avida site I linked to in my previous post, and explain why does Avida work if all mutations need to be disastruous.
quote:
Can i now conclude that you all failed to force this program to evolve encryption?
As far as I am concerned, you can conclude that. However, this does not mean what you said in the OP:
quote:
And if you can't, will you please stop saying that the whole of those creatures did evolve?
I do not see why should I do so.
---------------------
On a different note, if we are going to discuss the program itself any further, I would need to take another look at it, because as we stand now, I am going by memory.

This message is a reply to:
 Message 7 by Albert Godwin, posted 09-26-2006 3:30 AM Albert Godwin has replied

Replies to this message:
 Message 11 by Albert Godwin, posted 09-26-2006 9:56 AM Barbarian has replied

  
Barbarian
Inactive Member


Message 13 of 120 (352355)
09-26-2006 10:48 AM
Reply to: Message 11 by Albert Godwin
09-26-2006 9:56 AM


Hi, Albert -
quote:
If this thing (i.e. YOUR program) Evolves encryption then i will become an atheist tomorrow and believe in evolution.
the temptation is big, very big indeed, although perhaps evolution is not a thing to be believed on: we merely say that it is the only possible explanation we have at the moment. Besides, I am ambitious enough that I would do this just for the sake of putting this particular claim to rest before it finds its way to the Index of creationist arguments.
However, let me ask a few questions first:
(1) is the task to evolve a mechanism which helps eluding a selector looking at patterns of N bytes? What is N? (I could tell right away if I saw the QBASIC code.) Am I right in calling this a stealth mechanism and not an encryption one?
(2) do I get to change the selector too, to be more stochastic? Right now the selector goes and kills on sight all viruses (= programs containing a certain sequence of bytes). It should measure the difficulty of recognizing a virus and give them a chance of survival proportional to that difficulty.
(3) do I have to use Intel 8086 machine code in a PC BIOS + MS DOS environment, as the OP does? I could easily do that - all I have to do is break out the Norton Guides and feel young again -, but I think I could propose a simpler virtual machine code, which would allow me to do 4) below, do away with the fundamental DOSyness of the OP program and make us start from the same base, as both of us would be beginners for that kind of code.
(4) it may be that the evolution of a stealth mechanism becomes possible but not in human timeframes. If that is the case, would you accept a formal proof instead of a physical experiment? The proof would try to show that after a huge number of iterations the probability of having a working stealth code goes above 90%.
(5) is there anything to speed up the process of approval from the original author to publish the code again? I would want to keep the solution as close to the original one as possible.
(6) would you be so kind as to check out Avida?
quote:
But if you can't don't keep on writing theoritical posts here. Fine ?
No, that is not fine at all. But I might of course reconsider if you told us what is your objection to making theoretical posts here.

This message is a reply to:
 Message 11 by Albert Godwin, posted 09-26-2006 9:56 AM Albert Godwin has replied

Replies to this message:
 Message 17 by Percy, posted 09-26-2006 11:26 AM Barbarian has replied
 Message 20 by Albert Godwin, posted 09-28-2006 6:03 AM Barbarian has replied

  
Barbarian
Inactive Member


Message 19 of 120 (352583)
09-27-2006 7:22 AM
Reply to: Message 17 by Percy
09-26-2006 11:26 AM


quote:
If all Albert is looking for is an example of a code creature species hiding from a predator or otherwise protecting itself from selection pressures by evolving camouflage, then this should be easy. This happens in ALife all the time. In fact, it's so incredibly common and mundane that I don't think you should even go through the effort of coding yet another one, though it would be a fun exercise and well worth engaging in from that standpoint.
IMO the best - and still pretty weak - argument for doing it anyway is that even if we convinced Albert about the relevance of prior work in this area, the challenge would still have to be met directly in order to convince the more literal-minded segment of the population; stating that e.g. Tierra or Avida proves its doability could sound like cop-outs for many.
Basically, I planned to go through the proposed rule amendments one at a time and making it clear for Albert why am I proposing them. Such an exercise could lead to a lot of useful results. I know that under those amendments the task would be tedious but ultimately pretty simple, although getting it actually run to completion within a few hours could be challenging or even impossible.

This message is a reply to:
 Message 17 by Percy, posted 09-26-2006 11:26 AM Percy has not replied

  
Barbarian
Inactive Member


Message 22 of 120 (352762)
09-28-2006 7:03 AM
Reply to: Message 21 by Albert Godwin
09-28-2006 6:05 AM


Sorry, missing the code was entirely my mistake, when I returned to the original proposed OP I thought the code got snipped b/c there was some discussion as per the appropriateness of posting long excerpts or something like that. Please consider those requests moot.

This message is a reply to:
 Message 21 by Albert Godwin, posted 09-28-2006 6:05 AM Albert Godwin has not replied

  
Barbarian
Inactive Member


Message 25 of 120 (352805)
09-28-2006 10:36 AM
Reply to: Message 24 by Percy
09-28-2006 9:40 AM


quote:
I'm not sure why Barbarian didn't bring this up, but in reading the Minkowski/Faust discussion it seemed apparent that by encryption they actually meant camouflage. As Minkowski discovered when he ran his program, it achieved camouflage by slightly altering its code. As Minkowski himself says about the evolution of encryption, "that's not obligatory." Yes, encryption would also achieve the goal of hiding from the selector program, but so do very minor changes to the code sequence.
I tried to clarify that in the proposed amendment #1 above, but my English let me down and I could not promptly remember the word 'camouflage', so I proposed 'stealth' instead; nonetheless, 'camouflage' is a much better choice.

This message is a reply to:
 Message 24 by Percy, posted 09-28-2006 9:40 AM Percy has replied

Replies to this message:
 Message 26 by Percy, posted 09-28-2006 10:43 AM Barbarian has replied

  
Barbarian
Inactive Member


Message 27 of 120 (353034)
09-29-2006 4:04 AM
Reply to: Message 26 by Percy
09-28-2006 10:43 AM


Ah, ok, I misunderstood your post then. The reason was that I wanted first to think a bit about my next couple of moves here, and some pretty promising variants did in fact involve going along with this different notion of encryption. More soon.

This message is a reply to:
 Message 26 by Percy, posted 09-28-2006 10:43 AM Percy has not replied

  
Barbarian
Inactive Member


Message 28 of 120 (353038)
09-29-2006 4:29 AM
Reply to: Message 20 by Albert Godwin
09-28-2006 6:03 AM


Hi, Albert -
I am coming closer to get what the OP is trying to say: it seems to claim that the evolution of mutually dependent traits is impossible if the presence of only some but not all of them is detrimental to the organism, because there is no right order in which they could evolve, and that this makes all "macroevolution" impossible as well? Encryption is not meant to evade virus protection but to exemplify a set of traits - encryption cability, decryption capability and being encrypted - which can only appear together or the program is bust? I'll assume this is what you say, but please correct me if I misunderstood it.
This is a slightly different ballgame then. You want the program to hide part of its code by some sort of scrambling, byte-by-byte - there should be a routine that does the scrambling before saving, one that does the unscrambling and then passes control to the resulting code, and this unscrambled resulting code must do something, it must be executed. In addition, all this must be achieved step-by-step.
Now, depending on the exact definitions, this could be anywhere between trivial and impossible. Some stuff to consider: what is an acceptable scrambling? Adding 1 to each byte? XOR-ing it to a randomly chosen segment of the ROM BASIC code byte by byte and storing the start address of the chosen segment? Full-blown DES encryption? I propose that a deterministic, one-to-one replacement of every byte value, regardless of its position, should suffice as encryption/scrambling (e.g. adding 1 for scrambling and subtracting 1 for unscrambling should be sufficient).
What is the function and size of the code which needs to be hidden this way? Can it be a single NOP? Must it contain all the file-writing code? And: must it be executable over the whole evolution pathway? I propose that the code segment in question must be executed in the final result (but not in all previous generations) and that it have a minimal length of 12 bytes (so there is no restriction as to the actual function it performs - we only need to execute it to prove that the unscrambling did happen).
I would propose two more amendments to the rules for this challenge.
(7) a sequence of selectors may be used. I.e. we use one selector to evolve some trait, then when that is done we use another selector until the trait evolves into something else, and so on. Note that this is what happens in nature all the time: environments change. Real environment changes regardless if certain traits have already appeared, but we need to link the two because we want a certain result, we are reverse-engineering a teleological mechanism here.
(8) we should remove the error generating mechanism from the code. Most of biological evolution happens over mechanisms which seem to try very hard to produce exact copies, so mutations are essentially errors of that mechanism. I propose that mutations happen after file writing, during the copying to the new directory or whatever corresponds to that step. It should not be possible for a program to evolve the capability of not mutating at all. (In a virtual machine, replacements of bytes would also happen as random mishaps during store operations, not under the control of the code.)
Incidentally, if I posted a solution, would you be able to verify it? You said you were no assembly expert. Virtual machine?
quote:
No, i am sorry. If you can evolve steath (which will not either happen, ny the way) that's not the challenge. the challenge is to evolve encryption. and do it in real programming, no virual simulations and no formal proofs. i want a practical responce.
There is a lot of manual work involved in getting the next generation. Run the selector, create different directories, move survivors to them one by one, rename them to Gen.com, run them etc. If you are extra lucky, you can do ten generations hourly, and even that with a relatively small population. I am willing to put up with the - btw. incorrect - assumption implicitly present in the challenge that any replicator over any substrate can evolve into anything at all, but I draw the line at adding the clause "over arbitrarily small number of generations". That is simply not a realistic restriction. It could take 100.000s of generations to evolve something useful, and that would only prove that it is impossible to do it manually; living things had enough time to do that and much more.
A virtual simulation would have all the advantages we need here. It could manage the whole cycle - generate-select-verify - in a much shorter time. We could do away with dangerous things like one-byte interrupt calls which could easily damage the filesystem on your disk, or do damage to older harddisks or monitors. The particular machine code is complicated, and while that complexity is not a principial showstopper in any of the theoretical questions we try to tackle here, it could still make the effort practically unrealistic. Note that this does not mean that processes of similar character are unrealistic in nature, with more time and resources at its hands. If I understand your challenge correctly this time, I will insist on either the use of a virtual machine, or on a detailed explanation from your part about why do you think a virtual machine is a bad idea, because I don't really get it.
I am also worried about your dismissal of 'theory'. For instance, in 'theory', the probability of having the mutation shown in the OP in one step is approximately 0.00000003, as calculated from a few assumptions (the code size is appr. 170 bytes and the random generator is a uniform generator of one-byte values, so the probability in question = P(one mutation at the exact spot) * P(the mutation is an insertion) * P(the inserted byte is 52H=PUSH DX) = (255^169)/(256^172) = 0.00000003...). Does this fall into your 'theory' category? If it does, why is it not acceptable as a replacement to actually generating tens of millions of files and verifying each one of them? I did not plan to use as proof anything more complicated than this kind of calculation.
quote:
by the way, if you have read the original Marcus Minkowski/Faust Amoyo discussion, the program indeed DID evolve. but that's just a minor evolution, not marcroevolution.
I saw it, but I never said the program could not evolve at all. I said there are severe limitations to what it could evolve to, considering the inherent size limitation and the very restrictive selector.
quote:
I just said that because i didn't want to see stupid replies, just like the one Rick posted right after my last message.
I do not see at all what was stupid in that reply, and I wish you explained it in more detail. In addition, you addressed the restriction to either me or to an abstract 'you', not just to Rick. When I suggested that you should explain your demand, I sort of expected that you would point out whatever seems to be 'theoretical' in my previous posts. You should consider that we most likely do not share your idea about what is and what is not inacceptably theoretical (although I suspect it is more like 'conjectural' you are hinting at here), so for the sake of communication, you should walk the extra mile and explain it to us.

This message is a reply to:
 Message 20 by Albert Godwin, posted 09-28-2006 6:03 AM Albert Godwin has not replied

Replies to this message:
 Message 30 by Percy, posted 09-29-2006 5:37 AM Barbarian has not replied

  
Barbarian
Inactive Member


Message 33 of 120 (353062)
09-29-2006 8:06 AM
Reply to: Message 32 by Percy
09-29-2006 7:42 AM


Re: Examining Avida
Percy,
the Avida for Windows binaries are here. (Otherwise, the Avida main page, http://dllab.caltech.edu/avida/ has the link in a box in the upper left (Current release ... Download: ... ))

This message is a reply to:
 Message 32 by Percy, posted 09-29-2006 7:42 AM Percy has replied

Replies to this message:
 Message 34 by Percy, posted 09-29-2006 8:17 AM Barbarian has replied

  
Barbarian
Inactive Member


Message 35 of 120 (353071)
09-29-2006 8:36 AM
Reply to: Message 34 by Percy
09-29-2006 8:17 AM


Re: Examining Avida
Sorry - I thought you missed the link itself. Avida can be run by entering the directory Avida2.0-beta6/avida-work/, and executing either qt-viewer.exe or ncurses-viewer.exe.
ETA: I have just downloaded and run them. qt-viewer opens a can of 'file read error' on me, but ncurses-viewer runs fine.
Edited by Barbarian, : additional info

This message is a reply to:
 Message 34 by Percy, posted 09-29-2006 8:17 AM Percy has replied

Replies to this message:
 Message 36 by Percy, posted 09-29-2006 9:07 AM Barbarian has not replied

  
Barbarian
Inactive Member


Message 37 of 120 (353093)
09-29-2006 9:49 AM
Reply to: Message 20 by Albert Godwin
09-28-2006 6:03 AM


Hi, Albert
a few more details, while we are at it:
Why is encryption needed? The program could contain the encrypted portion and never execute it directly, only after decryption. Having only an encrypted portion and the corresponding decryptor is just as irreducibly complex, isn't it? If the decryptor runs on a non-encrypted code portion, it will create nonsense code, and if we have a non-functional decryptor, the encrypted code is useless. I propose to do away with the encryptor part and focus on breeding a program with an encrypted part and a decryptor.
I propose that the code write one single offspring in one run. The selector must be in charge with running the program and applying the mutations, because it needs info about the program's behavior.
I feel I have explain my previous request that the mutator be separate: it would make possible to automate the verification that the children run correctly. namely: if they produce an exact copy of themselves with the mutator agent turned off and they finish running before a given number of machine cycles are spent then they will be deemed to be correct and only then will be considered for selection.
If we were using a virtual machine, I would propose to have a number of special instructions which are frowned upon by the selector if seen in the code, but which are required to be executed. These instructions do not need any particular function, as only their presence would matter - they could be glorified NOPs, NOP1 through NOPn. By demanding that all of them are executed from within the program, but also demanding that they do not show up in the code, we are basically forcing them into the encrypted part, and by their number we set a minimal size for the encrypted code too. I propose we define the presence of encryption in the program as the absence of these instruction codes together with proof that they are executed during a program run. Naturally, this will also give rise to pure generators, code snippets which write the new code without any input, but I would apply the kind of selector looking for these instructions only at the end, at which point the solutions with a proper, instruction-by-instruction decryptor would be at a relative advantage because their encrypted part would have an easier job at receiving mutations and develop all instructions than it would be the case for a pure generator.
And finally: I haven't yet accepted your challenge, so please refrain spreading that claim on other boards. We are right now trying to figure out its exact shape and rules, so there is nothing to be accepted yet. I said in the first rule-setup post things like "the temptation is big" and "let me ask some questions first", and if that does not convey tentativeness, I don't know what else would. We need to reshape the challenge to a form which is still convincing to you and practically doable by me in a reasonable part of my spare time. We might never get to that point, unfortunately. I think the questions here should have convinced you that the original layman's version "evolve a program with encryption" is so fuzzy as to be meaningless. So let us just go first through the motions one by one, clarifying rules and concepts.

This message is a reply to:
 Message 20 by Albert Godwin, posted 09-28-2006 6:03 AM Albert Godwin has not replied

Replies to this message:
 Message 39 by subbie, posted 09-30-2006 2:29 PM Barbarian has replied

  
Barbarian
Inactive Member


Message 40 of 120 (353465)
10-01-2006 2:44 PM
Reply to: Message 39 by subbie
09-30-2006 2:29 PM


I assume that you are right and as far as Albert is concerned, I am wasting my time. But he did push me over the Threshold of Laziness, and thus it came to be that I finally clarified my thoughts about a virtual machine I would use for such experiments, then proceeded to code the damn thing. I have spent most of this weekend on it, but at least I have the virtual machine, a disassembler/dumper, an assembler and a debugger ready and working (ahem ... well, it could stand some testing). The whole thing so far is about 800 lines of code (in a language called Objective Caml). I have to add a mutator, a lifecycle manager, figure out the exact details of the selectors and implement them - I think I will not overstep 2000 lines in total. Performance is also promising - I just clocked it at about 2.7 million virtual instructions per second over an ancient 800 MHz processor. The issue is that I have to stop working on it in a few hours and then I can continue it next weekend only.

This message is a reply to:
 Message 39 by subbie, posted 09-30-2006 2:29 PM subbie has not replied

  
Barbarian
Inactive Member


Message 43 of 120 (353585)
10-02-2006 9:56 AM
Reply to: Message 41 by Albert Godwin
10-01-2006 2:51 PM


Hi, Albert -
quote:
> Adding 1 to each byte? XOR-ing it to a randomly chosen segment of the ROM BASIC code byte by byte and storing the start address of the chosen segment? Full-blown DES encryption?
Well, i don't understand this but as far as i understood, perhaps you should evolve a decryptor (XOR) that decrypts the bytes that are scanned. (the bytes that the basic program searches for)
I wanted to know if by 'encryption' you mean strong encryption, that is, an encryption that is difficult to break even if you know perfectly how it was done, or something simpler, like XORing or adding some constant to every byte etc. (In fact, inverting the sequence of bytes would also be sort of an encryption, because it would already hide the sequence from the selector even if it knew how to jump over inserted or altered bytes.)
I don't feel like even attempting to implement a selector based on the strength of the encryption (I would bet that this is impossible for the general scope), but checking whether certain bytes get executed but found nowhere in the code would be simple enough proof that they were, in fact, encrypted.
quote:
> What is the function and size of the code which needs to be hidden this way? Can it be a single NOP? Must it contain all the file-writing code? And: must it be executable over the whole evolution pathway?
It needn't be the whole program, but it must include the bytes that are looked for by the selector.
I propose to have a number of special instructions which would be detected if executed by the program but which should not show up in the program code. This would prove that they were generated by the program before execution; it is a different task to select the program which does this by decryption.
There is a question about whether the decryptor code must be correctly executable in all generations. I would, just to keep it realistic, propose that it does not need to be.
quote:
> (7) a sequence of selectors may be used. I.e. we use one selector to evolve some trait, then when that is done we use another selector until the trait evolves into something else, and so on. Note that this is what happens in nature all the time: environments change. Real environment changes regardless if certain traits have already appeared, but we need to link the two because we want a certain result, we are reverse-engineering a teleological mechanism here.
You are on! Do it,as long as you provide the sources for you selectors. I will try to contact any friend who knows programming to see them.
Naturally I would, in such a case, publish the entire source code, virtual machine, selectors and all. Actually, even if I don't accept the challenge in the end, I would probably still publish the code I have written so far, as it is a nice virtual machine and a good pedagogical demo of the O'Caml language.
quote:
> (8) we should remove the error generating mechanism from the code. Most of biological evolution happens over mechanisms which seem to try very hard to produce exact copies, so mutations are essentially errors of that mechanism. I propose that mutations happen after file writing, during the copying to the new directory or whatever corresponds to that step. It should not be possible for a program to evolve the capability of not mutating at all. (In a virtual machine, replacements of bytes would also happen as random mishaps during store operations, not under the control of the code.)
Incidentally, if I posted a solution, would you be able to verify it? You said you were no assembly expert. Virtual machine?
I don't understand. please clarify.
In the original example, the code subjected to evolution is providing its own mutation mechanism. I would move this part out from the program, for the following reasons:
(a) it matches most closely what happens in nature: mutations are externally induced errors in an otherwise perfectionist mechanism, not caused (although sometimes allowed) by the multiplication processes themselves.
(b) if it stayed inside the program, it would allow the evolution of a mutation-proof program by harmlessly breaking the mutation-inducing code. No such luck for living things (actually, a bacterium whose name I can't recall comes close, by having evolved extreme mechanisms to deal with damage to DNA caused by desiccation, and incidentally becoming fairly tolerant of radioactivity and chemical mutagens as well, but this is not the norm, and it is not perfect either).
(c) I plan to use a more sophisticated memory management structure - based on small and partially isolated segments of code/data - than the simple linear bytes-in-an-address-space variety of Intel86-16bit. The types of mutations made possible over such a structure, like duplication, splitting and joining would require a sophistication from the mutation engine which would simply not fit within the size of the program we try to evolve here.
(d) I want to be able to automate the "does it work?" test, and the simplest way I could come up with was to see if the program writes an exact copy of itself in the absence of mutations. This is what, in a somewhat anthropomorphic interpretation, real genetic mechanisms appear to strive for. I said before that the program must also finish correctly, but now I am not sure that it is needed: a program should be deemed correct if it writes out at least one exact copy of itself, period. It should be immaterial if it writes multiple copies, some of them non-exact, if it writes additional garbage, or if it dies with an error or because of an instruction cycle limit overstep.
This approach takes away a possibility present in evolution, namely the capability of the organism to evolve mutagen tolerance. I have some ideas about how to do this, but won't do it in the current version of the virtual machine.
quote:
> A virtual simulation would have all the advantages we need here. It could manage the whole cycle - generate-select-verify - in a much shorter time. We could do away with dangerous things like one-byte interrupt calls which could easily damage the filesystem on your disk, or do damage to older harddisks or monitors. The particular machine code is complicated, and while that complexity is not a principial showstopper in any of the theoretical questions we try to tackle here, it could still make the effort practically unrealistic. Note that this does not mean that processes of similar character are unrealistic in nature, with more time and resources at its hands. If I understand your challenge correctly this time, I will insist on either the use of a virtual machine, or on a detailed explanation from your part about why do you think a virtual machine is a bad idea, because I don't really get it.
Ok man. YOU ARE ON ! (I guess i am quite confident that nobody will make that, no ? )Use virtual emulation, as long as you give us the code of the program that evolved finally.
Sure, if I accept the challenge: you get source code of the toolkit, the original ancestor, the final replicator and possibly the full sequence of ancestors between the first and the final one - this latter stuff depends on the memory requirements.
quote:
>Why is encryption needed? The program could contain the encrypted portion and never execute it directly, only after decryption. Having only an encrypted portion and the corresponding decryptor is just as irreducibly complex, isn't it? If the decryptor runs on a non-encrypted code portion, it will create nonsense code, and if we have a non-functional decryptor, the encrypted code is useless. I propose to do away with the encryptor part and focus on breeding a program with an encrypted part and a decryptor.
OK! I am very kind, no? but wait? if the decryptor will decrypt the code, it will be unencrypted. But it needs to be RE-ENCRYPTED before the program makes a copy of itself. Otherwise, the decryptor of the offspring will run over non encrypted bytes and garble them, no? ( I am not a programmer but i understand logic )
The encrypted code is part of the program code and it does not disappear from there just because it was decrypted, so the replication mechanism could simply copy it to the output, instead of encrypting the decrypted result again. This would be the most natural thing to do, meaning that if we started with an encrypted text + encryptor + decryptor program, it would most likely find a way to bypass encryption altogether if selection pressure was applied to e.g. the number of machine cycles used.
quote:
> I propose that the code write one single offspring in one run. The selector must be in charge with running the program and applying the mutations, because it needs info about the program's behavior.
I don't understand. please clarify
The OP example writes 676 copies of itself, which are then culled by the selector based on their looks, then the remaining ones are moved to different directories and verified to 'work', whatever that means. But we must do away with the manual part, so we need an exact, programmable way of defining what 'works' means. This is where I propose that 'work' mean that the program writes an exact copy of itself (its original code - it could rewrite its own code in memory, but we compare the result to the original code, before the first instruction is executed). It is unnecessary from this point on that the program write multiple copies, because the copies can only differ in their acquired mutations, and those mutations are applied from the outside, after the program finished running. In fact, every program could be run only once, to establish that it 'works' - all of its descendants could then be simply generated by taking its original code and applying mutations. Reproductive success will be linked to preferences of the selector by allowing the program to stay alive for more reproductive cycles if it gets a high enough rating by the selector. I am still pondering whether mutations/damages should be applied to 'adults' while running - altering surviving adults between generations would not add new selection pressures, and altering adults while running would add the selection pressure to use more mutation-safe data structures, an unnecessary goal. We don't need no unnecessary goals.
The programs I envision here cannot communicate with the outside world in any but one way: they can invoke special instructions, much like INT 21H over PC-BIOS. The selector needs to know if they were invoked - think of their invocation as interaction with the surrounding world, which is an opportunity for natural selection to rate the individuals. E.g. I plan to use 'SpecInstr 0' for 'write segment with the address found on the top of the value stack', 'SpecInstr 1' as 'close output file - this was one individual copy', 'SpecInstr 2' through 'SpecInstr ' to do nothing but register the fact of having been called in a logbook, for later consideration by the selector. The final selector requires all these SpecInstr's to be called during program execution but not to be visible in the code - so they are forced to be stored in an encrypted form.
quote:
>I feel I have explain my previous request that the mutator be separate: it would make possible to automate the verification that the children run correctly. namely: if they produce an exact copy of themselves with the mutator agent turned off and they finish running before a given number of machine cycles are spent then they will be deemed to be correct and only then will be considered for selection.
I don't totally understand this. I will tell you what i understood: You want to first give the program some free time for some generations and then start the mutations ? If that's what you want then you are ON ! ( but you'll never evolve encryption, i am sure )
As I explained above, I only need this to establish that the program 'works'. If the program creates a perfect copy of itself before or after writing other garbage, and before finishing regularly or dying, it works. This is why mutations are not immediately applied at writing out the copy, but from a functional standpoint there is no difference that I see.
quote:
> If we were using a virtual machine, I would propose to have a number of special instructions which are frowned upon by the selector if seen in the code, but which are required to be executed. These instructions do not need any particular function, as only their presence would matter - they could be glorified NOPs, NOP1 through NOPn. By demanding that all of them are executed from within the program, but also demanding that they do not show up in the code, we are basically forcing them into the encrypted part, and by their number we set a minimal size for the encrypted code too. I propose we define the presence of encryption in the program as the absence of these instruction codes together with proof that they are executed during a program run. Naturally, this will also give rise to pure generators, code snippets which write the new code without any input, but I would apply the kind of selector looking for these instructions only at the end, at which point the solutions with a proper, instruction-by-instruction decryptor would be at a relative advantage because their encrypted part would have an easier job at receiving mutations and develop all instructions than it would be the case for a pure generator.
I am not a programmer ! i don't understand !
Most of it I have explained in this post, but feel free to point me to the parts you think I haven't touched yet. One thing I know I haven't explained earlier is the pure generator stuff, so I will now explain that a bit more:
The problem is that the human definition of encryption is hard to replicate in programs. A human notion of encryption would encompass the presence of an encryptor which can take any legal encrypted text and produce the corresponding plaintext. The existence of such a subroutine in a program is easily detectable by humans in most cases, but it is impossible to write a program, a selector, which recognizes the presence of said subroutine in the general case. Discovering if some routine is decrypting some actual segment of the program might not be theoretically impossible but it is very far into the impractical side. So I proposed to prove the presence of encryption by showing that a certain number of different instructions are not present in the code but are executed during program runs. However, a program fulfilling these requirements is not yet sure to contain an encrypted text - it might contain it, but again it might just have a code segment which writes the to-be-executed code without any input at all, IOW such a program might not contain a general decryptor. I think I can circumvent this by making it a premium skill for mutations at some stage to easily impact the encrypted part, if one is present.
quote:
> And finally: I haven't yet accepted your challenge
Hehe ! Wise move. Your first sign of defeat. You are consiously writing a program and taking all privilages to make it evolve and still you are not sure that it will.
We are approaching this stuff from very different positions. The challenge is not yet entirely clear, e.g. see the discussion about encryption above. Depending on the clarifications, it could turn out to ask for the impossible or for the impractical.
quote:
And you want me to believe that YOU yourself came into existence through chance?
Well, yeah. Sort of. Make that chance operating in strict accord with uncompromising natural laws. But is the context of this challenge so far-reaching? I still try to see it as a mere exercise in trying to evolve some irreducibly complex structure.

This message is a reply to:
 Message 41 by Albert Godwin, posted 10-01-2006 2:51 PM Albert Godwin has replied

Replies to this message:
 Message 44 by Percy, posted 10-02-2006 11:05 AM Barbarian has replied
 Message 55 by Albert Godwin, posted 10-08-2006 8:26 AM Barbarian has replied
 Message 56 by Albert Godwin, posted 10-08-2006 8:36 AM Barbarian has replied

  
Barbarian
Inactive Member


Message 45 of 120 (353650)
10-02-2006 2:27 PM
Reply to: Message 44 by Percy
10-02-2006 11:05 AM


Hi, Percy -
now this is a difficult call. On one hand, the test is easy to implement, on the other hand, it seems to severely limit the avenues available for evolution, for all admissible motherlines must contain individuals able to exactly replicate themselves. However, I think that motherlines without this property will be either trivially short or trivially infinite (e.g. when a NOP is added to the beginning of a segment when copying). The latter case is impossible to detect programatically and is unlikely to lead anywhere because in addition to acquiring a useful mutation, it should also lose the harmful one causing it to grow.
I also feel that I should penalize those who do not exactly write out their copy but I have no good measure for garbage-ness of output except this equal/not-equal metric. Some programs would write out multiple files and I cannot either naturally choose one true offspring from them or declare all of them to be offsprings, first because programs would start competing in number of copies of themselves while I want serious biodiversity in a limited population, and second because I want to control the number of offspring solely on the basis of the fitness rating given by the selector. All these problems go away if I only accept programs able to exactly replicate themselves, and it also allows me to have mutations as the sole source of diversity.

This message is a reply to:
 Message 44 by Percy, posted 10-02-2006 11:05 AM Percy has replied

Replies to this message:
 Message 46 by Percy, posted 10-02-2006 3:01 PM Barbarian has replied

  
Barbarian
Inactive Member


Message 53 of 120 (354662)
10-06-2006 3:27 AM
Reply to: Message 46 by Percy
10-02-2006 3:01 PM


It may be that the result is ill-defined, but I understood it as requiring the final outcome to contain some sort of encryption and be able to replicate itself. In that case, if I don't insist on the requirement for perfect self-replication, it will be lost along the way and quite difficult to evolve it again. This is a genetic algorithm sort of setup: the ability to procreate is part of the rating algorithm - once perfect self-replication is proven, it is the environment which applies mutations and creates new instances.

This message is a reply to:
 Message 46 by Percy, posted 10-02-2006 3:01 PM Percy has not replied

  
Newer Topic | Older Topic
Jump to:


Copyright 2001-2023 by EvC Forum, All Rights Reserved

™ Version 4.2
Innovative software from Qwixotic © 2024