Grad student colloquium

I gave a talk in the grad student colloquium about Chaitin's constant. I was afraid of running out of material, but I actually ran out of time. It was similar to my honors association talk, but for a math audience. The main points were:

• Intro: an "IT" proof that there are infinitely many primes.
• I call a computer program or data "compressible" if there's a shorter program that does the same thing. I think of incompressible program as "static".
• There's no program that can reliably detect incompressibility. Slogan: "static is undetectable"
• There's not even a good program to occasionally detect incompressibility. Any such program only detects finitely many incompressible programs (roughly, those that are not too much larger than it).
• Chaitin's constant is the probability that a random program is incompressible. It is a non-computable real number.
• Theorems of Cantor, Turing, and Godel are corollaries.

USC

I gave a talk at the Joint LA Topology Seminar in USC. First I talked Yin Tian, a student of Ko Honda, who was interested in my work, and categorifying it, and maybe relating it to contact structures. I also got to meet Aaron Lauda, and see some people I know like Heather Russell and Francis Bonahon. My actual talk felt a bit self-conscious and amateurish to me, but it seemed to go over okay. Here is the abstract.

The Joint Los Angeles Topology Seminar

@ USC

Stephen Bigelow (UC Santa Barbara): Diagrammatic invariants of tangles
I will mainly talk about the Alexander polynomial. There is a way to compute the Alexander polynomial of a knot diagram by resolving crossings into linear combinations of diagrams that have no crossings, but perhaps some "dead-ends". This works just as well to give an invariant that sends a tangle to a linear combination of simple diagrams that are easy to work with. I will explain this, the colored Alexander polynomial, and prospects for the Jones and HOMFLY polynomials.

the importance of units

Snowmass village
established 1967
elevation 8388
population 1866
total 12,221

From:


http://media.rd.com/rd/images/rdc/slideshows/16-silly-signs/snowmass-colorado-af.jpg

Honors association lecture on data compression

I gave an "honors association lecture". I think it went pretty well. There were about a dozen honors students in the audience. Below is the html I used, for what it's worth - most of the content was me talking.

Preparing for the talk really got me thinking, especially the question "is the universe compressible?". That is, can it be completely described by a smaller "theory of everything"? Randomness and arbitrary precision real numbers would be "non-compressible" parts of such a theory. I used to think the universe must be completely described by a simple combinatorial theory with no randomness or real numbers. Now I realize that this amounts to a blind faith that the universe must be compressible. How small do I think it "must" compress, and why? 

Data compression & the meaning of life

I want to talk about data compression, but more philosophical speculation than technical details. Most of this is from the book "Meta-math!" by Gregory Chaitin.
Last century there was a revolution in how we think about mathematics, that is still playing out today. Some big names:

• Cantor (1845-1918): some infinities are bigger than others.
• Gödel (1906-1978): some mathematical truths are unprovable.
• Turing (1912-1954): some functions are uncomputable.

Their proofs are long and difficult because they first had to invent computer science. It's easier now that computers are familiar to most of us.

What you need to know about computers

They do everything in binary. Sequences of 0s and 1s can represent:

• numbers,
• text,
• pictures,
• music,
• videos,
• games,
• apps.

These are all files.
I don't care about time.
(Imagine you have an extremely fast computer and are extremely patient.)
I do care about space...

Compression

Encode a computer file into one that takes less memory.

• Lossy (mp3, jpeg).
• Lossless (zip).
• Self extracting (stuffit, rar, my old Amiga).

I'm interested in lossless self-extracting compression. It's possible because most files have a lot of redundancy ("red pixel, red pixel, red pixel, [100 times]").
Question: Is every computer file compressible?


-------------- spoiler alert --------------


Answer: No.

Question: Could we write a program to determine which computer files are compressible?


-------------- spoiler alert --------------


Answer: No.

