How’s that for a post title that gives me a lot to talk about? Obviously, I can only talk about things I know I am ignorant of. Also, I will restrict the topic to the vague category of computer science, so that will narrow down the list. And what the hell, I’ll make it a top ten list, since those seem to be so popular these days. So, without further ado, here is the list of 10 things that finish the sentence, “I don’t know… “
#1 “What monads are.” — I have tried and tried to get a straight answer to this one. I have not tried terribly hard, but that’s how these things happen. I know monads are some kind of tricky way to avoid side effects for certain things like IO in functional languages. I know that they’re a transplant from category theory in mathematics, but to date monads are a black magic as far as I’m concerned.
#2 “What currying is.” — Listen. I will just tell you that I have not investigated this one. I keep seeing it thrown around as a feature, or mechanism certain languages have, but haven’t looked into it. A quick trip to Wikipedia would probably cure me, but I need to pad this list a bit.
#3 “What the minimal set of features for a Turing complete language are.” — All modern programming languages are Turing complete, sure. SQL is not. Regular expressions are not. I have an intuitive sense of the ways these things are different from real programming languages. Currently though, if you gave me a brand new programming language you just invented, I couldn’t tell you with certainty whether or not it was Turing complete.
#4 “How to program in Smalltalk, Haskell, Scheme, Objective-C, OCaml, Tcl/Tk, Brainfuck, Befunge, and Python.” — This list only includes languages that A: I could think of off the top of my head, and B: languages I’m interested in learning eventually. Scala almost made this list, but I don’t like the JVM enough to get excited. .NET can likewise go away. I won’t list all the reasons I am interested in these languages, but Befunge is worth learning specifically because it is 2D.
#5 “How to program x86 with all the neat extensions like MMX, and SSE 1,2,3 etc. “ — I have programmed assembly for the Motorola 68000 for a class on computer organisation, but the huge instruction set available on a modern Intel machine intrigues and mystifies me.
#6 “Whether P = NP “ — Luckily, I am in good company on this one. Personally, I don’t think they are equal, but the optimist inside me always holds onto hope. The rate at which mankind would progress following a constructive proof that P=NP would be something to marvel at.
#7 “The exact relationship between time complexity and space complexity.” — Everyone seems to have the intuition that there is always a tradeoff between the amount of computation that must be done and the amount of storage space required. Store a bunch of lookup tables and you can reduce your computational load. Increase the complexity of your algorithm and skip making up a bunch of tables. It seems very fundamental, but is there an exact mathematical theory for a law of “conservation of complexity” or something similar? I don’t know. And I promised myself I wouldn’t go to Wikipedia while making this list. (Actually I already cheated, because I looked up Befunge to make sure it was the 2D language I was thinking of. It was, so I claim it doesn’t count!)
#8 ” enough about reversible computation.” — This one is stretching the format a bit, but essentially, I know a little about reversible computing, but not anywhere near as much as I would like to. The basic idea is really neat: theoretically cool processors. Information isn’t destroyed in the process of computing, so no heat is generated. The sad part is that I have told you basically everything I know about reversible computing in this little paragraph.
#9 “How to write a compiler.” — I am sorely lacking in the skills to write compilers of computer languages. I am more specifically lacking in the skills to write compilers for 2D languages…
#10 “How to parallelize quicksort in Erlang.” — In theory, it should be easy to make divide and conquer algorithms parallel, but I cannot for the life of me figure out how to do this one. It is probably more a result of my lack of competency with Erlang than with any real barrier to writing such an algorithm… But there you go: number 10.
There are a lot more things I could write in here, like: “How long sandwich meat keeps in the fridge.” and, “When it’s finally going to cool down in Florida. It’s still 70 in the middle of December.” and “Who let the Dogs out?” But I think I will leave it this length for the time being.
9 Comments so far
Leave a comment
Retrograde Dynamic Tablature Assembly 
I’ve always found P=NP? not to be a particularly interesting question because it depends in a very fundamental way on the primitive operations we have available for computation, which depends in a large part on physics, where we don’t have all the answers yet. For example, it would be possible to construct a machine that solved NP problems in P time in a world that obeyed relativity but not quantum mechanics and in which matter was arbitrarily divisible.
Comment by anon December 13, 2007 @ 9:07 amYou’re right, the P=NP problem is sort of based on the methods we currently use to compute. So it wouldn’t have any bearing on what is computable quickly with say, a quantum computer. But I still find the question interesting!
Comment by habitue01 December 13, 2007 @ 9:13 amTell me then, what do you find interesting about it, given that an answer to it doesn’t necessarily have any real world consequences concerning actual computation, since you seem to be hardly the kind of person who likes to lose themselves in a world of abstraction without any regard for reality? (I deduce this from your lack of Haskell-love, which is common among mathematicians.)
Comment by anon December 13, 2007 @ 9:42 amI too don’t know those things.
It don’t matter how many tutorials I read,
this stuff doesn’t stick to my brain.
I’m doomed, I suppose.
Or maybe I’m just plain dumb.
Ciao
Comment by Giovans December 13, 2007 @ 10:21 amOh don’t get me wrong, I am perfectly content with completely abstract thought with no real application (and Haskell is in my langeages I want to learn up there). But actually an answer to P=NP? has infinite practical applications. Specifically if there were a constructive proof that P=NP(one that gives an algorithm for an NP-Complete problem in polynomial time) then we could prove or disprove just about every theorem out there. It really is a practical question, just framed in terms of theoretical limits. It’s not asking whether a given set of problems are computable, but whether they can be calculated in a practical amount of time.
Even if someone proved P!=NP, there is a good chance such a proof would shed some light on what the real differences between complexity classes are.
Comment by habitue01 December 13, 2007 @ 10:23 amRight, but whether they can actually be calculated in a practical amount of time depends on how you construct your machine, as do what the complexity classes even are, what falls in them, and what they mean. But proving P=NP would be done by proving that the ordinary computers, as we currently have them, can reach such solutions in P time (or that they can’t), which shows nothing about “real/actual” complexity. Anyways, just because it can be done in P time doesn’t mean it can be done quickly, the exponent could easily be a few thousand or the algorithm might consume a huge amount of memory, etc. Nor would such a process be extremely useful in proving mathematical truths, as far as I can see. First of all many truths are simply unprovable (Godel, at least if math is consistent). Secondly most useful mathematical advancements come from developing new axioms systems, new formalisms, not proving things in existing ones. While I agree that it is an interesting abstract problem I honestly don’t see much point in answering the question, because its primary consequences seem to be only for more abstract mathematics, which also lack practical consequences. But perhaps this reflects more my beef with abstract mathematics in general, which I find often forgets what the point of math is.
Comment by anon December 13, 2007 @ 10:36 am“I know monads are some kind of tricky way to avoid side effects for certain things like IO in functional languages.”
I’m afraid you don’t even know that, because it isn’t true. Yes, IO is a monad, but so are [] (the list datatype), Maybe, Either.
Monad is a typeclass (similar to an interface in Java) for general computation. The IO monad presents sequential computation; [] presents non-deterministic computation (computation that might have one of several results); Maybe presents computations which might fail. And so on.
The most important function in the monad typeclass is (>>=). a >>= b means “take the result of a, and apply b to it”.
That’s really about all there is to it.
Comment by Max December 13, 2007 @ 11:12 amI always find blog comments a facinating peek into human nature. In particular, it seems like comment format brings out the most arrogant in us. Take any normal person who could carry a polite two-way conversaion in a bar for hours on end and give him a blog to read, and suddenly he feels the uncontrollable desire to take the blogger to task on every single little thing he knows, or seems to know, or thinks he almost kinda sorta grasps to a fractionally greater degree than the blogger. And not in a polite, “oh, by the way, here’s a little theory behind that…” sort of way, but instread in a pissy “what gives you the right to think you can pollute the Internet with your ignorant spew” sort of way.
In any case, I’m going to have to forego my usual lesson on Monadic theory and finite automata… there’s another blogger who just completely mangled the symmetry identity of complex Fourier Transforms, and it’s my duty to beat the mistake into the ignorant fool publicly. That’ll show him…
Comment by Bca December 14, 2007 @ 1:54 amMy spouse and I absolutely love your blog and find the majority of your post’s to be precisely what I’m looking for.
Comment by Vada December 21, 2012 @ 9:01 amDo you offer guest writers to write content available for
you? I wouldn’t mind creating a post or elaborating on most of the subjects you write in relation to here. Again, awesome website!