How to find and how to store?

For readers of programming.reddit at least, it’s clear that Erlang is gaining momentum. Erlang is a programming language + virtual machine environment for extremely concurrent and fault tolerant software. It was built for the telecommunication branche and the lead scientist is Joe Armstrong.

Nice to hear you quoting Hamming – I often ask students the same questions!

The most important things:

  • how to store things
  • how to find things

By store I mean store forever – things like backup and syncing systems should not exist and are a consequence of a broken storage paradigm.

Once we have stored things we need to find them.

We need to understand how to make systems that run forever and evolve with time.

Am I working with these? – Yes and no. I keep coming back to them, then get stuck and work on something else, then go back to them.

Published in: on August 28, 2007 at 9:25 am  Leave a Comment  

The A in RSA

The RSA algorithm for public-key encryption is used practically whenever a secure connection must be established. The A in RSA is Leonard Adleman. He recieved the Turing Award for this work. He is also doing lots of rather theoretical stuff with DNA.

His reply to the Hamming question is:

Your question is a good one and to give a complete answer would require more time than I currently have; so I will just provide a brief remark:

  1. NP≟P (or some varient of it) is the most important open problem in CS. It is also on the short list of most important open problems in mathematic (see the Cole prize).
  2. I don’t work on it for 2 reasons. First, I did work on it for a few years as a youth, I had a few ideas worth (I thought) writing down (see “Time Space and Randomness” by moi), but ultimately I came to the conclusion that the problem was not “ripe” – ready to be solved. A few more decades (at least) of research would be required. It is for this reason that I changed my research to work on Fermat’s Last Theorem instead. My intuition suggested that, after 3 centuries, the problem was ripe. When Andrew Wiles proved FLT a few years ago, my consolation prize was to know that at least my intuition was correct.

Adleman is the first to respond with the P=NP problem. Is the P≟NP problem more a prestige problem than a theoretical one? Whether the result is useful depends on the answer. So we don’t know how important it is.

Published in: on August 26, 2007 at 7:41 pm  Comments (1)  

Create your own Fantasy Research Lab

Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.

If you read about Lisp, it won’t take long until you come to this quote. It’s from Philip Greenspun, who worked with Lisp while it was popular. Later he was one of the first internet entrepeneurs and founded and built the ArsDigita Community System.

Today he spends his time teaching helicopter and computer science students, taking photos and traveling. He response came from Africa.

I wrote

back in 2003. I don’t think too much has changed since then.

I haven’t read this before. It’s a nice thought experiment.

New graduate students in computer science often have a difficult time choosing among research projects and may never develop a broad view of the field nor think about the relative significance of efforts in various directions. When new graduate students ask me for advice I tell them to start by pretending that they are the lab director for computer science at a brand-new research university and to come up with a plan for how they’d populate their lab with projects. This is sort of like the fantasy baseball leagues that are popular with kids, hence the page title. In preparing a fantasy research lab plan, a student will need to familiarize him or herself with a broad range of problems and the current state of the art in solutions. This ought to give the student more perspective in planning a career.

He goes on and develops some projects and what research is needed for them.

I would add making

a reality would be a very useful problem too, though not fundamental. Consumers shouldn’t have to use scaled-down mainframes such as Windows and Mac OS.

His second link leads to a lengthy description about a phone-centric distributed computing thing.

Published in: on August 24, 2007 at 1:06 pm  Leave a Comment  

Personal Research Agenda

I found Brad Neuberg wrote a blog entry, where he ponders about the exact same question as i am doing here. He has a list of things, he considers important.

  1. What does a true, next-generation Internet word processor look like, one that deeply embeds the browser and community?
  2. Is it possible to continue creating radically new versions of the web and browsers that introduce fundamental new advances?
  3. The flip side of the previous question is: How far can we push the present generation of web browsers from the inside through clever tricks?
  4. How can we create communication technologies that provide ever greater levels of interpersonal connection, collapsing the geographical distance between loved ones and family?
  5. How can we create email systems that almost completely eliminate email from your life, allowing you to focus on the emails that you need to with as little time invested as possible?
  6. How can we create search systems that make answering our questions even more intuitive and integrated then they are now?
  7. Can we create hypertext technologies that transform how we link and talk about information and documents? Further, how can we port these hypertext technologies to the contemporary web so they are actually adopted?
  8. Handling events still sucks — how can we make scheduling and discovering events that are important and relevant to you and your groups suck much less than it does now?
  9. How can we be more effective at creating ideas?
  10. Can we create technologies that are as fundamental and important as writing has been?

That’s quite web centric, but we agree that it is important to think about this.

I’d love to see others create similar lists on their own blogs. One of the reasons for posting this list is I want to attract others who are interested in similar things, so we can brainstorm about them over a strong cup of coffee (or a strong Guinness).

Me too! I just have no list of my own, yet.

Published in: on August 22, 2007 at 2:55 pm  Leave a Comment  

The spec and the knowledge

The Lisp programmers claim that nearly every programming technique in the universe was first invented by them. Lisp is one of the oldest programming languages still in use. It was invented by John McCarthy in 1958 for his AI research. In 1971 McCarthy recieved the Turing Award for his major contributions to the field of Artificial Intelligence. Since 2001 he is Professor Emeritus of Computer Science at Stanford University.

McCarthy emphasizes mathematical logic in his research and his answer to my Hamming Question mirrors that. His email reply:

Two of the most important problems in computer science are getting interactive provers for showing that programs meet their specifications and formalizing common sense knowledge and reasoning in mathematical logic. I work on the latter. Arguments for the importance of these problems are in the articles reprinted on my web site.

This conforms with his article AI Needs More Emphasis On Basic Research from 1983:

In my opinion, the key problem at present is the formalization of common sense knowledge and reasoning ability. It still looks to me that separating epistemology from heuristics will pay off.

AI research has changed in the last twenty years. Today it is mostly about heuristics (perceptrons, bayesian filters, …) and we still have no model for human knowledge. We can’t measure knowledge and experience. I don’t even know about any ideas how to attack this problem.

We also won’t reach human level intelligence by building larger and larger production systems involving more and more facts all on the same level.

You can build pretty impressive things this way, though. Google is the prime example for this.

Published in: on August 22, 2007 at 10:07 am  Leave a Comment