Understanding through Discussion


Welcome! You are not logged in. [ Login ]
EvC Forum active members: 68 (9101 total)
3 online now:
Newest Member: sensei
Post Volume: Total: 904,467 Year: 1,348/14,231 Month: 272/1,076 Week: 5/376 Day: 5/78 Hour: 1/0


Thread  Details

Email This Thread
Newer Topic | Older Topic
  
Author Topic:   The Minkowski's challenge
Dr Jack
Member
Posts: 3507
From: Leicester, England
Joined: 07-14-2003


Message 31 of 120 (353048)
09-29-2006 5:45 AM
Reply to: Message 20 by Albert Godwin
09-28-2006 6:03 AM


Nthe challenge is to evolve encryption. and do it in real programming, no virual simulations and no formal proofs. i want a practical responce.
Do you have any idea how radically irresponsible that would be?
Computer programs that self-replicate already exist, going under the name Computer Viruses - writing them is illegal.

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 75 by Jazzns, posted 10-17-2006 11:39 AM Dr Jack has replied

  
Percy
Member
Posts: 21346
From: New Hampshire
Joined: 12-23-2000
Member Rating: 2.4


Message 32 of 120 (353058)
09-29-2006 7:42 AM


Examining Avida
I've resisted investigating any ALife systems in detail because I was much more interested in developing my own system, but faced with the practical impossibility of this at present I've broken down and started reading the Avida documentation.
My first impression after 5 minutes: what an incredibly arcane virtual instruction set! What an incredibly obtuse virtual CPU! I assume that as I read on I'll come to see that this derives from necessity, but the initial impression is of general bewilderment. I've programmed in PDP-8 assembler and PDP-11 assembler, and I have read-only familiarity with PDP-10 assembler and VAX assembler, and I've examined Sparc assembler and Intel x86 assembler. I'm familiar with the general architecture of the associated CPUs. But I've never seen anything even vaguely like this Avida instruction set and architecture, though perhaps PDP-10 byte pointers come close in some respects. But I've little experience with virtual machines, maybe they are conceptually more "freeing". Maybe Avida makes sense as a virtual machine. I'll reserve judgment for now.
Still, get a load of some of these instructions:
(d) if-n-equ Execute next instruction only-if ?BX? does not equal its complement
Say what??? Okay, let's not panic, let's try to figure this out.
?BX? is register BX. The question marks are an indicator that a NOP immediately following the instruction can alter the register to be AX, BX or CX, depending upon whether the NOP is NOPA, NOPB or NOPC (not much of a NOP if it actually has an effect).
So the next instruction is executed if register BX is not equal to its complement? When is anything ever equal to its complement (which is where all 0 bits become 1 and all 1 bits become 0)? Never, that's when! So what the heck do they mean by complement?
Reading on, it turns out that "complement" has a special (and stupid (I have a feeling I'll be using this word alot)) meaning in Avida. A register's complement is the next in the sequence. There are three registers AX, BX and CX in that order, wrapping at the end. The complement of BX is CX. So the if-n-equ instruction executes the next instruction if BX doesn't equal CX.
Avida also defines something called a "template complement." A template is a sequence of registers, e.g., ABAAC. The complement of this template is the next register in the sequence for each register, BCBBA. A template is defined by a sequence of NOP instructions, so the ABAAC sequence would be defined by this sequence of NOP instructions:
NOPA
NOPB
NOPA
NOPA
NOPC
Why do they feel the need for this?
Reading The Instruction Set File documentation I see that the unit of mutation is the instruction. Each instruction has these attributes:
Redundancy: the frequency of the instruction. It controls the likelikhood of being mutated to.
cost: number of CPU cycles to execute
ft cost: addition cost the first time an instruction of this type is executed.
prob fail: the probability that the instruction doesn't work, in which case it is a NOP for that cycle.
Omigod, reading on I just realized the reason for the template complement, and it's incredibly arcane. They use it as a labeling system. This is unbelievable, let me explain.
They can search through the program for a given template using the h-search instruction. The h-search instruction is followed by a template, and it searches through the program looking for the complement of the template. For example, this h-search instruction searches through the program looking for the template AB:
h-search
NOPC
NOPA
Why does h-search look for the complement of the template instead of the template? Because otherwise it would find itself!!!
All they really needed was a labeling system. All the macro assembly languages have them. I can see that because instructions can mutate, and because labels in the program are made up of instructions, that the labels can mutate, but there are more straightforward ways to accomplish the same thing. I can see the problem they're attempting to address. A single mutation to the label ABC might cause it to become ABB, but if your label is permitted to consist of all 26 letters then the odds of neutral and negative mutations might become prohibitively high.
I believe they were driven in this direction because of their desire to make the copying code (the reproductive code) part of the program. I can see the desireability of this, even the necessity, but I think there are far better approaches than this. I'm sure that once you've lived with Avida virtual code for a while that it all begins to make intuitive sense, but I would want something more accessible that anyone already familiar with assembly code could grasp intuitively after just a few minutes.
I couldn't find prebuilt Avida executables for Windows on line, and I don't have the tools for building C++ programs on my system. I could do it on a Unix or Linux machine, but now this is beginning to seem like it requires too much time, given that my workday must begin soon. So that's all I have to say about Avida.
--Percy

Replies to this message:
 Message 33 by Barbarian, posted 09-29-2006 8:06 AM Percy has 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

  
Percy
Member
Posts: 21346
From: New Hampshire
Joined: 12-23-2000
Member Rating: 2.4


Message 34 of 120 (353066)
09-29-2006 8:17 AM
Reply to: Message 33 by Barbarian
09-29-2006 8:06 AM


Re: Examining Avida
I had already downloaded that. I didn't notice any Windows binaries.
--Percy

This message is a reply to:
 Message 33 by Barbarian, posted 09-29-2006 8:06 AM Barbarian has replied

Replies to this message:
 Message 35 by Barbarian, posted 09-29-2006 8:36 AM Percy 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

  
Percy
Member
Posts: 21346
From: New Hampshire
Joined: 12-23-2000
Member Rating: 2.4


Message 36 of 120 (353080)
09-29-2006 9:07 AM
Reply to: Message 35 by Barbarian
09-29-2006 8:36 AM


Re: Examining Avida
Oh, I see where I went wrong. I had clicked on the "Current Release" link that appears in the list of links for Avida site navigation. This took me to a page that sent me to SourceForge which has the 2.6 release, but sources only.
I now see the Windows Binary link in the Current Release box on the home page. It's for version 2.0, but that should be fine for giving it a try. Both viewers seem to work for me. I started with qt-viewer, it's running the default simulation now. Thanks for the help!
--Percy

This message is a reply to:
 Message 35 by Barbarian, posted 09-29-2006 8:36 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

  
RickJB
Member (Idle past 4483 days)
Posts: 917
From: London, UK
Joined: 04-14-2006


Message 38 of 120 (353285)
09-30-2006 2:23 PM


Barbarian and Percy,
Some great posts here guys.
I think will struggle to follow your arguments (as a humble former script coder - javascript, actionscript, etc) but they are interesting nonetheless!

  
subbie
Member (Idle past 747 days)
Posts: 3509
Joined: 02-26-2006


Message 39 of 120 (353287)
09-30-2006 2:29 PM
Reply to: Message 37 by Barbarian
09-29-2006 9:49 AM


Barbarian, I fear you are wasting your time. By insisting on pinning down specifics before beginning, you may scare poor Albert away. Too many details agreed upon will make it more difficult for him to move the goalposts.
But good luck to you none the less.

Those who would sacrifice an essential liberty for a temporary security will lose both, and deserve neither. -- Benjamin Franklin

This message is a reply to:
 Message 37 by Barbarian, posted 09-29-2006 9:49 AM Barbarian has replied

Replies to this message:
 Message 40 by Barbarian, posted 10-01-2006 2:44 PM subbie has not 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

  
Albert Godwin
Inactive Member


Message 41 of 120 (353466)
10-01-2006 2:51 PM


Dear Barbarian,
Sorry for being late. I don't understand programming and i thought that it wouldn't be wise to contact Fady Bahig, seeing his last update in his blog:
lulu.com/fadybahig
> 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)
> 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.
> (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.
> (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.
> 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.
> 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.
Things that are not present now. because you will write your own selector.
I'll add the reply to the other post within moments.

Replies to this message:
 Message 43 by Barbarian, posted 10-02-2006 9:56 AM Albert Godwin has replied

  
Albert Godwin
Inactive Member


Message 42 of 120 (353473)
10-01-2006 3:12 PM


>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 )
> 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
>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 )
> 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 !
> 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. And you want me to believe that YOU yourself came into existence through chance? Your brilliant programming brain is a witness to the greatness of our beloved lord.
> (as a humble former script coder - javascript, actionscript, etc)
Oh, Nice Ricky. You like scripts? I am not a programmer, but as far as i know, those things are quite shameful to be said..
You like to write scripts baby? LOL

  
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

  
Percy
Member
Posts: 21346
From: New Hampshire
Joined: 12-23-2000
Member Rating: 2.4


Message 44 of 120 (353604)
10-02-2006 11:05 AM
Reply to: Message 43 by Barbarian
10-02-2006 9:56 AM


Hi Barbarian,
I think you may be creating extra and unnecessary work for yourself by including an explicit "does it work" test. The determination of whether it works or not is made by the outcome of the evolutionary process. If the organism survives to reproduce as do its offspring for generation after generation, then it works. If its line of descendents eventually dies out, then it doesn't work.
--Percy

This message is a reply to:
 Message 43 by Barbarian, posted 10-02-2006 9:56 AM Barbarian has replied

Replies to this message:
 Message 45 by Barbarian, posted 10-02-2006 2:27 PM Percy 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

  
Newer Topic | Older Topic
Jump to:


Copyright 2001-2022 by EvC Forum, All Rights Reserved

™ Version 4.1
Innovative software from Qwixotic © 2023