Uncommon Descent Serving The Intelligent Design Community

Avida’s EQU in 18 instructions

Winston Ewert
May 5, 2014
Engineering
Share
Facebook
Twitter
LinkedIn
Flipboard
Print
Email

The evolutionary model, Avida, is best known for evolving the EQU function. In the supplementary materials for the 2003 Nature paper, the authors presented the shortest known program to compute EQU taking 19 instructions. They note that it hasn’t been proven that it was the shortest program. In fact it is not, and I present a program that computes EQU only using 18 instructions.

  1. IO
  2. IO
  3. nop-C
  4. push
  5. pop
  6. nop-A
  7. nand
  8. push
  9. nand
  10. swap
  11. nop-C
  12. swap
  13. nand
  14. nand
  15. pop
  16. nop-C
  17. nand
  18. IO

 

Comments
I think this 17 instruction version will work. I've run it by hand, but haven't tested it in Avida. It's basically the same as Winston's but uses the stack differently to reduce the number of nops (register references). 1. IO 2. IO 3. nop-c 4. push 5. nand 6. push 7. nand 8. swap 9. pop 10. nop-a 11. pop 12. nand 13. nand 14. swap 15. nop-c 16. nand 17. IO Roy P.S. Avida programs would be so much easier to understand if the language designer had specified the nops as being before the instruction they affect.Roy
May 5, 2014
May
05
May
5
05
2014
09:35 AM
9
09
35
AM
PDT
Winston, you're right, it does work - I was misinterpreting the swap instructions. Congratulations. I wonder if it can be made shorter still? RoyRoy
May 5, 2014
May
05
May
5
05
2014
08:35 AM
8
08
35
AM
PDT
Karaite - The goal of Avida was to demonstrate experimentally that Irreducible Complexity is false. Therefore, the goal is to show that a complex algorithm can evolve by mutation and natural selection. The authors of Avida were able to evolve a function that they believe to be complex, the EQU function. Unfortunately, the Avida team didn't really have a very good definition of "complex". In addition, they inserted design into the environment by creating a step-by-step pathway to the EQU function. That is, the researchers knew each part that needed to be in EQU, so they made sure that every step on the way to EQU would remain selectable. This would seem to disqualify it from Irreducible Complexity to begin with.johnnyb
May 5, 2014
May
05
May
5
05
2014
07:23 AM
7
07
23
AM
PDT
Hello, I am a total ignoramus when it comes to informatics. Winston Ewert, I have read your article on ENV on this subject. I must say I still don't understand what Avida has accomplished. Can you, or someone else here, dumb it down a bit for me? Thanks.The Karaite Heretic
May 5, 2014
May
05
May
5
05
2014
06:00 AM
6
06
00
AM
PDT
Roy, Instructions 4, 5, 6 have the result of copying register BX to register AX. 4 pushes a copy of register BX onto the stock, the 5 pops it, but because 6 is nop-A it gets popped onto register AX. So the instructions are needed, and it does appear to me to work correctly for the case you mention.Winston Ewert
May 5, 2014
May
05
May
5
05
2014
04:38 AM
4
04
38
AM
PDT
Winston, AFAICT instructions 4/5/6 don't do anything so can be dropped, leaving a 15-instruction algorithm. But AFAICT neither algorithm works. If the first input is "1" and the second input is "0", the final output is "1" when it should be "0". AFAICT the algorithms work for the other three possible input combinations, so maybe the test input contained only those. RoyRoy
May 5, 2014
May
05
May
5
05
2014
03:39 AM
3
03
39
AM
PDT
1 2

Leave a Reply