Question: What percentage of computer files are compressible?
(Repeatedly roll dice with options: 0, 1, STOP. What's the chance you get something compressible?)


-------------- spoiler alert --------------


Answer: Nobody will ever know.
The same limitations apply to anything that is Turing equivalent. That means both:

• simple enough that a computer can simulate it, and
• complicated enough that it can simulate a computer.

Turing completeness is everywhere.

• Mathematical theorems.
• Solving polynomial equations.
• Cellular automata (Conway's game of life, Wolfram's rule 110).
• minecraft.

Questions

• If the answer to a question is unknowable, does it really exist?
• Should we be worried that mathematics might be inconsistent?
• Are humans Turing equivalent? (In theory? In practice?)
• Is the universe compressible? (That's the goal of quantum mechanics.)
• What's the meaning of life?

Adventures installing Linux 3

By the way, I see I got some actual page views for my last two posts! I treat this blog like a private notepad that I just leave lying around in public for no particular reason. So it's nice if somebody actually picked it up and maybe even found something useful in it.

The story so far: In the first episode, I got on the internet. In the second episode, I got on the internet again. In this third and probably final episode, I get the desktop environment working to the point where I'm ready to actually use it, to, you know, do my job and stuff.

The first problem was that KDE would crash part way through its loading screen. I have found three solutions. In order from very easy to easy:

• Use startxfce4 instead of startx.
• Use xwmconfig to change the default from KDE to, say, XFCE.
  
• Create a file /usr/share/X11/xorg.conf.d/composite.conf (or anything.conf) consisting of the text:
  
  Section "Extensions"
  Option "Composite" "Disable"
  EndSection

The next problem was that the touchpad mouse did not work. My ultimate solution was to buy a small inexpensive wireless mouse, which worked like magic straight out of the box. However I did learn a few things before I gave up.

Many websites advised me to edit a file xorg.conf in various ways. It confused me that I had no xorg.conf, but had xorg.conf-vesa, and a directory xorg.conf.d. The new way to configure xorg is to store them in files that end in .conf in the directory x. I suppose that's to make it easier to keep them organized. However xorg.conf still works, and so does some other old way of doing things involving something called "hal". As far as I can tell, xorg.conf-vesa does nothing.

The mouse data comes in through the file /dev/input/mice. If I "cat" this now it spits out random looking junk when I move my mouse, which is fun. Also, "cat /dev/input/mouse0" does the same thing. For some reason, I also have a file /dev/input/mouse1 that does nothing. Before I bought a new mouse I had no mouse0 or mouse1, and "cat /dev/input/mice" was dead silent.

Good places to look for error messages are the file /var/log/Xorg.0.log and the command dmesg. At first, dmesg showed me a lot of error messages about the mouse losing sync. Later, the mouse completely froze, never to move again, even after a reinstall (very weird). After running "rmmod psmouse" and "modprobe psmouse", dmesg revealed that it had tried and failed to install a "Generic PS/2" mouse. This might indicate a kernel bug, according to this thread about a similar problem.

There's a kernel patch, and installing it doesn't look all that difficult. However it seemed a bit drastic, and not guaranteed to work. This is when I gave up and bought a wireless mouse.

So now my cute little laptop is fully functional. At times I thought the whole experience was the most annoying waste off time ever, but in the glow of success it looks like an adventurous learning experience. Using the laptop is so much more fun now that I have some idea of what it's doing behind the scenes.

In between banging my head against Linux to make it work, I've been thinking about the political ideals it represents. It felt like a minor act of rebellion to buy a laptop and immediately delete Windows. Yeah, I know, after I'd already paid for it - I'm sure Bill Gates was devastated. Still, on a personal political level, it felt good. My Macbook "just works", but it was starting to bother me that I had no idea how it just worked, or to what extent it was working against me.

On the other hand "it just works" describes how I relate to almost everything - the microchips in my precious Linux laptop, every device I own, my body, the earth's climate, ... . I don't know why operating systems in particular suddenly started to bother me. Maybe after some time to get my thoughts straight I'll have some better idea.

Adventures installing Linux 2

I got frustrated trying to get the touchpad to work, so decided to re-install Slackware and start again from scratch. This time I tried to keep track of everything I changed to get wifi to work. This is for my own benefit, but maybe someone else will find it useful. If that's you, note that I'm installing Slackware 13.37 on an LT4004u computer with a BCM4313 802.11 b/g/n wifi chip, and I don't know what I'm doing. Here's what I did:

1. Put bcm43xx-0.fw and bcm43xx_hdr-0.fw in /lib/firmware/brcm
2. Added "blacklist ipv6" to /etc/modprobe.d/blacklist.conf
3. Changed /etc/rc.d/rc.inet1.conf to:
   DEBUG_ETH_UP="no"
   IFNAME[4]="wlan0"
   USE_DHCP[4]="yes"
   WLAN_ESSID[4]="[my computer's essid]"
   WLAN_WPADRIVER[4]="wext"
   WLAN_WPACONF[4]="/etc/wpa_supplicant.conf"
4. Changed /etc/wpa_supplicant.conf to:
   network={
     ssid="[my home's wireless]"
     psk="[my home's password]"
   }
5. Deleted wpa_supplicant.conf (this step is probably not important, but alien bob said it's okay)

It doesn't start on boot. Surely that should be easy to fix. In the meantime, I type:

wpa_supplicant -B -Dwext -iwlan0 -c/etc/wpa_supplicant.conf

dhcpcd wlan0

[Update: Indeed, just put the above two lines into "/etc/rc.d/rc.local".]

I added a network to wpa_supplicant with "key_mgmt=NONE", and now it works on campus and at most coffee shops. The "coffee bean and tea leaf" has a regularly changing password on a TV screen. I wonder if I'd have to edit wpa_supplicant every time, or if  there's way to do it from the command line, maybe as an option to iw. [Update: yes, of course, it's "iwconfig wlan0 essid Coffee-Bean-or-whatever key s:stupid-code-on-the-screen"].

Adventures installing Linux 1

I bought a Gateway LT4004u netbook, erased Windows, and installed the
Slackware distribution of Linux. Slackware is for people who either know what
they're doing, or are masochists. I do not know what I'm doing. However I
somehow seem to have it mostly working.

Actual installation was easy, once I gave in and bought an external CD
drive. In the network configuration, a couple of questions confused me:
The hostname and domain name are anything you want. The hostname is the
ESSID, which comes in handy later.

The hard part was getting on to the internet. Linux is free and open source,
and the wifi chip is made by a corporation that loves money and secrecy, so
it's not surprising that it is hard to get them to talk to each other. The go-between
is a "driver", which was reverse engineered by very smart and generous people
using leaked information and all sorts of legal shenanigans.

First I had to figure out what chip I have. The way to do that is with the command
lspci -vnn
which I learned from
linuxwireless.org/en/users/Drivers/b43
 It turns out I have a Broadcom BCM4313 802.11b/g/n chip,
and for some reason [14e4:4272] is important.

(By the way, the worst way to find out what chip you have is to pull the laptop apart
and look inside. The laptop opens by lifting the keyboard, not by pulling off the back.
In the process, I broke some fragile plastic latches, voided the warranty, and saw
nothing I could understand.)


Broadcom provides their own driver for download, but it seemed to only
cause problems, and I ended up deleting it. Instead I took advice from
althafkbacker.blogspot.com
to download the files:
brcm_bcm43xx-0.fw
brcm_bcm43xx_hdr-0.fw
and put them in /lib/firmware/brcm/. There was no such directory, so I created it.
Later I realized the "brcm_"s should be deleted from the names, which I
discovered by putting
DEBUG_ETH_UP = "no"
in
/etc/rc.d/rc.inet1.conf
and then reading error messages from
dmesg

I also set /etc/rc.d/rc.inet1.conf so that wlan0 would use DHCP. Some
apparently important lines:
WLAN_ESSID[4]=[my hostname]
WLAN_WPADRIVER[4]="wext"
WLAN_WPACONF[4]="/etc/wpa_supplicant.conf"

Which brings me to the other important configuration file:
/etc/wpa_supplicant.conf
I ended up copying this to a backup and replacing it with the super-short:

network={
ssid="[name of my home wireless network]"
psk="[password for my home wireless network]"
}

I found instructions online to create a psk using
wpa_passphrase [hostname] [my secret passphrase]
but that did not seem to work. I spent a long time wondering when I'd get
to enter my secret passphrase or the password for my network. Maybe my
secret passphrase is for people to log in to my computer? Anyway, I did not
end up using this psk at all.

Here are some random commands that I don't fully understand, but seem useful:
ip link set wlan0 up
seems to be the same as
ifconfig wlan0 up
To restart, I think you do:
killall -SIGHUP wpa_supplicant
To start and stop modules, or whatever, I think you do:

rmmod, and modprobe

Special praise is due to Alien Bob, whose online advice was incredibly
clear and helpful.

So now I have finally got it to log in to the internet whenever I boot it up
at home. And I feel like I earned it. Hooray! I guess I'll have to edit
wpa_supplicant every time I log on somewhere else. I don't know what I
did, or how I would do it again, but maybe this post will help.

The next challenge was getting startx to work. The still-unsolved challenge
is to prevent the mouse from constantly freezing up. Maybe I'll post about those later.