Some thoughts on randomness, not structured yet...
| Define | Cryptographic Randomness(type A) | The lack of patterns in a sequence |
| Chaitin Randomness(type B) | The inability to express a sequence in a short program |
You may wish to read up on the latter
Now, sequences that are type A are used all the time, most explictly in cryptography. If I run an RC4 cipher with a random key I can generate megabytes of data will pass type A tests. However, you can certainly code RC4 in less than a megabyte of data on a resonable UTM. And even if you couldn't do it in less than a meg you can just generate more RC4 data. Thus my type A random sequence is not very type B.
Now sequences that aren't type A random almost certainly aren't type B. I don't have anything like a proof for this yet, but it seems sensible. However, I don't think you can ever prove that you have the shortest program that will generate a given sequence without brute-forcing all programs upto that length. I think the proof for that is in this paper, but I need to reread that as I haven't looked at it for ages
So, given the set of all sequences of length n some will be type A and some of those will be type B random (both of those lines are fuzzy, but I don't think that right now matters). Assuming you can find the shortest program that generates each of those sequences you can reinterpret each of those programs as numbers and give each member of the set a number (and thus an order). Some sequences will have shorter numbers than others and if we generated everyu possible program in length order we would expect to see outputs in roughly the same order as our ordered set.
Now, this is where Wolfram's sequences come in. Mathamatica's random function actually runs a rule 30 CA and uses the values of the center line as random data. This gives type A randomness (so he says). However, what he's calling complexity in ANKOS is type A randomness and `his' (pompous twit) `complexity generating' CAs are simply low numbered members of the set of sequences.
Like I said, that was just me writing stuff down to see what I'm thinking
I wonder if we can expect some really fat, high profile, Americans to be defined as enemy combatants and detained without trail now?
Another just links day, though I'm kindof free of exams now
Oh look, linking to this site without permission is prohibited. Oh well - kiss my arse. Wired article (which links to NPR, so is that link banned too?)
Links today today because I'm feeling a little shot (and it's only going to get worse). I have some ideas about Wolfram/cryptographic randomness/chatin randomness which are starting to come into focus but I'm not sure if there's actually anything there yet
I had to write about Creationism today in GS exam (that page could have been useful yesterday - oh well). My hand hurts now after 3 hours of writing. I'm a maths person, I don't do lots of writing! (On the upside I found that I have pretty funky capital letters)
This looks like it might be interesting (read the press release)
Good text on refuting Creationism crap from SciAm. SciAm was one of the offenders who broke links when I checked, but given the URL of this page I'm hoping it's a little more permanent.
Been checking the old archive pages with the W3C link checker. Not too bad, thou it seems that Dilbert and SciAm break their links after a while. It also tells you when you've missed a / on the end of a URL which saves a redirect at least.
The RIPX delay made it on the number two slot on PM (the news show on Radio 4, if you're not British don't worry). That's coverage.
Someone emailed me about Xchat code, which I haven't touched in ages. Seems someone was a little `feature optimistic' with the documentation and so I wrote a patch to bring the code up to what the documented behaviour was. It's weird reading code that I wrote years ago, but it actually made a lot of sense. Reminded me of how much C sucks for a lot of stuff, but at least the code wasn't as bad as I thought it was going to be, considering I must have been about 15 then.
Guess who forgot up actually upload the Syncthread paper. Opps. (Well done to all the people who emailed me about that - that would, erm, be no one despite all the attempts to get it in the logs!)
Stand have announced that the debate over the RIPX order has been delayed until Monday the 24th (not Tuesday the 18th, like /. said - that's when it was going to be). Stand also have a neat little banner ad which is now floated on the top right of IV.
A New Germ Theory [via ESR] about how many conditions (such as cancer, heart disease and even homosexuality) are infectous because, if they were genetic, they would be selected against so strongly as to disappear. Well worth the (quite long) read.
What I said this morning (it's just below this - read it first) is backwards. We don't need a way of marking sections as "this stuff is actually someplace else", we need inlink linking (like <img> tags put content inline). This is nothing new - Ted Nelson told us all this years ago.
Well, there's a Backlink of the Day bar now. It's not really `of the day' as such - I grep them out of the logs by hand but it will do for the moment. Coincidentally, Keith is talking about implimenting backlinks as well today.
The two Google links above show one of the problems at the moment. In one case Google is linking to the text of Fear and Loathing which is fine because that's on a static page. However, the other is linking to a blog entry on the front page which long ago fell off the bottom.
In the Google case you can view the cached version of the IV frontpage, but in the general case the Referer header generated from people clicking links of the frontpage will be http://imperialviolet.org, not http://imperialviolet.org/page4.html#e72. We need some way to tell the browser what the source of a link should be.
Unfortunately, we cannot just add tags or attributes to existing tags without all the validators going nuts. That either leaves trying to get a change through the W3C (ye gods!), overloading some existing operator or hiding it in comments. None of those solutions are much good - anyone have any better ones?
Four entries today and counting. Partly I'm catching up from when IV was down this week but mostly it's because if I start coding anything I know that will be the afternoon gone and I really should revise Biology
This was posted to LtU this week. I've read about 1/4 of the way through, which covers all the basic ideas in J and the builtin operators.
It's a very interresting language and quite cleanly based around the idea of multi-dimentional arrays for everything. However, like most pure languages its range of applications it quite limited and it also suffers from being in the Perl family of function naming. In fact it's worse than perl in that reguard, J is more like K.
However, I do recommend that people read the beginning of the book and grok the concepts of the language about implicit loops.
Keith links to a discussion on A New Kind of Science. Most of the opinions there seem to follow my own quite closly.
Raph and Dave McCusker have been talking a lot about how to design servers recently.
I played around with these ideas a lot during Whiterose development and my views might be a little clouded because Whiterose isn't a typical network server (the Freenet protocol is far more complex than most). During Whiterose development I settled on syncthreading as a good model for managing state. This text gives a good overview of syncthreading (by my definition). It was written as a technical report for Uprizer, but since it says nothing about Uprizer specifically I doubt they have a problem with my making it public
Now, the SEDA people have a good paper with some neat graphs of throughput with threaded and event based models which certainly suggest that no one should consider writing threaded servers if they want it to scale.
However, threaded systems (certainly syncthreaded ones) are event based. They're fundamentally the same thing.
With an event system you loop over your input queue call (be it select, poll, kqueue etc) and, for each event, feed the event into the finite state machine (FSM) for that transaction. The FSM makes some quick, non-blocking, change in its state and returns. Repeat.
The only difference with a threaded model is that the FSM is a stack and some registers. You still feed the event into the FSM and it still returns quickly. If you have syncthreads you are doing this explicitly, otherwise the kernel is doing it for you. (if you don't get what I'm saying here, read the Syncthreading paper and come back).
In an ideal world the FSMs would be fully self contained and so it wouldn't matter if they were updated at the same time (e.g. preemptive threads). Sometimes, however, they have to interact because the protocol requires it. In this case there is a fundamental difference between preemptive threads and most event-based designs.
So, given that one caveat, if you are saying that threaded systems are slower, or have less throughput etc you are really complaining about the quality of your threading system.
Given that I've just said that syncthreading and event-models are, basically, the same - how can I say I support syncthreading?
Simply because the FSMs are so much nicer to code as threads when they are anything more than the most basic systems. Threading basically loads and saves your state for you (while event models make you update structures manually) and threading lets you have state encoded in the program counter. A linear progression of states is written as a linear progression of statements and loops of states are written as loops in the code. It's just so much easier to work with.
For you Mozilla users there is now a CSS tree at the top of the root page (in addition to the old-style tree at the bottom). It's a little buggy, sometimes it doesn't seem to fold away right and sometimes moving down to open a different branch changes the tree so that you select something else. It's a start thou
Later On: Removed it - just looks silly in a browser which doesn't support it
Very cool CSS [via Keith]. This is pretty much a mozilla only zone, konqueror doesn't stand up to much here, but there are some mangled versions of the pages for IE users. It would be cool to use some of the this kind of CSS on IV - but it would cripple it for most viewers. Having the tree structure as a CSS menu would be so funky I might just do it anyway.
With an eye to some backlinking on IV I tried to find a simple webserver that would log Referrer headers. Apache is far too big to use unless you really have a need for it (PHP etc), thttpd looks just right, but as soon as you switch to logging to a file it doesn't log referrers! Aggh!
In the end it only took about 5 minutes to hackup the One True Webserver to log referrers anyway, so that's what I'm running now
Whee! Imperialviolet.org lives! Xia went down and looks dead - and it unfortunately hosted the DNS for imperialviolet.org. Much thanks go to Schvin for DNSage from now on. I still have a slight hope of getting netsol to recognise metis as a nameserver thou.
Time has been all taken up by exams, so not much to tell from looking at my bookmarks (which are spanning both monitors again - sure sign that it's time to organise them).
Oh, and the letter I sent to my MP
Oh fuck. When the RIP act was passed dear Mr Straw bleated repeatedly about how careful the control was going to be and how tight the safeguards would be for spying on people. Now what do we have?
"expanded to include seven Whitehall departments, every local authority in the country, NHS bodies in Scotland and Northern Ireland, and 11 other public bodies ranging from the postal services commission to the food standards agency."
The Food Standards Agency?? And this comes as a government aide has to apologise for investigating a member of the Paddington Survivors group because they might be against government policy.
As a first step, your goal, dear reader, is to try and get TLS installed on your MTA today. It's only a small step, but it's pretty simple (qmail, Debian Exim, Exim, Postfix).
Send an email to me (via TLS/SMTP of course) and get your name on a roll call of fame. Guess who's MTA has been TLS enabled for ages?
E7l3 discusses A New Kind of Science today. As I'm a little further into it it has got a lot better - mostly because Wolfram has stopped talking about how wonderful he is.
Lots of new stuff on LtU. When it rains, it pours (certainly true of the weather today)
Seattle Times article [via Bram] talking about how `public domain' means almost nothing in US legal terms and a little about BitTorrent.
Old Story about Australia abusing spying powers. More reason why people should be very worried about what Europol wants to spy on (mentioned here before).
Like I said, a lot of projects are long term solutions to this and, in thinking about it, I must admit that I keep designing some manic things. (I'm not ready to throw them out yet). As a start I'm looking at overlay networks and the performance of TCP over different connections with a view to creating a Crowds like network. While I'm at it, it would be nice if the overlay network could make NATed and firewalled hosts first-class peers.
In order to play about with TCP I've setup a quick program that uses the tun/tap device to simulate a link with a given bandwidth, latency and packet loss. I might post the results here if there's anything worth noting.
However, exams are taking first place in my scheduling now
On Computers and the Evils Of Powersaving
Went into school yesterday to startup everything and to fit a UPS on metis. Unfortunately I didn't compile the kernel with serial support (minimal and all that) so I'll have to reboot metis on Monday with a newer kernel. Good excuse to switch to 2.4.18 thou.
I also took marvin (the laptop) in with me and let it feed off the 2Mbps connection. It's now a fully up to date Debian unstable with 2.4.18 etc. I also finally got both my PCMCIA cards working. The 3Com network card was fine under 2.2.17, but the Aironet didn't work at all.
In comes 2.4 and both of them break. It turns out that the 3c575 driver has been replaced with 3c59x which has hotplug support (meaning it can handle the PCMCIA card without cardmgr or any of the rest of the pcmcia-cs tools). The airo drivers, however, do need pcmcia-cs and only the latest will do. Anyway - it's all working now.
Since I have an Aironet but no other 802.11b devices I set ethereal sniffing wifi0 and walked into town to pickup a book (more on that later). The Aironet is, as I understand, the best card for sniffing since it can do RFMON (multiple frequency sniffing I think). But the laptop went into power saving (which I expected) and powered down the PCMCIA bus too (which I didn't), so I got nil packets. Oh well.
A New Kind of Science
The book I was picking up was A New Kind of Science, which has finally reached this country. And thanks to Anna Gregson who came up to me in town and just gave me 30 pounds, thus neatly paying for nearly all of the book. I wish more stunning ladies would do stuff like that
I've only read the first couple of chapters but so far Wolfram is being a pompous twit. He spends a lot of words talking about how he is the first person to recognise that complexity can come from simple structures and how he is the first person to study it.
Doesn't exactly ring true does it?
I think, Stephen, that most people has realised that long ago. Certainly people who had looked at crypto. I mean, it's spelt out word for word in Cryptonomicon (the chapter about LPW and organ). LFSRs were the mainstay of military crypto for years and were very well studied. Maybe I'll think more highly of this book as I get more into it.
The Beauty of Fonts
This [via Raph] is a good discussion of why so much has been said about unhinted AA recently. Just look at Chimera - that's nice. Unfortunately, since I run Xinerama I can't have XRENDER as well, at least in 4.1.0. Maybe 4.2.0 will fix it, but Debian doesn't have it yet (thou I note that Gentoo does).
(as an aside, Freetype have a cool new, fontish, logo)
CSS
As a rule of thumb - if it isn't broken in konqueror then I don't know about it. Pill pointed out that Mozilla (and other Gecko based browsers) didn't like the CSS because publicfile was returning the MIME type as text/plain. Fixed that in a very DJB way, the name of the CSS file is now iv.css.text=css.
Well, IV is still down as I write this, but I'm bringing it up tomorrow and taking my laptop to it's 2Mbps connection to download some stuff. Upgrading Debian for one (so I can drive my Aironet card) and I'll try to download this. It's a 143MB (5 hour) MP3 of someone called Zigmund Void. The first bit sounds weird (I wondered if the file was corrupt) but nym ensures me it's quite good.
Although a perfectly good day, I'm a little down. Firstly Zooko's hard drive died and took many unfinished papers and films of Irby with it. In the future I guess he'll backup, but there's something heart tearing about data loss like that. Maybe it's a sign of geekyness that I get upset by that. He's saving up to send it to DriveSavers but they cost lots. (you can always tell that if they don't have prices on the website then the cost is too high).
And for those unconcerned about the loss of millions of poor bits, then this made things worse. It's a record of what Europol wants to log given their new powers which I noted here before.
We need a short term solution to this problem (other than cutting these people up into lots of little pieces). Freenet/MNet and other such networks are long term and systems like Mixmaster are too difficult for most people. I don't know how much confidence I have given that most people seemingly couldn't care less but maybe something like Crowds (but with IRC and email etc too) would be ok.
I guess I'm more than a little depressed about human nature too. I have some thoughts about event-models and the like, but I don't feel like writing them up now
Imperialviolet will be down from sometime like 3AM BST tomorrow until BST morning Friday
It seems that Claire thinks she looks silly in this photo (she's dead center). Go email her and tell her she looks cute or something
When I subscribe to mailings lists I use a lists.something@imperialviolet.org address so that if that email address ever gets used for spam I can subcribe under another address and direct all mail to the old address into /dev/null
Unfortunately, this interacts badly with mailing lists which (resonably) require that the sender be a list subscriber. Good old mutt has send_hook commands in its config file which change the From address quite nicely.
That doesn't, however, change the envelope sender, but a quick look at the qmail-inject manpages shows that setting the Return-Path header will do that fine. Unfortunately, mutt strips Return-Path headers before sending (set one in a message, send it and then look at it in your outbox - it's gone). After grepping the mutt source and sending many test messages, deltab finially sorted it out - put set envelope_from in your .muttrc and all is solved. Thanks to all the #infoanarchy people who helped. (I'm just blogging this to help others and because I know I'll need it again at some point in the future)
Still reading Structure and Interpretation of Computer Programs and have just finished Garden of Rama (AC Clarke and Gentry Lee). It's pretty cool scifi - not hard scifi nor stunning - but a good read.
Software Fault Prevention by Language Choice: Why C is Not my Favourite Language [via DNM]
The following is a result of an IRC conversation with Zooko and tvoj and may well only make sense if one was a part of that conversation
This article (from the E homepage) suggests that capability systems cannot stop communicating conspirators. I think that either the author of that (MarkM?) or myself are misunderstanding something here. Capabilities can stop communicating conspirators (I'll show that in a sec) - but part of the situation definition in the article is "Bob may also communicate with Mallet" - which is a different problem. The article is, I think, talking about the following situation:A has a capability cap and can communicate with B. A and B wish for B to be able to use cap but A cannot transfer cap to B
In that situation A can proxy requests for B and in that way B can use cap
Now, there is a separate discussion about a different situation. I think we were confusing the two last night. The situation this time seems to me to be:
A has access to secret information and wishes to communicate/leak this to B. The capability system seeks to prevent this
Now I think that a capability system can ensure this. Proof by induction: Suppose for a moment that A and B have no capabilities. Thus they cannot do anything at all and so cannot communicate. If you only give them access to objects that do not allow communication then neither can communicate.
The problem is that the number of objects which do not allow communication is small and it's hard to find them. (I should mention at this point that this is a problem that Multics tried to solve - interested parties should Google for some papers from that).
If we give A and B access to integers and simple operations (add, multiply, divide) then they can perform simple tasks and still not communicate - even if we give them capabilities to the same integer objects. Integers are environment free - they have no state. An object which is environment free is also side-effect free and deterministic (the result only depends on the inputs). You can also think as side-effect free as does not write to to environment and deterministic as does not read the environment. In the following I mean deterministic (D) to mean mearly deterministic, the same for side-effect free (SEF)
Of course such properties only hold if the inputs are at least as strong. For example if you pass a deterministic object to an environment free function, then that function may set some global variable through the input.
To stop A and B communicating you must stop their environments from touching. You can give them EF objects with no problem. You can give them EF and SEF objects with no problem, same for EF and D objects. However, as soon as they have SEF and D objects you may have a problem as the D objects could write to something which the SEF objects could read.
Now, if A and B are running on the same computer then they share objects like the CPU. Give B a clock and they can communicate via the lengths of time-slices etc. Give them the ability to malloc and they may be able to communicate via the VM etc. This is why it's such a hard problem.
| / | Root |
| Alternate | The Weird and Wonderful |
| Backlinks | What are backlinks |
| John Gilmore | What's Wrong with Copy Protection |
| Archives | Blog Archives |
| One | Archive 1 |
| Two | Archive 2 |
| Three | Archive 3 |
| Four | Archive 4 |
| Five | Archive 5 |
| Six | Archive 6 |
| Seven | Archive 7 |
| Eight | Archive 8 |
| Nine | Archive 9 |
| Ten | Archive 10 |
| Eleven | Archive 11 |
| Twelve | Archive 12 |
| Thirteen | Archive 13 |
| Fourteen | Archive 14 |
| Fifteen | Archive 15 |
| Sixteen | Archive 16 |
| Seventeen | Archive 17 |
| Eighteen | Archive 18 |
| Nineteen | Archive 19 |
| Twenty | Archive 20 |
| Twenty One | Archive 21 |
| Twenty Two | Archive 22 |
| Twenty Three | Archive 23 |
| Twenty Four | Archive 24 |
| Twenty Five | Archive 25 |
| Twenty Six | Archive 26 |
| Twenty Seven | Archive 27 |
| Twenty Eight | Archive 28 |
| Twenty Nine | Archive 29 |
| Photos | Poor People Caught on Film |
| Jack and the Beanstalk | Jack and the Beanstalk |
| RIP Scan | Results of a Stage Scan Fire |
| Yosemite | Yosemite National Park |
| Projects | Incomplete things from the lab |
| Seagull's Bane | Linux Automounter |
| bttrackd | BitTorrent Tracker |
| CAPTCHA | CAPTCHA CGI script |
| Conserv | Console Serving |
| Deerpark | Using Tor with Firefox/1.1 (Deerpark) |
| DNSFix | Fixing DNS |
| Xovers | XTA Crossover Control |
| IAFS | Archive Org Storage |
| JBIG2 | JBIG2 Encoder |
| Verify | PGP Key Verifier |
| MaxFlow | Maximal Flow in Python |
| PyBloom | Bloom Filters in Python |
| pyGnuTLS | Python wrapping of GnuTLS |
| Sxmap | Apache SuEXEC Map |
| Hellard | Union Server Notes |
| Recordings | Free recordings |
| ICSM Choir | St Paul's Church |
| School | Ancient School Stuff |
| Writings | Who knows |
| Cap Systems | Capability Systems |
| Intro | Introduction to me |
| Suprema | JMC2 Group Project |
| MP Letters | Letters I've written to my MP |
| Sound | Sound With Dramsoc |
| SyncThreading | The wonders of user-land threads |
