Archive for the 'Computation' category

Animal Experimentation and Simulation

Mar 01 2010 Published by under Bad Software, Computation

In my post yesterday, I briefly mentioned the problem with simulations
as a replacement for animal testing. But I've gotten a couple of self-righteous
emails from people criticizing that: they've all argued that given the
quantity of computational resources available to us today, of course
we can do all of our research using simulations. I'll quote a typical example
from the one person who actually posted a comment along these lines:

This doesn't in any way reduce the importance of informing people about
the alternatives to animal testing. It strikes me as odd that the author of
the blogpost is a computer scientist, yet seems uninformed about the fact,
that the most interesting alternatives to animal testing are coming from that
field. Simulation of very complex systems is around the corner, especially
since computing power is becoming cheaper all the time.

That said, I also do think it's OK to voice opposition to animal testing,
because there *are* alternatives. People who ignore the alternatives seem to
have other issues going on, for example a sort of pleasure at the idea of
power over others - also nonhumans.

I'll briefly comment on the obnoxious self-righteousness of this idiot.
They started off their comment with the suggestion that the people who are
harassing Dr. Ringach's children aren't really animal rights
protestors; they're people paid by opponents of the AR movement in order to
discredit it. And then goes on to claim that anyone who doesn't see the
obvious alternatives to animal testing really do it because they
get their rocks off torturing poor defenseless animals.


Anyway: my actual argument is below the fold.

Continue Reading »

66 responses so far

Cloud Computing

May 20 2009 Published by under Computation, Coolness, Programming


In general, I try to keep the content of this blog away from my work. I don't do
that because it would get me in trouble, but rather because I spend enough time on work, and blogging is my hobby. But sometimes there's an overlap.

One thing that's come up in a lot of conversations and a lot of emails it the idea of cloud computing. A lot of people are interested in it, but they're not really sure of what it is, or what it means.

So what do we mean when we talk about "cloud computing"? What's the cloud? How's it different from good old-fashioned client/server computing?

Continue Reading »

No responses yet

My Favorite Strange Number: Ω (classic repost)

Dec 31 2008 Published by under classics, Computation, Numbers

I'm away on vacation this week, taking my kids to Disney World. Since I'm not likely to
have time to write while I'm away, I'm taking the opportunity to re-run an old classic series
of posts on numbers, which were first posted in the summer of 2006. These posts are mildly

Ω is my own personal favorite transcendental number. Ω isn't really a specific number, but rather a family of related numbers with bizarre properties. It's the one real transcendental number that I know of that comes from the theory of computation, that is important, and that expresses meaningful fundamental mathematical properties. It's also deeply non-computable; meaning that not only is it non-computable, but even computing meta-information about it is non-computable. And yet, it's almost computable. It's just all around awfully cool.

Continue Reading »

No responses yet

Scale: How Large Quantities of Information Change Everything

Nov 24 2008 Published by under Computation

Technorati Tags: , ,

Since people know I work for Google, I get lots of mail from folks with odd questions, or with complaints about some Google policy, or questions about the way that Google does some particular thing. Obviously, I can't answer questions about Google. And even if I could, I wouldn't. This isn't a Google blog; this is my blog, which I write as a hobby in my free time.

But there are intersections between my work life and my hobby. And one of the ideas that underlies many of the questions that I receive, and which also
hits on my work, and my hobby. And that's the idea of scale. Scale is computer-science talk for how things change as they get bigger. In particular, I'm talking about the scale of information; the amount of information that we use on a daily basis has increased dramatically, and the amount of dramatic, fundamental change that has resulted is both amazing, and amazingly unnoticed by most people.

Continue Reading »

27 responses so far

Cryptographic Integrity using Message Authentication Codes

Oct 06 2008 Published by under Cryptography

I don't have a lot of time to write; I'm having my fifth (I think) upper endoscopy done tomorrow, which means that the day's going to be a wash; and Yom Kippur is thursday, and I need to cook, so between the personal crap and work, I'm not going to have much time for blogging. So I'm trying to make use of the time I have to write one short but (hopefully) interesting post.

One thing that I've mentioned in passing is the distinction between message confidentiality, and message integrity.

Confidentiality is most of what we've been talking about
so far. Confidentially provides a guarantee that when you send an encrypted message, no one but your intended recipient is able
to read the plaintext.

Integrity is something very different. Integrity guarantees
that if you send an encrypted message, there's no way that the encrypted message could have been tampered with after you encrypted it, without the recipient knowing it.

Continue Reading »

15 responses so far

Monoids and Computation: Syntactic Monoids

Mar 06 2008 Published by under Abstract Algebra, Computation

While doing some reading on rings, I came across some interesting stuff about
Monoids and syntax. That's right up my alley, so I decided to write a post about that.

Continue Reading »

No responses yet

Colored Petri Nets

Oct 10 2007 Published by under Computation, Graph Theory, Networks, Programming

