The genetic algorithm is one method of solving problems in computer science. Although it comes in many flavors, for the purposes of this article I’ll focus on a simple example.
Imagine you have a multiple choice test with 20 questions. Each question can be answered by choosing one of four choices. A compete answer to the test consists of a string of 20 characters, each of which is chosen from the set {A, B, C, D}. The solution to the test is an answer string where every answer is correct.
A valid, but not necessarily correct, answer string would look like this:
ABDCBDABDBCABDCCBABD
How many possible answer strings are there? Well, each position in the string can take on 4 different values, and there are 20 of them, so there are 4^20 = 1,099,511,627,776 possible ways to answer the test. That’s “just” over 1 trillion (over by 99 billion, that is). To give you a sense of perspective, that’s about as many seconds as there are in 35,000 years. Yeah, that’s a lot.
Read more…
Computer Science, Evolution
Time travel has been a trope of Science Fiction since its inception as a genre. Perhaps the most famous is H. G. Wells “The Time Machine,” which gives us brief glimpses of the future at several points. The idea is certainly seductive. Who wouldn’t want to be able to whiz off to the future to view the progress humanity has made, or travel to the past and witness historic events?
But whether or not time travel is possible is still an open debate among physicists. In this post I want to discuss some of the paradoxes that would seem to result if time travel is possible, as well as an interesting algorithm for solving NP problems using a time machine.
Read more…
Computer Science, Metaphysics, Musings, Philosophy
In mathematics, a fixed point is a value of a function that maps to its self. In other words, x is a fixed point of a function f if f(x) = x.
According to Kleene’s recursion theorem, fixed points exist in every programming language; i.e. in every programming language, there is at least one program (actually infinitely many, trivially different from each other.) the output of which is an exact duplicate of the program.
Attached you will find a fixed point program written in perl.
Read more…
Computer Science, Programing
At a philosophical discussion last night, we read “Jipi and the Paranoid Chip” by Neal Stephenson (Which, I just noticed, was posted to reddit 9 days ago, and got 1 up vote and 1 down vote. WTF?). If you’ve never read anything by him, I suggest you stop right this moment, go out and buy Cryptonomicon, Snowcrash and the Baroque Cycle, and do nothing until you’ve read them all.
The story is about a piece of software that was evolved to be indistinguishable from a paranoid schizophrenic. In the course of discussing the plot, someone asked if the paranoid schizophrenic chip would pass the Turing Test, with their inclination being no, it couldn’t.
Read more…
Computer Science, Metaphysics, Philosophy
The paradox of the heap, also known as the Sorities Paradox (from the Greek word for heap), is a paradox revolving around the problem of vagueness.
In its classical formulation, the paradox is expressed as follows:
One grain of sand is not a heap.
If one grain of sand is not a heap, adding one grain of sand will not make it a heap.
So two grains of sand are not a heap.
So three grains of sand do not make a heap.
…
X grains of sand do not make a heap.
Therefore, 10,000 grains of sand do not make a heap.
The form of this argument boils down to:
X grains of sand are not a heap.
If X grains of sand are not a heap, adding 1 grain of sand will not make it a heap.
(Some arbitrary large number of grains of sand) do not make a heap.
Read more…
Computer Science, Evolution, Musings, Philosophy, Vagueness
Cognitive Daily has an interesting discussion going on about whether or not an artificial intelligence requires a body. There are some interesting posts in the discussion, but as with most of these discussions, it quickly turned into a matter of “what does it mean to be intelligent?”
To drop my two cents in on the matter, I must say that the answer to the question is obviously yes; but we have to define “body.”
Read more…
Computer Science, Musings
Computers are a wonderful invention, capable of a profound variety of actions. But there are limits to what a computer can do, and today I wish to talk about one of them. Specifically, I wish is discuss the Busy Beaver problem.
Read more…
Computer Science, Logic