Is the Universe the Smallest Possible Representation of Itself?

6 Replies

Four centuries ago, Newton showed that the gravitational field of a perfectly spherical object is equivalent to that of a point. In other words, if you pretend that the Earth is spherically symmetric (which is a really good approximation), then, if you want to know the net gravitational effect that comes from this massively complex system made up of about 10^{53} elementary particles–each one with its own mass creating its own gravitational field–it suffices to consider the gravitational effect of a single particle. (Admittedly, you need to consider a single particle that weighs 6,000,000,000,000,000,000,000,000 kilograms.) In other words, the gravitational field is simply given by \frac{k}{r^2}, where k is a constant and r is the distance from the center of the Earth. (Extending this model to include points within the Earth is easy as well.)

This idea is enormously powerful. It takes a problem that our most powerful computers couldn’t even contemplate and converts it cleanly into a problem that everyone solves as a freshman in high school. Indeed, physicists are so enamored with spherical approximations that they get mocked regularly for it.

So, to act like a caricature of a theoretical physicist for a minute, let’s pretend that the Earth is indeed perfectly spherically symmetric and that it’s the only object in the universe. And, say we only care about gravity in this world. In this fabled universe, it’s not too hard to imagine building a computer that perfectly represents the effects of gravity everywhere in the universe. A user of this computer could enter coordinates and a desired level of accuracy and learn the strength and direction of the gravitational field at those coordinates within the requested level of accuracy. It is even conceivable that this computer could itself be a sphere of uniform density, centered around the center of the earth, so that the computer could easily consider its own gravitational effects as well. (Or, the density of the material from which the computer is constructed at a given distance from the Earth’s center could be the same as all other matter at that distance. E.g., the computer could be as dense as rock and inside the Earth or as dense as air and in the atmosphere.)

Continue reading →

Consequences of the Halting Problem: Gödel’s First Incompleteness Theorem

Leave a reply

In my first post on this blog, I defined and proved my favorite fact: The halting problem is undecidable. You should probably read that post if you don’t know what that means, but in brief, it means that it is impossible to write a computer program that will always correctly tell you whether any given computer program will run forever or eventually stop.

I promised to talk about some of the far-reaching consequences of this fact in future posts, and here I am keeping my promise, if a little late. (Don’t get used to me keeping my promises on this blog, though…) I’ll start with arguably the biggest consequence of the halting problem’s undecidability: Gödel’s First Incompleteness Theorem.

As is my m.o., I’ll try to keep the discussion accessible to laypeople; I’ll provide lots of context; and I’ll just generally be extremely long-winded.

This post will be even more long-winded than usual because I feel the need to provide way too much context. To sort of acknowledge that this post is absurdly long, I’ve put a little (*) in the heading of sections that are less tangential. I’m incredibly biased, of course, but I suggest attempting to make it through the whole thing, and if you get tired somewhere around Euclid or Cantor, skip ahead to the next asterisk.

Continue reading →

A Simple Vulnerability Found in… Lots of Stuff

1 Reply

(Since this blog is read by a lot of poker players, it’s probably a good idea to mention right away that I don’t know of any way that this vulnerability could affect poker client software.)

My friend Thomas Bakker recently showed me an amazing (and hour-long) video from the recent Chaos Communication Congress, which is essentially a conference in which various hackers get together and laugh at the current state of computer security implementations. These types of things are very helpful for people trying to improve security, but of course, they’re also absolutely terrifying. Most of the scary stuff discusses specific vulnerabilities that are unique to a device or piece of software. (Here, for example, is a short video showing a man-in-the-middle attack that works against every iPhone 3G.)

Those things are freaky enough. However, Alexander Klink and Julian Wälde (a penetration tester and a student respectively) demonstrated a much much more general attack. Instead of targeting the specific security implementations of one particular piece of software or device, their attack targets the programming languages that almost all major websites use: PHP, Java, ASP.NET, and Python amongst others. Basically every modern website on the internet uses these, including, for example, Facebook, Twitter, Two Plus Two, Subject: Poker, the New York Times website, YouTube, this blog, Wikipedia, Gmail, whitehouse.gov, and cia.gov.
Continue reading →

My Favorite Fact: The Halting Problem

9 Replies

I figure the first topic on my blog should be my favorite. It concerns a question that is fundamental to computer science theory called the halting problem. It’s really not a fact about computers or computer programs at all; it’s just best formulated in that way. It was first solved in 1936 by Alan Turing, and one can argue that the basic question goes back at least to David Hilbert’s 23 problems in 1900 (although Hilbert initially assumed something that was false in his question). It was introduced to me by Professor Eugene Charniak a few years ago in his class on models of computation, and it’s a relatively standard problem that undergrads in computer science learn about at some point.

Most importantly, it’s really beautiful.

I’ll introduce the problem and prove the solution in this post. In a future post, I’ll discuss the wide-ranging consequences.

Continue reading →

Hi

2 Replies

There are a number of nerdy subjects that I’ve wanted to write about for a long time, but I haven’t really had the right venue for it. My poker blog occasionally strays from poker. But, it’s probably not fair to the people who come there to read about poker to do that too often, so I save it for things that I feel a strong moral compulsion to discuss.

So, I created a new venue.

This blog will be standard fare–If I have a thought about something other than poker and feel like writing about it, I’ll probably write about it here. (I’ll still maintain my poker blog in the sense that I won’t rule out writing future posts for it–I’ve even got some in mind—but, as a blogger with a history of breaking promises to his readers, I ain’t makin’ no more of those right now.)

Topics of interest include virtually anything nerdy, with a specialization in computer science theory. (I’m currently waiting to hear back from PhD programs in that field.) I assume that my readership will start out as roughly the nerdier 10% of the people who read Subject: Poker or my other blog, most of whom don’t have formal math training. So, for now at least, I’ll try to keep the content accessible to laypeople.

If that’s the sort of stuff you might want to read, you should subscribe to my RSS or follow me on Twitter.

Continue reading →