The Minkowski's challenge

I can't tell whether you merely playing Devil's Advocate, or not. It is; they all without exception run in virtual machines.

That is in particular demonstrably false. It is unbelievable that anyone with even moderate understanding of code or programming culture to make such a statement as 'all without exception'.There is an entire class of codes called Quines that are standalone self-replicating programs. There are even contests to create new an interesting Quines in various languages.It is also NOT illegal to simply make self-replicating programs. Your previous suggestion that it was is unfounded at the very least.

---

Of course, biblical creationists are committed to belief in God's written Word, the Bible, which forbids bearing false witness; --AIG (lest they forget)

Quines are not self-replicating. They produce their own source-code, not their own code.

In non-compiled languages, there is no distinction. Execution of the child code is one thing that COULD be included as part of the original source but just so happen to not be the case for Quines. They are also only one example of possible self-replicating code that is both not a virus, does not run on a virtual machine, and is not illegal.

---

Of course, biblical creationists are committed to belief in God's written Word, the Bible, which forbids bearing false witness; --AIG (lest they forget)

I think it's wonderful that an on-topic discussion is finally breaking out in this thread, but could we keep the discussion more topic-focused and less personal? Thanks!

---

--	Percy
	EvC Forum Director

Firstly, an interpretter is a virtual machine.Secondly, the code is not self-replicating because it requires human intervention to reproduce itself.

Unfortunatly Mr Jack an interpreter is not a virtual machine. The biggest difference being that an interpreter contains a parser and grammar definition while a virtual machine does not. A virtual machine is specifically a virtualization of a computer architecture on hardware that is not native to the architecture. Most interpreters are VASTLY more complicated than most virtual machines. That you are incorrect about this is beside the point though.Overall you are equivocating on the definition of 'code' in ways that have no meaning in response to the criticism I originally raised. It is not required that a virus be written in a machine language and the fact that the SINGULAR example I gave of self replicating code, a Quine, does not execute the produced code is a mere formality of the paradigm of a Quine. It is certainly feasable to write a Quine that includes a call to exec. Hence you next statment: is a moot point.But lets remember your original statement: In no way are all programs that self replicate, including ones that actuall execute their child code, to all be considered viruses. Beyond that it is not even true that all viruses are illegal. There are many instances of virus or worm style codes that are done for research purposes for a myriad of reasons including of course security as well as distributed updates, or distributed computing in general.Edited by Jazzns, : No reason given.

---

Of course, biblical creationists are committed to belief in God's written Word, the Bible, which forbids bearing false witness; --AIG (lest they forget)

The level of abstraction of a machine is not a consideration for this issue. Whether or not a particular machine architecture has ever been realized in actual hardware, i.e., is virtual, is irrelevant.--Percy

I think it would be really cool to do something like this in a more abstract language although I think it might be much harder. Your mutation mechanism would have to at least have knowledge of the grammar and it seems that providing good mutations would be non-trivial.In an assembly language, like I assume Barbarian is going to use, mutating an insertion for example just means I have to drop in a word of 32 random 1's and 0's weeding out the instructions that are invalid for user code.

While mutating at the symbol and grammar level and allowing the potential for illegal symbols and syntax is a possible approach, mutations at the underlying semantic level would be much more productive as far as simple evolution is concerned. But if you're studying certain other aspects of evolution, such as the evolution of error tolerance, it might prove to be a very productive approach.Barbarian will have to confirm, but my understanding of his approach is that the instruction is the unit of mutation, not the individual bits coding for machine instructions. I don't think his abstract machine includes the concept of bit-encoded machine-level instructions, but I'm sure he'll let us know.--Percy

