Category: Computer Science
On Evolution: Biological and Computational
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.
Time Travel, Paradoxes and Computation
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.
You Don't Know What You Can't Know: Fitch’s Paradox of Knowability
Or, You Can't Know What You Don't Know You Can't Know.
This is an interesting result from modal logic that I will try to sketch here. The upshot of the result, depending on which side of a divide you fall into, is either that there are some truths that are logically impossible to know, or that every truth is already known by someone.
The dividing line in this case is whether you are a realist or anti-realist. The realists posit that there is an external reality that has certain definite properties. The anti-realist deny that such an external reality exists (or, in some cases, that we can have access to it). I'll get more into this distinction after I sketch the proof. If you find logic boring, feel free to skip the proof and scroll to the end for a brief discussion on the implications of this result.
A Fixed Point Program
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.
The Turing Test and Philosophical Zombies
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.
Must AIs be embodied?
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.”
Busy Beavers
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.
XML Feeds