haggai's New Writeups

Chaitin's constant (thing)

2005-10-29T13:15:38Z

Gregory Chaitin gave this as an example of a definable number, which is not computable; so you can describe a number which you will never be able to calculate... The obvious (and in a sense only) way to do this is to make the number's definition talk about the halting problem.

The number Ω is loosely defined as the probability of a randomly-generated Turing Machine (with input) ever halting. To make this precise, we pick a binary prefix-free encoding of all pairs of (syntactically) valid Turing Machines and inputs; this is not hard to do, just not very interesting. Equivalently, we consider all (binary encoded) programs for a Universal Turing Machine. We now pick successive bits with even probability, until we get a valid machine and input pair. If there are invalid strings in our representation, we just force the value whenever one choice would leave us with no valid continuation, but really we could just remove them from our encoding.…

definable number (idea)

2005-10-29T12:26:01Z

A (real) number x is called a (first-order logic) (real) definable number if it is the only real number satisfying a first-order logic formula f, which has one free variable. Really, this means all the numbers you could specify exactly (by describing what equations etc. hold for them). Numbers are also sometimes called "definable" according to other logical languages.

All the algebraic numbers are trivially definable, but so is every other mathematical constant and number you've bumped into. This should come as no surprise: we've pretty much included every number which mathematics can "call by name" (in the sense of unambiguously singling out a specific number). On the other hand, definable numbers must be countably infinite, as they may easily be Godel numbered (each one is described by a finite logical formula).

So where do all the other real numbers come from? Where else? From the Axiom of Choice (or one of its friends). If…

computable number (idea)

2005-10-29T01:40:59Z

We call a real number x computable, if it may be described by a Turing machine T, in the sense that when T is input a number n, it outputs the first n digits (say decimal, or whatever you like) of x. Equivalently (and more conveniently, perhaps), there is a (non-halting) algorithm which prints out the digits of x. Computable numbers are also called recursive numbers (when defined through recursive functions rather than TMs) or effectively definable (as distinct from definable numbers, of which there are many more). This definition requires what seem to be more "elementary" tools than a rigorous definition of the real numbers.

Let's think about that definition. The integers are obviously computable. So are the rationals (just fire up a long division algorithm). The square root of 17 is, too, along with sin(e^-2.1): any old approximation method shows this. It's a hop and a skip to deciding that all algebraic numbers are computable,…

A Classical Introduction to Modern Number Theory (thing)

2005-10-29T00:50:05Z

A great introduction to (surprise!) modern Number Theory, by Kenneth Ireland and Michael Rosen, and published in Springer-Verlag's outstanding Graduate Texts in Mathematics. It is the textbook of choice for many basic number theory courses. It is commonly referred to as "Ireland and Rosen", as you are expected to know all about it (and the title is just too long and unspecial)...

The book assumes the reader to have some familiarity with abstract algebra, and is probably appropriate for an advanced undergraduate course, or a basic graduate one. It starts from absolute basics (e.g. unique factorization) and goes on to give a fair idea (anyway, to the extent I can follow) of most basic topics and some of what number theorists get to do nowadays. Given some prior knowledge, it makes for good reading, and there is a fair amount of exercises to make sure you're following and introduce a few further concepts. There is some attempt to put things in historical perspective, e.g.…

tabbed browsing (idea)

2005-10-28T23:43:44Z

One of the great things about Firefox is tabbed browsing. Tabbed browsing is not limited to Firefox, but is primarily a Mozillaesque thing, and I will be ignoring other browsers in what follows.

Tabbed browsing comes out of the box in Firefox, complete with numerous options, but many extra features for tabs are available through extensions. Many features of tabbed browsing (and other favourites) have been popularised in extensions and then added to the base code. These extensions are quite popular, so some of what I describe here and is "extension only" will probably be standard in a close release. You can use the browser without ever using tabs -- just separate browser windows -- but you'll be missing out on a whole lot of fun.

Tabs are one of a few MDI looks. Historically, most MDIs have been awful, but this is one that really works. Basically, a single browser window may "contain" several different webpages (or any other browsable goodies).…

juice stall (thing)

2005-10-28T20:49:53Z

The best place for a refreshing drink in an Israeli city will almost invariably be a small, cheap juice stall. These have been a classic for years now, chiefly serving orange and carrot juice, but in recent years the fad has really taken off (of course following Tel Aviv's fashionable lead), fuelled by the Israeli's love of multiple choice and combinations. They're a great refreshment pit stop on a hot day.

A juice stall may be an actual rickety stall or hole in the wall, perhaps around the local market or commercial district, or tucked away with the corner shops in a residential neighbourhood. Flashier, more upmarket places might be at shopping malls (no food court is complete without somewhere to get fresh squeezed juice), or proper walk-in places or storefronts along a main street, possibly also selling ice cream and such. Lastly, many grocers and other small shops will set up a small extra counter, especially in summer, to squeeze and serve juice. In…