Yes I also assumed the instruction is the unit of mutation. An insertion like I described above would be the whole 'word'. The word itself would be a random one. The only thing you MIGHT want to do at that point is filter out any words that are not valid instruction. In Barbarian's case though he might leave it if it is in his 'encrypted' section of the program.Deleting would be the removal of a word.A point mutation though may be a single bit change in a single word. I imagine the real world being a 2 bit version of what Barbarian is trying to do with A,C,T,G capable of being represented by 0,1,10,11.What might make Barbarian's job a little harder is there are many more viable instructions than that depending on the virtual architecture he is working on. Point mutation may be the equivalent of a deleting and insertion at the same location.The more I think about this the more I think that Barbarian's job may be harder than I originally though. The different selectors are the key and it may take some art to get things to come out how he wants.It seems like the first selection pressure should be the functionality of reading the encrypted code. This could be a one word read.Then the selection pressure might be to alter the word that had been read. The problem I see with this is that this selection pressure may need to have knowledge about how the fitness under the first selection pressure was obtained. The pressure here is, 'alter the thing you just read'. But information needed by this second selection pressure may be the location of the data.I suppose you could alter the first selection pressure to read the encrypted data into a known place but it looks like this might get very hairy with respect to the sequence and details of the selection pressure. My worry is that they would get to be too guiding. If the selection pressure start to get so detailed that they are at the point of specificing a particular instruction, then I don't know if that means anything with respect to evolution since the range of fitness would be very narrow.

---

Of course, biblical creationists are committed to belief in God's written Word, the Bible, which forbids bearing false witness; --AIG (lest they forget)

quote:

---

Barbarian will have to confirm, but my understanding of his approach is that the instruction is the unit of mutation, not the individual bits coding for machine instructions. I don't think his abstract machine includes the concept of bit-encoded machine-level instruction

---

That's correct: one unit of mutation is the instruction, another one is the segment.In fact, I have a very basic draft specification of the language and the mutation mechanisms, which I feel to be on-topic enough to post here:Programs are non-empty sequences of segments; segments are non-empty sequences of instructions.A program is executed starting with the first segment and executing instructions in order - potentially resulting in control transfer to other segments - until either an error condition occurs or execution runs off the end of a segment. Execution does not fall over to the next or any other segment - it has to be explicitly transferred by a JUMP, CALL etc. instruction.The context of a program consists of a value stack and a return stack. The value stack can contain any instruction; the return stack can contain addresses only. Both stacks start out empty.Instructions fall into the following categories: literal integers, literal addresses and simple instructions. Simple instructions are further subdivided into special instructions (see below) and regular instructions (all the rest).Literal integer values (0 to 7, but this is a compile-time option and can go all the way to include all integers representable on 63 bits) and simple instructions form the class of values. Repeated incrementing starting from literal zero will pass through all integers, then all simple instructions (first regular, then special ones), then loop back to zero, IOW it loops through all values in a certain order; semantics of addition and negation are derived to be consistent with this behavior. The length of this cycle has a fundamental role in the structure of programs, and it is called FIRST_INVALID (as it is the first invalid numeric value if we start enumerating them from zero). The cycle also establishes an one-to-one correspondence between values and corresponding numeric values (nonnegative integer numbers up to FIRST_INVALID - 1).Technically, addresses are pairs of segment identifiers and offsets, although they are somewhat smarter than that - more about this in the mutation part. Addresses can by construction only point into valid, existing segments, but they can point to invalid (i.e. too high) offsets within those segments. Offsets start with zero for the first instruction in the segment, and extend all the way up to (but not including) FIRST_INVALID. Thus, any value can be used as offset (via its numeric value). Conversely, the numeric value of an address is the numeric value of its segment.Incrementing an address increments its offset modulo FIRST_INVALID, negating it amounts to negating its offset modulo FIRST_INVALID; both instructions yield addresses with a new offset and the original segment. If an address is the top/second operand of an AND or XOR operation, it behaves as if it was a value corresponding to its offset (the segment gets discarded). If an address is the bottom/first operand of these operations, its offset is used in carrying out the computation and then the result is constructed to be an address with the original segment of the first operand and the result of the computation for offset.Equality means complete equality, in the case of addresses the segments and offsets must be pairwise equal, and no address can be equal to any value. As for ordering, values are ordered by their numeric value and are smaller than any address; addresses are ordered by the order of their segments, then by their offsets.I list the instructions below. Unless otherwise noted, 'expects on stack' or 'continues at address' mean that the program exits with an error condition if the expectation is not met or the address is invalid. Expected stack context is enumerated starting from the top of the stack which is imagined to grow upwards; 'expects an address and two values on the value stack' means that the address is the topmost, last pushed element on the stack.