Colored Petri Nets
The big step in Petri nets - the one that really takes them from a theoretical toy to a
serious tool used by protocol developers - is the extension to colored Petri nets (CPNs). Calling them "colored" is a bit of a misnomer; the original idea was to assign colors to tokens, and allow color-based expressions on the elements of the net. But study of analysis models quickly showed
that you could go much further than that without losing the basic analyzability properties
that are so valuable. In the full development of CPNs, you can associate essentially arbitrary
collections of data with Petri net tokens, so long as you use a strong type system, and keep
appropriate restrictions on the expressions used in the net. The colors thus become
data types, describing the types of data that can be carried by tokens, and the kinds of tokens that
can located in a place in the net.

So that's the fundamental idea of CPNs: tokens have types, and each token type has some data value associated with it. Below the fold, we'll look at how we do that,
and what it means.

Continue Reading »

No responses yet

Modeling Concurrency with Graphs: Petri Nets

Oct 01 2007 Published by under Computation, Graph Theory

Among many of the fascinating things that we computer scientists do with graphs
is use them as a visual representation of computing devices. There are many subtle problems that can come up in all sorts of contexts where being able to see what's going on can make a huge difference. Graphs are, generally, the preferred metaphor for most computing tasks. For example, think of finite state machines, flowcharts, UML diagrams, etc.

One of the most interesting cases of this for one of the biggest programming problems today is visual representations of concurrency. Concurrent program is incredibly hard, and making a concurrency regime correct is a serious challenge - communicating that regime and its properties to another developer is even harder.

Which brings us to todays topic, Petri nets. Actually, I'm probably going to spend a couple of days writing about Petri nets, because they're fun, and there are a lot of interesting variations. The use of Petri nets really isn't just an academic exercise - they are seriously used by people in a lot of real, significant fields - for one example, they're very commonly used to specify behaviors of network communication protocols.

Continue Reading »

12 responses so far

The Perspex Machine: Super-Turing Computation from the Nullity Guy

Sep 09 2007 Published by under Computation


If you remember, a while back, I wrote about a British computer scientist named James Anderson, who
claimed to have solved the "problem" of "0/0" by creating a new number that he called nullity
. The
creation of nullity was actually part of a larger project of his - he claims to have designed a computing
machine called the Perspex machine which is strictly more powerful that the Turing machine. If
this was true, it would mean that the Church-Turing thesis is false, overturning a huge part of the theory
of computer science.

Of course, just overturning the theory of computer science isn't grandiose enough. He also claims that this solves the mind body problem, explains how free will works, and provides a potential
grand unified theory of physics. From Anderson's own introduction on his website:

The Book of Paragon is a web site that offers one solution to the centuries old philosophical conundrum
of how minds relate to bodies. This site shows that the perspective simplex, or perspex, is a simple
physical thing that is both a mind and a body.

The perspex can be understood in many ways. Mathematically, the perspex is a particular kind of matrix; concretely, it is simultaneously a physical shape, a physical motion, an artificial neuron, and an instruction for a machine that is more powerful than the Turing machine. In other words, a perspex is an instruction for a perspex machine that is more powerful than any theoretically possible digital computer.

The perspex machine operates in a 4D space of perspexes called perspex space. This space is related to the 4D spacetime we live in. It is claimed that the perspex machine can describe any aspect of the universe we live in, and can be built from any part of our universe. In other words, the universe can be understood as a perspex machine. And, on the materialistic assumption, our bodies and minds are physical things so they, too, can be understood as perspex machines.

This site contains mathematical formulas for the perspex machine and for properties such as feeling, consciousness, and free will. These things are described in scientific papers, books, and software that you can download and run. The site also contains news items that explain the perspex machine in a non-technical way, and it has links to old research on the perspex machine.

He also claims that the Perspex machine can prove the existence of free will, God, and original sin.

One thing you've got to give to Anderson - the guy's got ambition.

Continue Reading »

41 responses so far

Graph Searches and Disjoint Sets: the Union-Find Problem

Sep 06 2007 Published by under Computational Complexity, Graph Theory, Set Theory

Suppose you've got a huge graph - millions of nodes. And you know that it's not connected - so the graph actually consists of some number of pieces (called the connected components of the graph). And there are constantly new vertices and edges being added to the graph, but nothing is ever removed. Some questions you might want to ask about this graph at a particular point in time are:

  • How many components are there in the graph?
  • Which component is vertex X in?
  • Are vertices X and Y in the same component?
  • How many components are there?

All of these questions are variants of a classic computer science problem, called
union-find, which also comes up in an astonishing number of different contexts. The reason for the name is that in the representation of the solution, there
are two basic operations: union, and find. Basically, the division of the graph into
components is also a partition of the vertices of the graph into disjoint sets: union find
is a problem which focuses on a particular kind of disjoint set problem, where you can modify
the sets over time.

Continue Reading »

12 responses so far

« Newer posts Older posts »