complexity 1: some thoughts on life
May. 29th, 2011 04:23 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
stormsewerSo, I've been thinking about life lately. Not in the who-am-I-why-am-I-here sense, but in the what-is-the-difference-between-alive-and-not-alive sense. Now I'm certain that my cogitations are pretty infantile compared to those of certain others, but I'd like to tell you some of what I've been thinking.
Like pornography, life is one of those things that we know when we see it, but actually defining it is difficult. Actually, I'm not even sure we do know it when we see it. For instance, is a virus alive? It doesn't eat or carry out metabolism, and it does not contain complete instructions for replicating itself- it has to piggy-back on the complete instructions maintained by something else, using the materials that "something else" builds as a result of eating things. On the other hand, it does reproduce itself very well, it does maintain an environment separate from the outside, it does make responses to stimuli, and it does evolve and adapt. Some people would waffle on the question and say it is alive when it is interacting with a cell but otherwise not alive. Personally, I prefer to think of them as straight-up alive. Even if they cheat a little.
Self-Replicating Programs
One of the questions that invariably comes up when you head down this rabbit hole is, Can a machine or a computer program be alive? Most people prefer to think not, but why? This had been in the back of my mind lately as I began to read Complexity: A Guided Tour by Melanie Mitchell.1 Today I was reading Chapter 8, where she mentions that one objection people may give about why a program or machine cannot be alive is that it cannot replicate itself. Of course with the advent of computer viruses and worms, everyone now knows that programs can replicate themselves, and there are even some simple machines that can replicate themselves now. When she mentioned the idea of a simple self-replicating program, I immediately stopped reading the book and set about writing one, which was successful. Only later did I read her statement of the original conundrum people had about doing this, which I will restate as an English-language program:
"This is a self-replicating program, so type 'T' 'h' 'i' 's' ' ' 'i' 's'..." going onward until you get to "''' 'T' ''' ' ' 'h'..." as you begin to type instructions for typing instructions, and then...
Did you ever as a kid start thinking about thinking, and then realize you were thinking about thinking about thinking, and that therefore you were thinking about thinking about thinking about thinking, and thus... Let's just stop there. This seems to be a logical room of mirrors from which there is no escape. And yet clearly there is a way to write a self-replicating program without waiting literally forever.
My Self-Replicating Program
My solution, translated into English, was this:
"This is a self-replicating program written in a file named reproducer0. Its replicator number is zero. First, read everything between the quotation marks here into your working memory as a temporary copy. The new replicator number is the old replicator number plus one. Now, in this temporary copy, go back to the first sentence and change the number following reproducer to the new replicator number. Do the same for the number mentioned in the second sentence. Now write the modified program to a file that has the same name as the last word in the first sentence of the modified program."2
Okay, so I'm a genius for figuring out the answer to one of the foundational problems in computer science in a few minutes, right? But wait, can you explain what it is that the first program does wrong, and what it is that the second program does right to avoid the first's fate? That rather stumped me once I read Mitchell's statement of the problem after coming up with my answer, and I had to read on and have her explain it to me.
Requirements for Self-Replicating Programs
Here's my version of that explanation. In the first example, no part of the program is ever both subject and object of computation at the same time. In other words, none of the instructions are truly self-referential. My solution, which I'm sure I only came up with because such things are taken for granted by people remotely computer literate in this day and age, does contain self-referential instructions (specifically, "read everything between the quotation marks here into your working memory as a temporary copy"). A more simple way to state the solution is, "This is a self-replicating program, so copy out this sentence in its entirety." It's as if infinity must be turned directly back on itself in order to be defeated.
Mitchell points out the interesting fact that biological replicators function in the same way. DNA encodes DNA polymerases, which then go and make copies of the DNA that encoded them. Biological systems go even further, though, in that they also encode the system that translates the DNA polymerases from the DNA code. My program, like most programs, does NOT encode the means for translating its instructions into output- that role is filled by my Python interpreter. (Though apparently Von Neumann did write a program that encoded its own interpreter in his original solution to this problem, which was written out mathematically, not in a programming language.)
(The question of how all this relates to statements like "This statement cannot be proven to be true," and whether or not all mathematically true relationships can be proven to be true in finite time is left as an exercise for the reader. :) )
Life in Biological Versus Computer Viruses
And, coming back around to my original topic, viruses also do not encode their own interpreter (in compu-talk) or translation apparatus (in biospeak)- they use their host cell for that. So grant me for a moment that influenza virus is "alive." Why then is a computer virus not alive? That's a hard question.
I think it's because computer viruses cannot evolve and adapt without someone manually modifying them. Influenza can. It's interesting to compare the "programming code" of viruses (and all other life) to those used in man-made computers. The DNA code is actually quite tolerant of changes. While most mutations do make things worse, most mutations also fail to totally crash the system, which gives you breathing room to do a random walk through search space looking for the mutations that help you out. DNA replication is unavoidably inaccurate to some degree- it's the nature of the random and transient electrostatic interactions that the whole thing is based on, such that every once in a while a mistake will be glommed onto long enough to get stuck into the final product- and many viruses actually have very low fidelity in copying their DNA, which seems to allow them to modify their code (evolve) even faster.
On the other hand, try going through the code of a computer virus and randomly changing letters to other letters. Or even going down to the binary and randomly changing ones to zeroes or vice versa. How long is that virus going to keep functioning once you start doing that? What are the chances you'll make a virus that's even better by doing this? Not long, and zero.
An Evolvable Programming Language?
So perhaps what would be needed for a program to really come alive is a computer programming language that is tolerant to random changes (including not just changing symbols, but also deleting, repeating, and moving symbols or groups of symbols, and maybe even random insertion of code from outside) and a copying method that introduces random changes into programs written in that language. What would would such a programming language look like? What would happen if a computer virus was written in it, complete with its own faulty replicator?
I guess that's another exercise for the reader.
Notes
1On Melanie Mitchell's book on complexity. I've really been enjoying this book so far. It covers the basics of all kinds of things I always I thought I would be interested in if I could get a reasonable explanation of them (for example, chaos theory, fractal geometry, Turing machines) as well as things I definitely know I am interested in and have spent a fair amount of time studying (genetics, evolution, thermodynamics, stock markets...). The book has made me realize a common thread between many of my passions, which is that I am fascinated by complex systems, in general. (Where my personal over-simplified definition of a complex system is "hard-to-predict large-scale patterns resulting from small-scale actors following simple rules.") If I had encountered a book like this in high school, my life might have taken a different turn. If you're interested in these kinds of things, I would definitely recommend the book, as it explains things gently and clearly. Gödel, Escher, Bach, another book that I've been meaning to read and that was written by Mitchell's PhD advisor, seems like a good potential companion book.
2The actual Python program is below. The name of the progenitor program is "reproducer_0.py". (Keep in mind I've no formal training in programming, and this can be considered as part of the ongoing process of teaching myself Computer Science 101.)
reproducer_number = 0
#reproducer ver 1.0
#when reproducer_(n).py is run, it makes a new file called reproducer_(n+1)
#that is identical to reproducer_(n)
#(n) is given to be the reproducer_number at the start of the file
repn = open("reproducer_%d.py" % reproducer_number)
repn_read = repn.readlines()
repn.close()
new_reproducer_number = reproducer_number + 1
repn_read[0] = "reproducer_number = %d\n" % new_reproducer_number
repnplus1 = open("reproducer_%d.py" % new_reproducer_number, "w")
for line in repn_read:
repnplus1.write(line)
repnplus1.close()
I spent much of the day making more complicated versions of this. For instance, if you run replicator_0 above, you get replicator_1. If you run replicator_0 again, it just overwrites the replicator_1 it already made; if you want replicator_2, you have to run replicator_1. So I made a version that checks out all the other replicators in the same folder, figures out the maximum replicator number present, and names the new replicator as the next number after that maximum. So you can just run replicator_0 over and over again to get more and more copies.
Then I made versions that keep track of their own geneaology, all the way back to replicator_0. One version just tracks its lineage within its code (as a "genotype," to use biotalk), and another version also displays its lineage in the filename (as a "phenotype"). It is alarmingly tempting to write versions that replicate without having to be told, or randomly insert the new copies of themselves into other folders on my hard drive, or thumb drive...
Like pornography, life is one of those things that we know when we see it, but actually defining it is difficult. Actually, I'm not even sure we do know it when we see it. For instance, is a virus alive? It doesn't eat or carry out metabolism, and it does not contain complete instructions for replicating itself- it has to piggy-back on the complete instructions maintained by something else, using the materials that "something else" builds as a result of eating things. On the other hand, it does reproduce itself very well, it does maintain an environment separate from the outside, it does make responses to stimuli, and it does evolve and adapt. Some people would waffle on the question and say it is alive when it is interacting with a cell but otherwise not alive. Personally, I prefer to think of them as straight-up alive. Even if they cheat a little.
Self-Replicating Programs
One of the questions that invariably comes up when you head down this rabbit hole is, Can a machine or a computer program be alive? Most people prefer to think not, but why? This had been in the back of my mind lately as I began to read Complexity: A Guided Tour by Melanie Mitchell.1 Today I was reading Chapter 8, where she mentions that one objection people may give about why a program or machine cannot be alive is that it cannot replicate itself. Of course with the advent of computer viruses and worms, everyone now knows that programs can replicate themselves, and there are even some simple machines that can replicate themselves now. When she mentioned the idea of a simple self-replicating program, I immediately stopped reading the book and set about writing one, which was successful. Only later did I read her statement of the original conundrum people had about doing this, which I will restate as an English-language program:
"This is a self-replicating program, so type 'T' 'h' 'i' 's' ' ' 'i' 's'..." going onward until you get to "''' 'T' ''' ' ' 'h'..." as you begin to type instructions for typing instructions, and then...
Did you ever as a kid start thinking about thinking, and then realize you were thinking about thinking about thinking, and that therefore you were thinking about thinking about thinking about thinking, and thus... Let's just stop there. This seems to be a logical room of mirrors from which there is no escape. And yet clearly there is a way to write a self-replicating program without waiting literally forever.
My Self-Replicating Program
My solution, translated into English, was this:
"This is a self-replicating program written in a file named reproducer0. Its replicator number is zero. First, read everything between the quotation marks here into your working memory as a temporary copy. The new replicator number is the old replicator number plus one. Now, in this temporary copy, go back to the first sentence and change the number following reproducer to the new replicator number. Do the same for the number mentioned in the second sentence. Now write the modified program to a file that has the same name as the last word in the first sentence of the modified program."2
Okay, so I'm a genius for figuring out the answer to one of the foundational problems in computer science in a few minutes, right? But wait, can you explain what it is that the first program does wrong, and what it is that the second program does right to avoid the first's fate? That rather stumped me once I read Mitchell's statement of the problem after coming up with my answer, and I had to read on and have her explain it to me.
Requirements for Self-Replicating Programs
Here's my version of that explanation. In the first example, no part of the program is ever both subject and object of computation at the same time. In other words, none of the instructions are truly self-referential. My solution, which I'm sure I only came up with because such things are taken for granted by people remotely computer literate in this day and age, does contain self-referential instructions (specifically, "read everything between the quotation marks here into your working memory as a temporary copy"). A more simple way to state the solution is, "This is a self-replicating program, so copy out this sentence in its entirety." It's as if infinity must be turned directly back on itself in order to be defeated.
Mitchell points out the interesting fact that biological replicators function in the same way. DNA encodes DNA polymerases, which then go and make copies of the DNA that encoded them. Biological systems go even further, though, in that they also encode the system that translates the DNA polymerases from the DNA code. My program, like most programs, does NOT encode the means for translating its instructions into output- that role is filled by my Python interpreter. (Though apparently Von Neumann did write a program that encoded its own interpreter in his original solution to this problem, which was written out mathematically, not in a programming language.)
(The question of how all this relates to statements like "This statement cannot be proven to be true," and whether or not all mathematically true relationships can be proven to be true in finite time is left as an exercise for the reader. :) )
Life in Biological Versus Computer Viruses
And, coming back around to my original topic, viruses also do not encode their own interpreter (in compu-talk) or translation apparatus (in biospeak)- they use their host cell for that. So grant me for a moment that influenza virus is "alive." Why then is a computer virus not alive? That's a hard question.
I think it's because computer viruses cannot evolve and adapt without someone manually modifying them. Influenza can. It's interesting to compare the "programming code" of viruses (and all other life) to those used in man-made computers. The DNA code is actually quite tolerant of changes. While most mutations do make things worse, most mutations also fail to totally crash the system, which gives you breathing room to do a random walk through search space looking for the mutations that help you out. DNA replication is unavoidably inaccurate to some degree- it's the nature of the random and transient electrostatic interactions that the whole thing is based on, such that every once in a while a mistake will be glommed onto long enough to get stuck into the final product- and many viruses actually have very low fidelity in copying their DNA, which seems to allow them to modify their code (evolve) even faster.
On the other hand, try going through the code of a computer virus and randomly changing letters to other letters. Or even going down to the binary and randomly changing ones to zeroes or vice versa. How long is that virus going to keep functioning once you start doing that? What are the chances you'll make a virus that's even better by doing this? Not long, and zero.
An Evolvable Programming Language?
So perhaps what would be needed for a program to really come alive is a computer programming language that is tolerant to random changes (including not just changing symbols, but also deleting, repeating, and moving symbols or groups of symbols, and maybe even random insertion of code from outside) and a copying method that introduces random changes into programs written in that language. What would would such a programming language look like? What would happen if a computer virus was written in it, complete with its own faulty replicator?
I guess that's another exercise for the reader.
Notes
1On Melanie Mitchell's book on complexity. I've really been enjoying this book so far. It covers the basics of all kinds of things I always I thought I would be interested in if I could get a reasonable explanation of them (for example, chaos theory, fractal geometry, Turing machines) as well as things I definitely know I am interested in and have spent a fair amount of time studying (genetics, evolution, thermodynamics, stock markets...). The book has made me realize a common thread between many of my passions, which is that I am fascinated by complex systems, in general. (Where my personal over-simplified definition of a complex system is "hard-to-predict large-scale patterns resulting from small-scale actors following simple rules.") If I had encountered a book like this in high school, my life might have taken a different turn. If you're interested in these kinds of things, I would definitely recommend the book, as it explains things gently and clearly. Gödel, Escher, Bach, another book that I've been meaning to read and that was written by Mitchell's PhD advisor, seems like a good potential companion book.
2The actual Python program is below. The name of the progenitor program is "reproducer_0.py". (Keep in mind I've no formal training in programming, and this can be considered as part of the ongoing process of teaching myself Computer Science 101.)
reproducer_number = 0
#reproducer ver 1.0
#when reproducer_(n).py is run, it makes a new file called reproducer_(n+1)
#that is identical to reproducer_(n)
#(n) is given to be the reproducer_number at the start of the file
repn = open("reproducer_%d.py" % reproducer_number)
repn_read = repn.readlines()
repn.close()
new_reproducer_number = reproducer_number + 1
repn_read[0] = "reproducer_number = %d\n" % new_reproducer_number
repnplus1 = open("reproducer_%d.py" % new_reproducer_number, "w")
for line in repn_read:
repnplus1.write(line)
repnplus1.close()
I spent much of the day making more complicated versions of this. For instance, if you run replicator_0 above, you get replicator_1. If you run replicator_0 again, it just overwrites the replicator_1 it already made; if you want replicator_2, you have to run replicator_1. So I made a version that checks out all the other replicators in the same folder, figures out the maximum replicator number present, and names the new replicator as the next number after that maximum. So you can just run replicator_0 over and over again to get more and more copies.
Then I made versions that keep track of their own geneaology, all the way back to replicator_0. One version just tracks its lineage within its code (as a "genotype," to use biotalk), and another version also displays its lineage in the filename (as a "phenotype"). It is alarmingly tempting to write versions that replicate without having to be told, or randomly insert the new copies of themselves into other folders on my hard drive, or thumb drive...
