Archive for the ‘computer’ Category

Computer talk

Monday, March 6th, 2006

I always enjoy listening to Car Talk on the radio. I think it's wonderful that it is possible to have a show with such broad appeal on such a technical subject. I suspect that most people who actually know a lot about cars find it annoyingly simplistic and inaccurate but probably still enjoy the jokes.

I wonder if it would be possible to do a similarly broadly-appealing show about computers? I guess the closest thing I've seen was Call for help on the old TechTV but I think that was both too geeky (and not funny enough) to have broad appeal, and also too simplistic to be of interest to real geeks. Being on TV instead of the radio probably didn't help either - if you're watching a TV show it's much more difficult to do something else at the same time than if you're listening to the radio so you're only going to watch if you're particularly interested, not if you're just a casual computer user.

I think a car-talk-style show about computers would be great fun to do. It would include all the jokes, banter and puzzles that we enjoy on Car Talk, and also help normal, non-geeky people with their computer problems. Sure you'd get a lot of calls just consisting of "Help! My computer has spyware!" but the Car Talk guys get a lot of calls just consisting of "Help! My car is making a funny noise/smell!" and somehow they always manage to make it interesting so I'm sure it's possible.

Perhaps it is just an idea whose time has not yet come. Computers have only been widely available for about half as long as cars have. Perhaps in another 30 years or so computers will be enough like cars are now that such a show would be possible.

Analog quantum computers

Thursday, February 16th, 2006

Quantum computers are really difficult to build. No-one has yet managed to build one that can do something that a classical computer can't do more quickly and easily. However, if someone does manage to build a quantum computer of reasonable power it could make all sorts of computations possible that aren't practical today. For example, a quantum computer might be able to solve chess (predict whether black or white would win, or if it would be a draw, if both players made the best possible moves).

Current avenues of research for quantum computers seem to mostly involve building something that looks sort of similar to a classical computer, with bits and gates that can hold both 0s and 1s at the same time (and which can be entangled with other gates/bits).

This article got me wondering if there might be another (possibly easier) way to go about quantum computing. Imagine you have an irreguarly shaped loop of wire, that bends and twists at all sorts of strange angles in three dimensions. For some reason you wish to find the surface which has that loop as its perimeter, but with the smallest possible area. This is quite a difficult problem computationally, but extremely easy physically - to solve it all you need to do is put some detergent in some water and dip your loop of wire into it. The resulting soap bubble film will be exactly the surface you are looking for. The difficult problem is made easy by the massively parallel nature of the many molecules of soap and water.

Suppose we found a physical way to solve a certain class of hard computing problems ("NP complete problems", to use a technical term). There is a theorem in computer science that (effectively) says if you can solve one NP complete problem, you can solve them all by rephrasing the unsolved problem in terms of the solved one. So all we would need to do would be to find a physical "computer" that could solve a particlar type of NP complete problem.

Quantum mechanics is extremely difficult to simulate on a computer, because every particle is "spread out" and computations must be done at each point in space to figure out what what will happen. There are some shortcuts for simple situations, but even moderately complex molecules are beyond our ability to simulate with a high degree of accuracy.

Perhaps it would be possible to solve some NP complete problem that would take centuries to solve with today's computers by transforming it into some physical problem which could be solved by a quantum-mechanical analog computer (maybe something like a Bose-Einstein condensate interacting with atoms fixed in particular positions on some substrate), reading off the answer and then transforming it back into the answer of the original problem.

[Edited to add] Since writing this I have realized that analog quantum computers don't really add anything because you can effectively only measure digital information. Even when making a measurement of some analog quantity your instruments are only so accurate so there will be a finite number of significant figures that you actually read off.

The future of computer interaction?

Monday, February 13th, 2006

I was going to post this seriously cool link today, but Slashdot and Fark beat me to it, so you probably saw it already.

Laptop fixing

Saturday, February 11th, 2006

