Back when I was a student working on my PhD, I specialized in programming languages. Lucky for me I did it a long time ago! According to Wired, if I…
Types Gone Wild! SKI at Compile-Time
Over the weekend, a couple of my Foursquare coworkers and I were chatting on twitter, and one of my smartest coworkers, a great guy named Jorge Ortiz, pointed out that…
Static Typing: Give me a break!
I'm a software engineer. I write code for a living. I'm also a programming language junkie. I love programming languages. I'm obsessed with programming languages. I've taught myself more programming…
Turing Crackpottery!
One of the long-time cranks who’s commented on this blog is a bozo who goes by the name “Vorlath”. Vorlath is a hard-core Cantor crank, and so he usually shows up to rant whenever the subject of Cantor comes up. But last week, while I was busy dealing with the Scientopia site hosting trouble, a reader sent me a link to a piece Vorlath wrote about the Halting problem. Apparently, he doesn’t like that proof either.
Personally, the proof that the halting problem is unsolvable is one of my all-time favorite mathematical proofs. It’s incredibly simple – just a couple of steps. It’s very concrete – the key to the proof is a program that you can actually write, easily, in a couple of lines of code in a scripting language. And best of all, it’s incredibly profound – it proves something very similar to Gödel’s incompleteness theorem. It’s wonderful.
To show you how simple it is, I’m going to walk you through it – in all of its technical details.
Return of the Revenge of the Return of the Compression Schmuck
Well, folks, this one is going to be boring for most of you. But the
compression jackass, Jules “Julie-baby-dumbass” Gilbert has been repeatedly
bugging me. And today, he replied to my latest “fuck off and stop sending me
mail” with a long-winded proselytizing response in which he requested that I
be courteous and not publicize the discussion of his “work”.
Fuck that
The entire correspondence is below.
Before I get to it: the short summary of what Jules is doing
is munging a file in a way that makes it amenable to recompression. In
the classic sense, this is removing a trivial bit of information from the
file, which thus allows is to be re-compressed just a tiny bit
more.
The catch is, of course, you can’t un-compress it without re-introducing
the information that you removed. In his case, you need to repeatedly
un-compress, un-munge, un-compress, un-munge, and so on –
exactly the right number of times. From some of his emails, he
does this hundreds to thousands of times.
You can’t un-compress his stuff without knowing how many times the compressor
ran. And how many times is that? Well, gosh, to know that, you need to know
some extra information. Anyone want to take a bet on what the
relationship is between the amount of additional compression he can get, and
the number of repetitions of his system? Anyone?
Ok. On to the transcript.
Revenge of the Return of the Compression Idiot
Do I really need to go through this again? Argh!
As long-time readers will remember, a while back, I had an encounter with
a crackpot named Jules Gilbert who claimed to be able to cyclically compress
files. That is, he could take a particular input file, compress it, do
something to it, and then compress it again, making it smaller. He claimed to
be able to do this for any input.
And to make it more annoying, his claim to be able to do this brilliant
magical cyclical compression was attached to an obnoxious christian “I want to
save you soul” rant, where he effectively offered to share the profits from
this brilliant invention with me, if I’d only give him the chance to tell me
about Jesus.
I tried to get rid of the schmuck. I asked him to leave me alone politely.
Then I asked him to leave me alone not-so politely. Then I asked him to
leave me alone very, very rudely. Then I publicly mocked him on this blog.
After the last, he finally seemed to take the hint and go away.
Unfortunately, good things often don’t last. And yesterday, I received
another new message from him, bragging about the results of his uber-magical
compression system. He has now perfected it to the point where he can take
any input file, and compress it down to about 50K:
I am now compressing single bit as:
I use C code to pack up one bit to a byte and call bzip2’s compress
buffer.I print the result and compute the size.
(I did this for both gzip and bzip2.) Gzip didn’t compress; it gave
me back about 6.25, but I needed at least 8.0.And bzip2 gave it to me. About 8.2 and higher. (This is with no
actual I/O, just buffer to buffer.)This was with random data. At least that’s what people call it.
Bzip2 data. (It looks pretty random to me.)I expect to show up at a friend’s house and show him the system on
Monday. THIS IS NOT A COMPLETE SYSTEM, but it’s not just research
either. The input was randomly chosen (not by me, by a C function,)
and the program has been arranged to simply open another file when a
current file is exhausted.Every input file has been compressed once with bzip2. Each input file
is at least 5k bytes and was chosen with the intent to represent all
popular OS’s somewhat equally.This program is easily able to process MN’s 415k file. And since it
uses 256 byte blocks, I can bring it down to about 50k (number
demonstrated in testing.) Another way to say this is that (with this
program,) all files greater than about 50k can be made that small.This is the simplist system I have ever made that uses my “modern”
techniques (I mean, not my LSQ ideas of a decade ago.) i started
coding it this morning, to see if a certain idea worked…I’m trying to drop bzip but it’s pretty good! I’m also trying to
modulate my input to it, in order to obtain a gain from the pattern
recognition (the BWT may not be an actual FFT but it’s a similar
idea.) If I can do this I will keep it.If all this is greek to you, here’s the thing: Just about every other
computer scientist in the whole wide world believes this is
impossible. Why is this valuable? Because it means that all files
and messages can be compressed in while in transit to, say, 50k —
probably much less. (Or while sitting on a CD-ROM or DVD.)
I love that line in there: “Just about every other computer scientist in
the whole wide world believes this is impossible”.
Jules, baby, belief has nothing to do with it.
Animal Experimentation and Simulation
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.
Dumbass.
Anyway: my actual argument is below the fold.
The Return of the Compression Idiot
Remember a while back, I wrote about a crackpot who pestered me both about
converting to Christianity, and his wonderful, miraculous compression system? He
claimed to be able to repeatedly compress any file, making it smaller each time.
Well, he’s back pestering me again. Repeatedly asking him to leave me alone,
shouting at him, etc., hasn’t worked. (His current claim is that he doesn’t know how
to delete me from his gmail contacts list.) So I’m resorting to another round of
public humiliation, which I hope will be informative and entertaining as well.
I Get Mail: Iterative Compression
Like a lot of other bloggers, I often get annoying email from people. This week, I’ve been dealing with a particularly annoying jerk, who’s been bothering me for multiple reasons. First, he wants me to “lay off” the Christians (because if I don’t, God’s gonna get me). Second, he wants to convince me to become a Christian. And third, he wants to sell me on his brilliant new compression scheme.
See, aside from the religious stuff, he’s a technical visionary. He’s invented a method where he can take a source document, and repeatedly compress it, making it smaller each time.
This is a stupid idea that I’ve seen entirely too many times. But instead of just making fun of it, I thought it would be interesting to explain in detail why it doesn’t work. It touches on a bunch of basic facts about how data compression works, and provides a nice excuse for me to write a bit about compression.
The basic idea of data compression is that you’re eliminating redundancies in the original text. You can’t discard information. Mathematically, a compression function is an invertible function C from an array of characters to an array of characters (or you could use bits if you prefer), such that if y=C(x), then on the average input, the length of y is smaller than the length of x.
An ideal compression system is one where for all possible values of x, C(x) is shorter than x. C is your compressor; and since C is reversible, it has a unique inverse function C-1 such that C-1(C(x)) = x. An illustration of this basic compression system is in the diagram to the side.
The Z2K9 Problem
I’ve been getting a lot of emails asking about the so-called “Z2K9” problem.
For those who haven’t heard, the software on a particular model of Microsoft’s Zune music player froze up on New Year’s eve, because of a bug. Apparently, they didn’t
handle the fact that a leap year has 366 days – so on the 366th day of 2008, they froze up for the day, and couldn’t even finish booting.
Lots of people want to know why on earth the player would freeze up over something like this. There was no problem with the date February 29th. There was nothing wrong with the date December 31st 2009. Why would they even be counting the days of the year, much less being so sensitive to them that they could crash the entire device for a full day?
The answer is: I don’t have a damned clue. For the life of me, I can’t figure out
why they would do that. It makes absolutely no sense.
- 1
- 2