31 Mar 2010

I was inspired by an item in Luke's Tumblr blog last night. It was a screenshot of a program called PawSense, which monitors a computer's keyboard for cat activity. (I don't know if it's any good, but it's funny.) As anyone with cats knows, it's not unusual to leave a computer only to come back later to see garbage typed in by a wandering cat. I wrote a version for Emacs today.

git clone http://git.nullprogram.com/cat-safe.git

Or you can download a snapshot: cat-safe-master.tar.gz.

Put it (cat-safe.el) somewhere in your load-path (like ~/.emacs.d/) and put this line in your .emacs file,

(require 'cat-safe)

This only monitors Emacs itself; it should help protect your buffers but not your web browser. When cat interference is detected Emacs switches focus to a junk buffer and lets the cat make a mess there instead. In case your cat happens to type out some Shakespeare you will be able to read it in the junk buffer. Just kill the junk buffer to return to work.

It could still use some improvement. Right now it looks for a single key being help down, excepting keys humans tend to hold down like backspace, delete, and space. If you play around with it you'll notice if you press several keys at once Emacs will sometimes create a pattern with them. I need to figure out a good way to detect this.

I'm going to run it at home for awhile to make sure it remains transparent, but still does its job. It will probably incur a performance penalty on frequently repeated keyboard macros.

09 Mar 2010

Fractran is a Turing-complete esoteric programming language. A Fractran program is just an ordered list of positive, irreducible fractions. The program's output for an input n is the output of the program run on n multiplied by the first fraction in the list that results in an integer. If no such multiplication results in an integer, the output is the input n. Variables are encoded in the exponents of the prime factorization of the input and output.

Some time ago I thought up an idea for a short story involving Fractran. A mathematician accidentally creates a Fractran program that can trivially factor large composites. Think something like O(log n). It's just the right magical string of, say, 31 fractions.

The story would be a first-person narrative of the mathematician's thoughts during a short time after the discovery, considering many of the consequences of the program. For example, it would render much of cryptography, which plays an essential role in the modern world, useless. He would also wonder if mankind should deserve such a discovery, considering how accidental it was.

This whole idea vanished once I realized that this Fractran program is actually completely trivial. It even runs in O(1) time. It's so trivial as to be worthless. Remember that Fractran stores its data in the number's prime factorization? The Fractran program that can factor any number in constant time is the identity function. To decode the output, which matches the input, all you need to do is factor it!

Interestingly, it doesn't seem to actually be possible to implement the identity function in Fractran (But somehow it's Turing-complete? Hmmm... more investigation needed.), unless you can define your program in terms of its input. For example, the program 1/(n+1) is the identity function for input n.