"Puck", my laptop, developed a loose connection in its power connector over the past few days so today I set about fixing it. The actual fixing was fairly easy (I just had to unsolder the offending connector, clean and tighten the contacts and solder it back on to the laptop's motherboard) but the process of taking the machine apart and putting it back together again took the best part of the day.

There was an awful lot of dust, fluff, hair and food crumbs in there (the CPU cooler was especially full of dust and fluff which explains why there wasn't as much airflow through it as there used to be). This is why my can of compressed air ran out half way through. Also, I didn't have quite the right screwdrivers for the job, so I left a bit early to pick up Gennie from work and stopped at Fry's on the way.

The CPU must have become really hot at some point in the past because when I removed the CPU cooler (to clean the fan) a small area of the thermal compound had clearly been heated much more than the rest, and was baked right on to the heatsink. I wonder what the part of the CPU directly over that part of the heatsink does... I eventually managed to scrape it all off and replaced the heatsink using some fresh thermal compound. It is running much cooler now (Prime95 has been running for a good half an hour now and the exhaust still isn't burning my fingers). I suspect the thermal contact was never very good in the first place and that the fan now no longer needs to continually run at full speed to stop the CPU overheating.

Amazingly, when I put it all back together again it worked first time. This makes a pleasant change from when I took my previous laptop, "Jack" apart and killed it in the process. In my defense, I didn't know about thermal grease then. It is nice to know that I can fix a laptop.

The fan is still a little bit on the noisy side so I had a look online to see if I could find a replacement (Fry's didn't have anything suitable). There only seems to be one place in the entire world that sells the right sort of fan, and they were sold out. I suspect this particular model of laptop (a Samsung VM8000) often has fans fail. I also had a look on eBay to see if anyone was selling VM8000s (either working or for parts). I found two interesting things - someone selling a working one for £225, and someone was selling one that has exactly the same problem that "Puck" had this morning for £20. So (assuming those are fair prices) I have effectively made £205 (about $400) today. Maybe if I get bored of working for Microsoft I should start a business buying broken laptops, refurbishing them and then selling them. I know that there are people who make a living doing this.

Sand game

Tuesday, January 24th, 2006

The falling sand game is an amusing way to while away a few hours. The physics may be distinctly non-realistic but the emergent effects caused by the different interactions between the various substances are fascinating. See if you can figure out how I generated this image:

However, the version with flammable zombies is infinitely more disturbing.

Spam

Wednesday, November 30th, 2005

Current laws designed to prevent spam haven't really helped - the international nature of the internet simply means that spammers route spam (and, on the other end of things, "generated leads") via countries without anti-spam laws so that they cannot be traced by law enforcement.

To eliminate spam, it is not necessary to be able to identify every single spam email. Catching 99% or even as low as 90% would probably do the trick. By reducing the income of spammers by a factor of 10-100, sending spam quickly ceases to be economically feasible.

Catching 90-99% of spam or more is quite possible with today's spam filters. The problem is that because the focus is on eliminating the damage done by spam (the expense of the bandwidth it uses) these spam filters are generally implemented on email servers rather than at the client end. This means that there is no easy way for users to give feedback when the spam filter makes an incorrect choice (no access to the emails marked as spam, and no easy way to report a missed spam as such). This means that people are inclined to turn the filters off (so that they don't miss any email) and also means that the filters are never "trained" to recognize the newest spam-detector-foiling techniques.

The first thing we need to do is have the most popular email clients contain Bayesian spam filters. Emails detected as spam are downloaded but put into a separate folder and users are not notified when new spam is downloaded as they are when new non-spam ("ham") is downloaded. This means that users never need to worry about false positives - they can always check back through their spam folders for a missed message. As the amount of spam decreases, it eventually becomes possible to look at every spam during slow periods, to make sure there were no false positives. These clients will have two extra buttons "delete as spam" and "false positive" that they can use to help train the spam filters.

Whenever the email client is connected to the internet, it uploads its latest changes to its filter data to a trusted central server. This server collates all the information from the clients and produces new filter data which is sent back to the clients. In this way, all spam filters can quickly be updated to recognize the latest spam keywords and filter-avoidance techniques.

How do we prevent the spammers from polluting the filters by sending a large amount of bad data to the servers? All clients are authenticated to the servers and a trust metric is set up. If the data sent by the client tends to agree with data sent from all the other clients, that client's trust rating goes up. If it tends to disagree, the trust rating goes down. That way, the damage that can be done by a particular client is very limited (the filter should be designed to be able to cope with a small amount of incorrect data).

The final change that can be made (and, I think, the one that would make the most difference) is educating end-users that responding to spam is a bad idea. If a large red flashing message saying something like "Warning! The message below is likely to be fraudulent in nature. Exercise extreme caution in giving any money or information to this person or organization" appeared above any email detected as spam, it would probably put off most of the potential clients of the spammers. This method also minimizes the negative consequences of false positives.

These methods work even if not everybody adopts them and for the most part they are most helpful for those who do adopt them (thus providing an incentive for adoption).

Please feel free to evaluate my spam solution against the spam solution evaluator:

Your post advocates a

( ) technical ( ) legislative ( ) market-based ( ) vigilante

approach to fighting spam. Your idea will not work. Here is why it won't work. (One or more of the following may apply to your particular idea, and it may have other flaws which used to vary from state to state before a bad federal law was passed.)

( ) Spammers can easily use it to harvest email addresses
( ) Mailing lists and other legitimate email uses would be affected
( ) No one will be able to find the guy or collect the money
( ) It is defenseless against brute force attacks
( ) It will stop spam for two weeks and then we'll be stuck with it
( ) Users of email will not put up with it
( ) Microsoft will not put up with it
( ) The police will not put up with it
( ) Requires too much cooperation from spammers
( ) Requires immediate total cooperation from everybody at once
( ) Many email users cannot afford to lose business or alienate potential employers
( ) Spammers don't care about invalid addresses in their lists
( ) Anyone could anonymously destroy anyone else's career or business

Specifically, your plan fails to account for

( ) Laws expressly prohibiting it
( ) Lack of centrally controlling authority for email
( ) Open relays in foreign countries
( ) Ease of searching tiny alphanumeric address space of all email addresses
( ) Asshats
( ) Jurisdictional problems
( ) Unpopularity of weird new taxes
( ) Public reluctance to accept weird new forms of money
( ) Huge existing software investment in SMTP
( ) Susceptibility of protocols other than SMTP to attack
( ) Willingness of users to install OS patches received by email
( ) Armies of worm riddled broadband-connected Windows boxes
( ) Eternal arms race involved in all filtering approaches
( ) Extreme profitability of spam
( ) Joe jobs and/or identity theft
( ) Technically illiterate politicians
( ) Extreme stupidity on the part of people who do business with spammers
( ) Dishonesty on the part of spammers themselves
( ) Bandwidth costs that are unaffected by client filtering
( ) Outlook

and the following philosophical objections may also apply:

( ) Ideas similar to yours are easy to come up with, yet none have ever been shown practical
( ) Any scheme based on opt-out is unacceptable
( ) SMTP headers should not be the subject of legislation
( ) Blacklists suck
( ) Whitelists suck
( ) We should be able to talk about Viagra without being censored
( ) Countermeasures should not involve wire fraud or credit card fraud
( ) Countermeasures should not involve sabotage of public networks
( ) Countermeasures must work if phased in gradually
( ) Sending email should be free
( ) Why should we have to trust you and your servers?
( ) Incompatibility with open source or open source licenses
( ) Feel-good measures do nothing to solve the problem
( ) Temporary/one-time email addresses are cumbersome
( ) I don't want the government reading my email
( ) Killing them that way is not slow and painful enough

Furthermore, this is what I think about you:

( ) Sorry dude, but I don't think it would work.
( ) This is a stupid idea, and you're a stupid person for suggesting it.
( ) Nice try, assh0le! I'm going to find out where you live and burn your house down!

(I started doing so myself, but realised I could not be objective.)

What Colour are your bits?

Saturday, November 5th, 2005

Sorry for the lack of posts lately. I have a number of things on my backlog but they're in various states of incompleteness. Maybe tomorrow I'll find some time to finish some of them.

This is a really good essay about why computer scientists and lawyers will never quite see eye to eye and a very good way of thinking about things such as digital rights management and cryptography. The
follow up essay is a good read too.

Bootstrapping a compiler from nothing

Wednesday, September 14th, 2005

Two posts today 'cos I missed yesterday due to being disorganized.

Recently I've been working on bootstrapping a compiler from nothing. Just for fun. I know it's been done before but I wanted to learn about parsing and optimizing and how compilers are constructed.

The first stage of my compiler is a pretty clever hack, even if I do say so myself. I didn't want to use any external tools to get my compiler started, but that left me with a problem - how do I generate the first executable file? Well, one way to generate an arbitrary file from Windows is to just use an "echo" statement in the Windows command prompt and redirect the output to a file. But that only works reliably for ASCII characters (and not even all of those). This poses a problem, because the opcodes for even simple "MOV" instructions are all non-ASCII characters. But it turns out that the "constrained machine code" for x86 consisting of only ASCII bytes is actually Turing-complete and can be used to do useful things (non-ASCII opcodes such as the one for "INT" can be constructed using self-modifying code). So I put together an ASCII program that takes two characters from the command line, combines them into a byte and outputs the resulting byte (which can then be redirected to a file). Calls to this program can be strung together to make (almost) arbitrary binary files, which can be used to compile more complex languages.

In this way (13 iterations later) I have built up a simple but effective 2-pass 16-bit DOS assembler which outputs .com files. I have also written a recursive descent parser for simple infix expressions on unsigned 16-bit integers, and am working on writing a code generator which can output binary code for these expressions.

Eventually I hope to evolve this into a fast and powerful language to rival C++. It will be a language which combines very low-level and very high-level concepts, and will therefore be an ideal language for writing compilers (such as itself) in. I could then use it for writing all sorts of other fun things - maybe I'll tackle an OS when I've finished the language. But for now I'm just having fun learning about things.

Now I just need a name for this thing

Wednesday, August 31st, 2005

I was arguing (in a friendly way) with some people the other day and it got me thinking about an idea for a new website. Technically it is a kind of "conflict resolution" website, but in practical terms it is a forum for people to argue in without anybody getting angry or repeating themselves and without the argument devolving into what the definition of "is" is.

It occurs to me that this idea has been brewing in my head for some time - back when I was living at home, one of my brothers used to argue with my parents quite often all the time and I used to try to moderate the arguments. It was frustrating to try to get each party to actually listen to what the other was saying. Also, because the refutation of any given statement might involve several other statements (more than one of which might need to be refuted) it can get difficult to keep track and some threads of conversation might get forgotten.

Here is how the site would work. User A posts a controversial statement - say (for argument's sake):

  • Statement 1: "Abortion should be legal"

This statement becomes a page on the site. User B, happening upon this page, is given the option of expressing an opinion on this statement. The options are "I agree", "I disagree" and (the default) "I neither agree nor disagree". On each statement's page, the site would show the proportion of people who have expressed an opinion on the statement and the proportion of those who agree with it.

Suppose user B disagrees with statement 1. They then have the opportunity to make a set of arguments and statements in support their opinion. In this case, such statements might be:

  • Statement 2: "Abortion is murder"
  • Statement 3: "Murder should not be legal"
  • Statement 4: "Statements 2 and 3, when taken together, imply that statement 1 is false"

User A might agree with statements 3 and 4 (and can press buttons on the pages for those statements saying so) but disagree with statement 2. User A's arguments against statement 2 might take the form:

  • Statement 5: "Murder is the deliberate premeditated ending of a human life"
  • Statement 6: "An unborn fetus less than 24 weeks into the term of pregnancy is not a human life"
  • Statement 7: "Statements 5 and 6, when taken together, imply that statement 2 is false"

User A might also make another statement in support of statement 1:

  • Statement 8: "If abortion was illegal, it would create a black market for abortions which could be dangerous for women who are in desperate situations"
  • Statement 9: "Statement 8 implies statement 1"

User B might then agree with statements 5, 7 and 8 but disagree with statements 6 and 9 and give their reasoning. And so on.

There are two sorts of statements here - "monolithic" statements like statements 1, 2, 3, 5, 6 and 8 and "connecting" statements like statements 4, 7 and 9. The site uses connecting statements to create trees of deduction for a particular user - figuring out why people believe what they believe.

The site would keep track of unrefuted statements, track back through the deduction trees and show, for each statement, which side (if any) is "winning" the argument.

In the course of reading statements from other users, a user might change their mind about some statement. Suppose user C agrees with statements 3 and 4 but disagrees with statements 1 and 2, but is then persuaded to change their mind about statement 2. The site uses the trees of deduction to find contradictions in a user's opinions. The user will then be given the opportunity to choose which other statements they want to change their mind on to resolve the conflict. In this case, the site would say "Your opinions on statements 1, 2, 3 and 4 conflict. Which one(s) do you want to change your mind on?"

Another possibility is that two users might disagree on some experimentally verifiable fact. The site would keep track of such statements and, given a disagreement, would be able to propose an experiment which would resolve the disagreement one way or another. Once this experiment has been done, the result (with suitable references) can be posted in another statement and can be used to convince people of things or can be disagreed with (if people believe the experimental method used was flawed).

Yet another possibility is that two users agree to disagree on a particular statement, and make a connecting statement saying ("statement x is neither provable nor disprovable"). That is fine too - the site only records people's opinions on various statements, it does not pretend to be fount of universal knowledge.

Further refinements which could be made:

  • The site could keep track of definitions of particular words, so that users have a common vocabulary to communicate with (e.g. the word "murder" in statement 3 might be a hotlink leading to the page for statement 5). A statement about murder in a different context might link to a different definition.
  • Users could associate themselves with particular groups such as "liberal", "conservative", "libertarian" - this would not change any of the arguments but would allow the site to be able to generate interesting (although possibly obvious) statistics such as "90% of conservatives agree with statement 2". The site could even try to categorize users based on their opinions.

Of course, some users might disagree with the logic that the site uses to deduce things. For example, a user might disagree with "if A implies B and B implies C then A implies C" on finding some of their long-held beliefs in contradiction. Such users would be encouraged to set up their own site with their own system of logic (you can't even begin to have an argument if you don't agree on some basic axioms that you can use to deduce things). Of course, a similar website which uses a form of logic that isn't very useful won't be well-frequented!

Computer graphics of the future

Sunday, August 28th, 2005

Back in secondary school I was fascinated by the concept of ray tracing. At first I thought it was the ultimate rendering algorithm - that photographic-quality computer-generated pictures would be possible just as soon as we managed to accurately model the way light reflected or was refracted by the surfaces we wanted to visualize.

Then it occurred to me that maybe shooting rays from the eye back to the light source was not necessarily the best way to go about rendering objects. What if we shot rays from the light sources to the eye instead? The trouble with that approach, I quickly realized, was that most light rays are absorbed by other surfaces before reaching the eye, so you would have to shoot an awful lot of photons to get anything approximating an image.

The next step in this mental process was to imagine combining forward and reverse ray tracing - shoot rays from the light source and bounce them around a bit to figure out where the light ended up in the scene, and then shoot rays from the eye into the scene (using the normal ray-tracing algorithm) to actually render the image, using the first set of rays to figure out which parts were lit up, which were in shadow and so on. Unfortunately I never got around to implementing this idea.

Turns out that someone beat me to it anyway - Henrik Wann Jensen had already invented photon mapping some years before and rendered some beautiful images of Cornell boxes, caustics and architectural models. All the good ideas have already been thought of...

If computers continue to get more powerful at the rate they have been, in 10-20 years it should be possible to render photon mapped images and model the subsurface scattering needed to render translucent objects (like people) all in real time. By then we will all have high dynamic range displays (I saw one of the BrightSide displays at an MS research techfest earlier this year - it was awesome) and will have sophisticated procedural geometry algorithms for rendering all sorts of complex natural objects. These technologies (especially combined) will be able to generate some truly awesome images, increasingly difficult to distinguish from real life.

The future of computer graphics looks good!