|
Tue Dec 18 17:01:55 EST 2007
happy holidays
--
The Semester
Wow, it's been a little while since I posted anything. I've been
pretty busy with school and work, but now that the semester is
basically finished I though I should write something to show that
I am not dead :).
I took a distributed operating systems and a theory of computa-
tion class. The OS class was pretty interesting, but I wish we
spent more time on distributed algorithms. A lot of time was
wasted on a project. The goal of the project wasn't silly, it
was the framework in which we had to implement the code that was
the pain. It came down to simulating a wireless sensor network
using this packages called "TinyOS". The latest version might be
a tad more bearable, but we were stuck using an old version. I
am certain that we could have created our own (discrete event)
simulators from scratch in a much shorter amount of time, and we
would have probably learned more about the actual problem itself.
Overall the class was good, since I did learn some cool new algo-
rithms - a couple well enough, in fact, to add Wikipedia articles
on them :).
The second class on the theory of computation provided a nice re-
fresher course on finite automata. Unlike the theory class I had
when pursuing my MS, we got to spend a significant amount of time
on context-free languages, push-down automata, and Turing ma-
chines. We also spent a decent amount of time on complexity
classes, such as P and NP. I learned a lot, and I am hoping the
CS department here offers some graduate level classes on the sub-
ject. If not, there are always the MIT OpenCourseware offerings
on the subject.
In Spring, I am taking a graph theory class and a graduate level
programming languages class. In the PL class, we'll most likely
be writing compilers and such - which is a pretty cool thing to
do. Also next semester, I am going to be taking the program's
qualifier exam; and this means that if I pass, I'll have to get
serious about picking an adviser, committee, and developing a
plan of study. I am looking forward to the change and focusing a
bit on things in which I am interested, but the test will not be
easy.
The Break
I am going to take advantage of the break to work on a couple of
things my mind's been drifting towards. One is a problem sug-
gested to me by one of the CS professors. It is interesting, and
straightforward enough to keep my attention; in otherwords I find
it easy to get obsessed with it. I also would like spend some
time working on the DFA->RE transformation in FLaT. I've started
to implement a version of an FA that contains "regular expres-
sion" objects as its transition labels, but I have to go a few
steps further. In order to do the DFA->RE transformation, I am
going to implement state elimination, and this will mean that the
RE-objects-as-labels will be interacting using the usual regular
expression operators.
Artificial Life
I read a very interesting article [1] today that talked about
some efforts scientists are undertaking to create "artificial
life." This means that they are inventing the entire strand of
DNA in the lab. They are using existing DNA to cheat a bit, but
it is still an interesting concept. This got me thinking about
how exactly DNA works to encode all the complex machinery and in-
teractions inside of a life form. I think that any human, no mat-
ter how smart would have to cheat in this way. It seems virtual-
ly impossible to start from scratch.
Given the recent hours and days spent contemplating Turing ma-
chines, the languages (programs) they accept, and their inherent
limitations, it made me wonder about a couple of things. For ex-
ample, is it possible to reverse engineer DNA? History is
wrought with people saying, "that's impossible", but if one real-
ly thinks about what it means to reverse engineer DNA-as-a-pro-
gram (i.e., set of instructions), the mind should shut down by
the sheer size of the problem. In fact, this seems akin to in-
quiring about the properties or function of a Turing machine,
given the description of the machine itself - which is well know
to be "undecidable".
It can be said that DNA doesn't just encode a single machine. It
encodes many machines, and all of these machines must interact in
concert with one another. Many unrelated machines and systems
share the same parts, and modify a seemingly insignificant part
of one machines adversely affects many others. This to me seems
infinitely more complex than figuring anything about our silly
models of computation. An organism can also be viewed as the ul-
timate "shared memory" program - and how on Earth could all the
problems that come with shared memory programming be worked out
explicitly?
Given that DNA encodes a complex network of interrelated systems,
how does one /really/ engineer an artificial life? It just
doesn't seem possible to start from scratch and design an organ-
ism from scratch. I think this is beyond the capabilities of hu-
mans. It may be possible to program little autonomous things
much like computer scientists can create interesting cellular au-
tomata, but at the end of the day creating an organism from
scratch is such an enormous feat that it seems impossible. Of
course, the scientists working in this area are using DNA from an
existing organism (i.e., a working program) to start with.
This is not unlike learning a new language looking at examples,
but DNA's encoding is so much more complex than simple human pro-
gramming languages. DNA is so densely packed with information,
that the only way to see what is in it is to "let it run". But,
it is not simply a set of instructions contained in the DNA. It
is instructions on how to construct the machines and systems that
THEN interact at various stages of development and life to make
the organism what it is. On top of this are assumptions based on
the basic laws of physics - and we don't even know what these are
exactly.
To me, a practical computer analogy would liken DNA to a self-ex-
tracting hierarchical and maximally compressed TAR file that con-
tains a set of programs. Hierarchically compressed in that vari-
ous levels of compression reveal different programs that are then
used to either uncompress other parts, or generate additional
code and instructions that are to be executed by other machines
or go on to create yet more code. It is a chain reaction of in-
structions creating machines that create more instructions and
machines. The more machines and systems that are set in motion,
the more that can be done as these machines interact and grow.
The sheer complexity of it all is mind blowing, and I challenge
anyone to design such a system from scratch. It is in my mind in-
finitely more complex than trying to model a chemical reaction or
something like a nuclear explosion - and human technology is
barely at the stage where it can do either of these very well. In
fact, it is similar to the study of algorithms that asks, "give
some string of 1's and 0's, what is there a smaller way to gener-
ate this sequence that is /smaller/ (in terms of computer memory)
than a program that simply prints the string explicitly? In oth-
erwords, can we find a program or algorithm that generates this
string or sequence of symbols? Translate this to the task of cre-
ating artificial life from scratch. Assuming one has figured out
how the pieces and parts of the organism will work together - how
do you "grow" this system by means of some set of primitive in-
structions? The instructions here are obviously the DNA, but the
problem just seems intractable to me.
It is as if we've been given some alien technology to reverse en-
gineer - but who's to say that humans are even capable? Who's to
say that /anyone/ or being (save your Supreme Deity of choice)
has the capacity to understand the interactions taking place? A
proposed experiment to a human's capability would be to create
such a compressed tarfile as the one described above - except one
that would obviously have to be much simpler since a human is de-
signing it. The challenge would be for the investigator(s) to de-
termine accurately what is happening. In other words, one would
have to construct a model of this unknown system. Of course one
would be given a time limit, but the idea would be to see how
good humans are at figuring out systems. In summary, the experi-
ment is to start with a known system, allow people to observe how
it works in a way similar to how people observe the development
and life functions of simple organisms, have the subjects create
a model of what they think is going on, then compare it to the
actual system. I believe the results will be shockingly bad, even
with the help of techniques like Markov Chains.
Another thought that comes to mind is, if a Turning machine can't
determine what any other TM (including itself) does, how can we
(the product of DNA instructs) determine how life works with the
degree of certainty that would allow us to create real artificial
life or intelligence?
Well, sorry for the rantings of a mad man - that'd been building
up in me for a while. Over the next week or so, I'll be cleaning
up this post and adding more thoughts in other ones. Have a Merry
Christmas and a Happy New Year.
[1] http://www.washingtonpost.com/wp-dyn/content/article/2007/12/16/AR2007121601900.html
--
Powered by vee
Copyright © 2006-2008
|
|