{"id":726,"date":"2008-12-31T08:53:39","date_gmt":"2008-12-31T08:53:39","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2008\/12\/31\/my-favorite-strange-number-classic-repost\/"},"modified":"2008-12-31T08:53:39","modified_gmt":"2008-12-31T08:53:39","slug":"my-favorite-strange-number-classic-repost","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2008\/12\/31\/my-favorite-strange-number-classic-repost\/","title":{"rendered":"My Favorite Strange Number: Ω (classic repost)"},"content":{"rendered":"

I’m away on vacation this week, taking my kids to Disney World. Since I’m not likely to
\nhave time to write while I’m away, I’m taking the opportunity to re-run an old classic series
\nof posts on numbers, which were first posted in the summer of 2006. These posts are mildly
\nrevised.<\/em><\/p>\n

Ω 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<\/em> computable. It’s just all around awfully cool. <\/p>\n

<\/p>\n

So. What is it Ω?<\/p>\n

It’s sometimes called the halting probability<\/em>. The idea of it is that it encodes the probability<\/em> that a given infinitely long random bit string contains a prefix that represents a halting program.<\/p>\n

It’s a strange notion, and I’m going to take a few paragraphs to try to elaborate on what that means, before I go into detail about how the number is generated, and what sorts of bizarre properties it has.<\/p>\n

Remember that in the theory of computation, one of the most fundamental results is the non-computability of the halting problem<\/em>. The halting problem is the question “Given a program P and input I, if I run P on I, will it ever stop?” You cannot write a program that reads an arbitrary P and I and gives you the answer to the halting problem. It’s impossible. And what’s more, the statement that the halting problem is not computable is actually equivalent<\/em> to the fundamental statement of Gödel’s incompleteness theorem.<\/p>\n

Ω is something related to the halting problem, but stranger. The fundamental question of Ω is: if you hand me a string of 0s and 1s, and I’m allowed to look at it one bit at a time, what’s the probability that eventually<\/em> the part that I’ve seen will be a program that eventually stops?<\/p>\n

When you look at this definition, your reaction should<\/em> be “Huh? Who cares?”<\/p>\n

The catch is that this number – this probability – is a number which is easy to define; it’s not computable; it’s completely uncompressible<\/em>; it’s normal<\/em>.<\/p>\n

Let’s take a moment and look at those properties:<\/p>\n

    \n
  1. Non-computable: no program can compute Ω. In fact, beyond a certain value N (which is non-computable!), you cannot compute the value of any bit<\/em> of Ω. <\/li>\n
  2. Uncompressible: there is no way to represent Ω in a non-infinite way; in fact, there is no way to represent any substring<\/em> of Ω in less bits than there are in that substring.<\/li>\n
  3. Normal: the digits of Ω are completely random and unpatterned; the value of and digit in Ω is equally likely to be a zero or a one; any selected pair<\/em> of digits is equally likely to be any of the 4 possibilities 00, 01, 10, 100; and so on.<\/li>\n<\/ol>\n

    So, now we know a little bit about why Ω is so strange, but we still haven’t really defined it precisely. What is Ω? How does it get these bizarre properties?<\/p>\n

    Well, as I said at the beginning, Ω isn’t a single number; it’s a family of numbers. The value of an<\/em> Ω is based on two things: an effective (that is, turing equivalent) computing device; and a prefix-free encoding of programs for that computing device as strings of bits.<\/p>\n

    (The prefix-free bit is important, and it’s also probably not familiar to most people, so let’s take a moment to define it. A prefix-free encoding is an encoding where for any given string which is valid in the encoding, no prefix<\/em> of that string is a valid string in the encoding. If you’re familiar with data compression, Huffman codes are a common example of a prefix-free encoding.)<\/p>\n

    So let’s assume we have a computing device, which we’ll call φ. We’ll write the result of running φ on a program encoding as the binary number p as &phi(p). And let’s assume that we’ve set up φ so that it only accepts programs in a prefix-free encoding, which we’ll call ε; and the set of programs coded in ε, we’ll call Ε; and we’ll write φ(p)↓ to mean φ(p) halts. Then we can define Ω as:<\/p>\n

    Ωφ,ε<\/sub> = Σ<\/b>p ∈ Ε|p↓<\/sub> 2-len(p)<\/sup><\/p>\n

    So: for each program in our prefix-free encoding, if it halts, we add<\/em> 2-length(p)<\/sup> to Ω. <\/p>\n

    Ω is an incredibly odd number. As I said before, it’s random, uncompressible, and has a fully normal distribution of digits. But where it gets fascinatingly strange is when you start considering its computability properties.<\/p>\n

    Ω is definable<\/em>. We can (and have) provided a specific, precise definition of it. We’ve even described a procedure<\/em> by which you can conceptually generate it. But despite that, it’s deeply<\/em> uncomputable. There are procedures where we can compute a finite prefix of it. But there’s a limit: there’s a point beyond which we cannot compute any<\/em> digits of it. And<\/em> there is no way to compute that point. So, for example, there’s a very interesting paper where the authors
    \ncomputed the value of Ω for a Minsky machine<\/a>; they were able to compute 84 bits of it; but the last 20 are unreliable<\/em>, because it’s uncertain whether or not they’re actually beyond the limit, and so they may be wrong. But we can’t tell!<\/p>\n

    What does Ω mean? It’s actually something quite meaningful. It’s a number that encodes some of the very deepest information about what<\/em> it’s possible to compute. It gives a way to measure the probability of computability. In a very real sense, it represents the overall nature and structure of computability in terms of a discrete probability.<\/p>\n

    Ω is actually even the basis of a halting oracle – that is, if you knew the
    \nvalue of Ω, then you could easily write a program which solves the halting problem!<\/p>\n

    Ω is also an amazingly dense container of information – as an infinitely long number and so thoroughly non-compressible, it contains an unmeasurable quantity of information. And we can’t even figure out what most of it is!<\/p>\n","protected":false},"excerpt":{"rendered":"

    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 revised. Ω is my […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[13,79,43],"tags":[],"class_list":["post-726","post","type-post","status-publish","format-standard","hentry","category-classics","category-computation","category-numbers"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-bI","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/726","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=726"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/726\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=726"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=726"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=726"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}