​

The list of instructions is the following:

​

Literal integer (written # N e.g. #5) - pushes itself (i.e. the integer) onto the value stack.

​

literal address (written *LABEL eg *LOOP1 or * <2:4> for segment=2 and offset=4) - pushes itself (i.e. the address) onto the value stack. It does not matter whether the address is valid or invalid.

​

NOP - does exactly nothing

​

NOTEMPTY - expects an address on top of the value stack; if the stack beneath the address is empty, jumps to the point denoted by the address, else removes the address from the top of the value stack and continues to the next instruction

​

ADD - expects two instructions on the top of the value stack, removes them and pushes their sum on the value stack.

​

INCR - expects an instruction on the top of the value stack, increments it according to the rules above

​

NEG - expects an instruction on the top of the value stack, negates it as described above

​

XOR - expects two instructions in the value stack, combines them as described above

​

NEWSEG - expects an instruction on top of the value stack; removes it and adds a new segment containing the instruction as the only element to the program; pushes the address of its first (and only) element onto the value stack

​

OFFSET - expects an arbitrary instruction and an address on the value stack; replaces them with the address built by taking the segment from the first/lower operand and the numeric value/offset of the second/top operand for offset.

​

NEXTSEG - expects an address on top of the value stack, replaces it with the address of the beginning of the next segment if any, or with an integer 0 if there is no segment after the one pointed to by the top one.

​

LOAD - expects an address on top of the value stack, replaces it with the instruction to which it points

​

PUSH - expects an address and a value on the value stack, removes them and prepends the value to the segment pointed into by the address (offset gets ignored)

​

ESC - does nothing, but the immediately next instruction is pushed onto the value stack instead of being executed. This is the only way to explicitly push simple instructions on the stack.

​

DROP - expects the value stack to hold at least one instruction; discards the topmost element.

​

DUP - expects an instruction with numeric value N on the top of the value stack; replaces it with the element at depth N in the value stack (N=0 corresponds to the topmost element)

​

SWAP - expects the value stack to contain at least two elements; swaps the topmost two elements

​

LIFT - expects an instruction with numeric value N on the top of the value stack; drops it, removes the element at depth N and puts it onto the top of the value stack.

​

JUMP - expects an address on the top of the value stack; removes it and continues with the instruction pointed to by said address

​

CALL - expects an address on top of the value stack; removes it and continues with the first instruction in the segment pointed to by said address (the offset is disregarded!) but before doing so pushes the address of the instruction after the CALL onto the return stack

​

RET - expects the return stack not to be empty; removes the topmost address and continues execution with the instruction pointed to by it

​

STOP - changes the execution mode such that all subsequent instructions except START will count as NOPs. In particular, more STOPs do not open nested levels. Falling off the end of the segment counts for regular termination

​

START - restores normal execution mode. If the machine was not operating under the effect of a previous STOP, START acts as a NOP.

​

IFEQUAL - expects an address and two instructions on the value stack; removes them; if the instructions are exactly equal, continue at the address, else with the next instruction

​

IFLESS - expects an address and two instructions on the value stack; removes them; if the first/deepest value is less than the second/middle one, it continues at the specified address, else with the next instruction.

​

INVALIDADDR - expects an address and an instruction on top of the value stack; removes them; if the instruction is not a valid address, it continues at the given (top) address, else with the next instruction

​

Special instructions, written SPECINSTR N e.g. SPECINSTR 2 - act as NOPs as far as the machine is concerned, with the exception that they can raise error conditions. These are the instructions whose execution can convey information to the environment. I am undecided about their required number. I am sure I will use SPECINSTR 0 to expect an address on the value stack and - leaving it there - I will use this as a request to write out the segment pointed to by the address; I will also use SPECINSTR 1 to signal the end of a set of written segments. A sequence of SPECINSTR 0's followed by a single SPECINSTR 1 is akin to writing and closing a file - this can be repeated then with new values. Other SPECINSTR's simply register the fact of them having been executed.

​

Mutations can affect instructions or structure/segments. First, it is decided whether a mutation must take place or not. If the answer is yes, we decide whether it be an instruction-level or a structure mutation.

​

Instructions can be deleted, inserted or replaced. *EDITED* Insertion is not always possible, but the other two are; the type of mutation is chosen from an uniform distribution of possible mutation types.

​

Deletion does not care about what instruction it deletes, but readjusts all addresses pointing into the segment of the deleted instruction and to a point higher than the deletion occurred. If the segment had only one instruction, then the whole segment is deleted, see below.

​

Insertions are possible before the first, after the last or between any two instructions, provided that the resulting segment is not longer than FIRST_INVALID. Addresses will be adjusted accordingly. The environment first decides whether to insert an address or a regular instruction. If it is an address, the segment is chosen in an uniformly random way, while the offset will be chosen from a truncated geometric distribution. If it is a regular instruction, it is chosen in an uniformly random way.

​

Replacements are sensitive to what they change. The three classes are addresses, integers and the rest. There is a small chance of changing the class; if it happens, the new value is chosen uniformly from the available values in the new class, except for address offsets which are chosen from a truncated geometric distribution. If there is no change of class, integers turn into a strictly different integer, chosen from an uniform distribution; instructions turn into a strictly different instruction, chosen from an uniform distribution; addresses change either their segments or their offset or both; if the segment is changed, it is chosen from an uniform distribution of all valid segments; if the offset is changed, it is chosen from a truncated geometric distribution but must differ from the previous one if the segment did not change.

​

Stucture/segments can be mutated in four ways: duplication, deletion, fusing and splitting. Duplication is always possible, the other three may sometimes be impossible. The actual mutation type is chosen from a uniform distribution of possible types.

​

A duplicated segment is placed at the end of the program. No adjustments of addresses will take place. All segments have equal probabilities of being duplicated.

​

Deletion is accompanied by adjusting all addresses pointing to other segments, and replacing all addresses pointing into the deleted segment by literal integer 0's. All segments have equal probabilities of being deleted.

​

Fusing is done by removing one segment and concatenating it to another one (the base segment). This is only possible if the length of the new segment is not greater than FIRST_INVALID. Addresses pointing into the removed segment are adjusted accordingly. The last RET or JUMP instruction in the base segment is replaced with a NOP or a DROP, respectively. All joinable segment pairs have the same probability of being chosen for fusing.

​

Splitting is only possible between two instructions (you can't split off the empty end or beginning of a segment, splitting before the first or after the last instruction). The split-off part is added to the end of the program, after other segments, and addresses are adjusted accordingly. All splitting points have the same probability of being the site of a split.
[ETA!] The literal address of the start of the new, split-off segment and a JUMP are added to the end of the truncated segment part. Accordingly, segments having maximal length (FIRST_INVALID) cannot be split between the last two instructions.

​

Edited by Barbarian, : Reason for edit: forgot to copy the last two sentences into the text box...

​

Edited by Barbarian, : Display of smilies interferes with syntax of literal address

​

Edited by Barbarian, : Of course, deletion of an instruction is always possible, what I had in mind was insertion ...

Facinating. I love the simplicity. Picking a stack machine makes sense.Did you design this architecture?Are you going to put in an instruction execution limit to avoid infinite looping?

---

Of course, biblical creationists are committed to belief in God's written Word, the Bible, which forbids bearing false witness; --AIG (lest they forget)

quote:

---

Did you design this architecture?

---

Yes. It is an extreme deviation from another one I designed to serve as an intermediate language in a compiler infrastructure I was (and still am) trying to put together. As you can tell, I have really weird hobbies.

quote:

---

Are you going to put in an instruction execution limit to avoid infinite looping?

---

Yes again. The language is Turing-complete (*), so the halting problem is not generally solvable for programs written in it. I toyed with the idea of proposing a non-Turing-complete language, but decided against it. Instruction count limitation is much simpler.(*): well, theoretically. Practically the limit embodied by FIRST_INVALID makes it non-Turing-complete, but by that standard few other languages are complete. Assuming an infinite value for FIRST_INVALID, I am pretty sure Turing completeness would be tedious but straightforward to prove, and I am also sure that the potential infiniteness of segment count is not rescuing me from Turing-incompleteness in the presence of a finite FIRST_INVALID.Edited by Barbarian, : Added further musings about Turing-completeness

Some more details, this time mostly about code I haven't written yet (but it should not be an issue - the biggest challenge I see now is saving and reloading the state):Populations are size-limited collections of genotypes, organized by their fitness function. Genotypes with identical fitness values are grouped into fitness classes. After additions (including mergings of two populations) the population is always cut back to the size limit.Procreation means the building of a second collection of individuals, by giving every genotype in the source population as many chances as indicated by its fitness value to procreate. Procreation means the creation of a copy with at least one mutation (due to the fact that the parent population is not discarded but merged with the new one, there is no need to bother with non-mutated offspring), computing its fitness value and adding it to the child population (several optimizations are planned here, e.g. offspring with a fitness value lower than the current low in the parent population are not added but discarded). I think for now I can do with exactly one mutation per offspring, but I am not excluding the possibility of drawing the number of mutations from a geometric distribution.After the child collection is completed, it is merged with the parent population and trimmed to size (low fitness values get eliminated). The last fitness class, potentially straddling the population size limit, is randomly culled to fit.I plan to use a chain of selectors, connected as follows: every selector has its own associated population. Initially, only the first selector in the chain has a non-empty population. A new generation is produced as follows: first, the first population undergoes a procreation step as discussed above. The next population undergoes the same, except its offspring population gets initialized with the collection of offspring admitted into the first population. This is repeated all the way to the last population, where I will be waiting, watching the fitness of top performers and running the experiment until I see a spike in said fitness.Right now I score almost 3 million instructions executed per second (on a 800MHz Athlon), while the mutation engine can build new individual programs worth about 4.5 million instructions per second. These numbers combine to an estimated procreation speed of creating programs worth 1.5 million instructions per second. Making my own work easy, I assume the average size of a program is 30 instructions, and come to the estimate of about 50,000 individual procreation events per second. I don't think this can be significantly enhanced - I can imagine a fivefold or sixfold speedup from complete rewriting in C or assembler, but the required amount of work and maintenance (and for the assembler solution, portability issues) mean that the speedup is simply not worth it.I thought I would implement sort of a predictor mechanism, which would look like the above except two changes (1) it would not enforce the population size limit if there was only one fitness class in it and (2) it would create an offspring with every conceivable single mutation. Optimization demands that in subsequent generations, whoever had a chance of procreation should not be given such a chance again. With a smaller population, this method would in fact try to find the most likely direction of evolution. It is, unfortunately, easily defeated by the appearance of a population consisting of one single but huge fitness class - the population size is unlimited in this case. I am just playing with this idea now.The structure of the programs would make mating / horizontal gene exchange simulation pretty easy, but in order to stay within the valid-analogy radius of the original challenge, I'll go with asexual division / parthenogenesis / whatever it is called.I planned to write a bit about the selector sequences, but I won't have the time to do both coding and writing. Basically, the most promising idea is to evolve programs which write two copies of themselves, then alter the code in a way to cause one of the copies to contain freak decryption of a minimal part of the code (thereby making this copy an invalid one) and execute it (crashing the program) after the valid copy was written out, then wait until the program acquires another mutation which suddenly turns the henceforth invalid copy into a valid one (and the so far valid copy into an invalid one), then forcing all SPECINSTRs to reside in the decrypted code only. This is just one of the ideas; I have a number of other lines to try.