We can always count on help from him on the toughest NY Times crossword puzzles, and sometimes he even picks up the tab at our student social nights. Plus, he was too modest to even mention winning this award, so the whole theory group was just as surprised as everyone else when it was announced.
And oh yeah, he's gotten a haircut since the picture on his web page:).
This is good work, because it illustrates the real-world importance (i.e., feasibility) of "chosen-ciphertext attacks." PGP and GnuPG are vulnerable to these attacks *by design*. It's not a mathematics problem, or an implementation problem, or a standards problem, but simply a requirements problem. Nobody thought to use CCA-secure encryption in PGP et al. Nor is anyone really to blame: these kinds of attacks weren't even formalized, nor reasonable solutions proposed, until a few years ago. It requires specialized cryptosystems, built from the ground up, to offer provable security against such attacks.
Chosen-ciphertext attacks take advantage of some kind of "malleability" in the ciphertext. For example, say Eve intercepts some RSA ciphertext C of a message M from Alice to Bob. She wants to know M, but can't solve RSA. Well, she just multiplies C by, say, 3^e (mod n) [where e is the encryption exponent in the public key] and sends it off to Bob. Bob decrypts it and gets some junky-looking message M', and sends it along to Alice, saying "what gives?" Little does he know that M' = 3M, whence Eve intercepts M', divides by 3, and viola. In reality the situation is more complicated (RSA is used to encrypt session keys, not full messages), but the principle is the same.
Chosen-ciphertext-secure cryptosystems generally embed some "proof" that whoever generated the ciphertext "knows" the message to which it decrypts. For example, they use (idealized) hash functions, or encryption of the same message under two different keys. This way, Eve can't generate a valid ciphertext by modifying something Alice sent to Bob. If the proof doesn't check out, then Bob can tell that he may be under a chosen-ciphertext attack, and will throw away the ciphertext. In the previous scenario, Bob can't tell whether the ciphertext was built maliciously, or was just the encryption of some garbage that Alice legitimately sent. Here, he can.
I like this work because it moves chosen-ciphertext attacks from the realm of "paranoid academics modelling an unrealistically powerful adversary" to the "real world." Now people may think twice before chosing weaker crypto than is currently available.
The overwhelming standard in computer science academia is to list the authors in alphabetical order, by last name. This is even true when the first author is a grad student, and the second is a fully tenured and famous professor. (See, e.g. the Liskov and Rivest paper in Crypto'02 this summer.)
In other fields (biology and other physical sciences, most specifically) the principal investigators tend to be listed first, followed by the "lesser" contributors (even if most of the work was performed by the latter).
At Asiacrypt this year, Nick Hopper presented a paper (by he and Manuel Blum, both of CMU) on a related theme. The goals were to come up with an authentication process that could be performed:
By a naked person,
In a glass house,
Without any calculation aids (i.e., scratch paper).
The idea was to have a large (say, 20 by 20) grid of squares. The user remembers a few (say, 7) of those squares by their positions. This can be aided by shading the grid, so the user can remember "one of my squares is that white one in the black blob at the upper-right."
A challenge is performed in the following way: random digits, 0-9, are assigned to each square in the grid, and presented to the user. He adds up the digits inside his squares, and enters the last digit of the sum (mod 10 arithmetic). Here's the kicker: the user has to do this 7 times (with 7 different random assignments), but he MUST answer EXACTLY ONE challenge (of his own random choice) wrong!
It turns out that you can prove some pretty strong things about this scheme: even if an adversary has tons of computation power, can watch "over the user's shoulder," and make the user authenticate himself a million times (way more than any user could ever do), the adversary's odds of authenticating as the user are extremely low. The authors' experiments showed that most people (well, OK, CMU grad students) can authenticate themselves correctly within one or two tries.
To aid memory, I suggested using a complex scene (like a "Where's Waldo" picture) and having the user remember a few objects in the picture (e.g., "hammer, red-haired woman, church,..."). A challenge would consist of the scene with a random digit superimposed over every object.
The major problem with this scheme is the time it takes to authenticate (about a minute or more). I don't know if they are going to do more experiments, but it sounds like it has potential.
IIRC, Guy Steele (one of the designers of the Java spec) wrote his thesis on converting Scheme code into continuation-passing style, then compiling that. This gives you tail-recursion (briefly, writing code in a recursive style, but making it behave iteratively) for free!
Continuations are really nice for *formally* defining how languages should behave under forking (with data dependencies among threads), and other wacky control features that may or may not be useful. I've only seen this stuff done rigorously for Lisp-like languages, in the lambda calculus. I doubt it's used at all for imperative languages.
Oh, gee, thanks Mr. Hatch. The same guy who got us into a huge software-copyright mess with the DMCA is now offering to save us by threatening compulsory licensing of music? You'll pardon me if I ask you kiss my pecker. (With apologies to Kevin Spacey aka Verbal Kint of "The Usual Suspects.")
Let's not forget that the DMCA is the very law that screwed over fair use, the very law that caused the recent DeCSS mess, the very law that Metallica used to bully Napster, the very law that makes you guilty until proven innocent of copyright violation, and the very law that Hatch himself admits was supposed to encourage online music distribution. Yes, Mr. Hatch has amply demonstrated his qualifications for crafting reasonable copyright legislation.
Go ahead, whoop it up over Hatch and his Congressional inquiry. You'll find that any law that comes out of it will further stifle innovative models for music distribution down the road. Pay attention to your history before you go crying to Congress to fix your problems for you.
I think the problem derives from you think "true" means. When you prove that T is undecidable, you're formally proving that there is no finite sequence of statements that prove T, and no finite sequence of statements that prove "not T". In other words, you can't prove that every system containing the axioms has a counterexample. There is, in fact, a counterexample in a suitably extended system!
The example of (non-)Euclidean plane geometry and the parallel postulate is a good one. That axiom is undecidable wrt the other axioms. In other words, it's not provably true, but you can't prove that there is a counterexample in every logically consistent geometry that includes the other axioms. Therefore good ol' high school geometry tacks on the parallel postulate, but non-Euclidean geometries (which contain all the other axioms) define lines and points such that there is greater/less than one parallel line through the point.
Conversly, the statement "for all x, x>=2" is provably false in every system which obeys Peano's axioms for the natural numbers, because the element known as "1" is a counterexample.
If you show that a statement T is undecidable, then it is "true" in the sense that there are no counterexamples, but the "way that it goes" is up to you. You can extend your system into two logically consistent systems: one in which T is provable (by making T an axiom, for example), and one in which T is false (by making "not T" an axiom).
So, in conclusion, proving the undecidability of T does not constitute a proof of T.
Several of Hilbert's problems in 1900 were of the form "find an algorithm for such-and-such", where such-and-such was something like "determining whether a polynomial of arbitrary degree and arbitrary number of variables has integer roots." These problems were closed, but not strictly solved, since it was proved that there were no such algorithms to do what he wanted.
I would find it extremely interesting if, in the 21st century, it were shown that many of these conjectures were also proved to be undecidable. It would certainly explain why some of them have taken so long to figure out.
If you show that the conjecture is undecidable, you haven't proven or disproven it - so do you still get the million $$?:)
In both cases, the average class/section will be taught by a graduate student and you'll be quite lucky if the professor even knows the names of ten people in the entire course.
That's a laugh. My freshman physics recitation (8.01) was taught by Alan Guth (an almost-certain Nobel prize winner in Physics for his work on cosmology). He knew my name within two class sessions - but that was easy, because there were only 18 of us in the recitation.
Maybe that was a fluke, but I don't think so - because my introductory computer science recitation (6.001) was taught by Rod Brooks. Yeah, the guy who created AI robots with insect-like intelligence (his current project is a artificial human).
Or let's take a look at my sophomore year, when my Computer Systems Engineering recitation was taught by Ron Rivest, "the R in RSA." I enjoyed that so much I took his Computer and Network Security class the next term. And he remembered me!
Mind you, these are just recitations - the lectures were taught by equally luminous professors. Like my 8-person topology seminar with James Munkres, who is basically the top guy in the field. Or my graduate AI class with Patrick Winston. Or any of several classes by Marvin Minsky or Noam Chomsky.
Lest I be accused of name-dropping, this illustrates the point quite clearly: you really can get a personalized education from the very best in a field if you go to a Really Expensive School. If you have the opportunity, go for it!
If you're looking for straight answers to the kinds of questions that you listed, check out Harry Browne's site, and the Libertanian Party site. Whether or not you agree with his/their views, you won't be treated like a fool; you'll get straight answers. Hopefully you'll like the answers and be persuaded to vote Libertarian, but if not, you can at least make an informed decision.
Any dialect of LISP (e.g., Scheme) will treat tuples (OK, pairs) as first-class objects. Even better, programs themselves are essentially complex structures built from pairs. This is all a consequence of LISP's incredibly simply syntax (even simpler than Python, I'm sure). That makes LISP a great language for writing programs that manipulate programs (evaluators, compilers, etc.). I've seen simple compilers implemented in hundreds (not tens of thousands) of lines of LISP code. If you like Python's ability to built complex structures from basic pieces, you'll really like LISP.
In a class called "Computer and Network Security" taught by Ron Rivest, a group of students did an interesting project on how one might completely destroy the security of a Linux machine. To wit:
One could write a kernel module that doesn't allow itself to be listed with lsmod. It even steps on certain system calls so that the file containing it doesn't get listed with ls. It also adds itself to several key executables but alters the system calls so that the file sizes don't appear to change. It provides a backdoor that allows a cracker to own the machine remotely, and disables any kind of logging that would result from the cracker's actions. This module could be sent through any kind of buggy network daemon, and spread like a worm. The machine's admin would have a hell of a time even discovering that the machine was infected! It seems that running a virus in kernel space gives you significantly more power than even running it as root.
Of course, the students didn't implement this virus/trojan/worm - it would require some crazy skillz, but they really had their bases covered when it came to design.
It should be noted that this kind of thing could probably pulled off on many different types of operating systems, and might be even more successful since commercial systems have more homogenous kernels (I can imagine all kinds of "unresolved symbol" errors with all the custom Linux kernels out there...)
During a 1:20am commercial break of "Late Night w/ Conan O'Brien" here in Michigan, there was a 10-second news bite delivered by the usual tired-looking local newsperson. After mentioning some Texas schoolteacher wanted for murder, she said (approximately) "a California judge has denied a restraining order for software that allows copying of DVDs."
While I'm sure none of us would be happy with the content and length of the report, it does show how big of an event this was! I'm sure that the great turnout by interested and well-behaved parties plays a big part in the news coverage that we're seeing.
Let's say, for the sake of argument, that the NSA made this announcement. The inevitable response?
"The NSA must have found some huge security flaws in Linux! They're trying to get us to run it so they can packet-sniff our diffs! Then they can have the newest kernel releases before the Slashdot effect bogs down kernel.org! Conspiracy! (Run BSD instead!)"
I'll quit while I'm ahead, now that I've pissed off just about every special-interest group here...
An idea I've been batting around for awhile: micro-payments in conjunction with open-source software. The software developer maintains a website with documentation, links to archived mailing lists, and packages with binaries and source code. In order to download the binaries or source from that site, you make a micropayment of, say, ten cents to the lead developer/organization behind the project. With all the people using the software, there would be enough money coming in to prevent the developer from going broke, and maybe enough to be a good chunk of supplemental income.
Nothing else would change: the software would still be free (so it might be available for free from lots of other ftp and web sites), but by going to the "official" distributor, you'd get the latest version and be able to make a small, but appreciated, contribution. Right now it's just too inconvenient to support free software financially, and in order to make a difference, you've got to hand over a much bigger chunk of cash. This would allow a developer to make a difference for himself, and probably a lot more money too.
Of course, in theory this could all be done with banner ads on the official site. But that probably doesn't bring in nearly as much cash. I can't think of a real good reason why more people aren't already doing this, actually...
At any rate, this doesn't become practical until there is a solid micropayment infrastructure set up. Wake me up in ten years and we'll see how good my predictions were...
Gosh, all I see is whining about how this is "old news" - I don't recall ever seeing exactly what license XFS was going to be distributed under.
Regardless, let's showing a little fscking gratitude (forgive the pun) to SGI! They're supporting Linux on their workstations, their developers have always contributed to the kernel, and now they're freeing a huge, important chunk of code that is desperately needed and would be a massive development effort to start from scratch! Hoorah for SGI!
So what if it's a pre-emptive strike against IBM's journaling file system? More free software is good free software! Now we have more choices, and people can pick what's right for their uses, and may the best product "win", because in the end, we're all going to win. Huzzah!:)
Well, you can compile e-lisp code (EMACS's dialect of lisp) into a sort-of e-lisp bytecode. Check your site-lisp directory; it probably has a mixture of.el and.elc files - the.elc ones are precompiled.
To merge with another thread farther up the discussion, this is exactly why the power to create a post office was written into the US Constitution. It was believed that the social benefits of having an accessible, universal communication device that by definition served the entire nation outweighed any savings from local delivery efficiencies.
Even if I agree with your entire post, you haven't given a single reason why independent, non-governmental businesses should be locked out from providing first-class service, or package delivery at as low of a price as they can provide. The entire thesis of my original post, if you look at the first paragraph and the first two items, was that these laws are ridiculous and hurt the consumer (keeping in mind that "repealing the two-times law" != "destruction of USPS through market forces" != "destruction of USPS by act of law"). The USPS, large delivery services, and local delivery services could all coexist, that is, if federal law didn't effectively eliminate the possibility of local delivery services. I repeated these issues in my rebuttal. Why have none of the replies come even remotely close to addressing this issue??
What kind of guarantee are you offering? If private businesses charge 34c per letter are you personally going to reimburse the letter senders of America one billion dollars?
Yes, of course I will. Just send the bill to the me, c/o Dept of Dumb Rhetorical Questions. Now that we're both done being silly, let's get the heart of the matter.
Or are you offering the same guarantees that accompanied the other deregulations and mergers that have thus far failed to pass along any cost savings to customers (i.e. none whatsoever)?
Arguments about the value of mergers aside, you'll notice my original message stressed the unnecessarily high cost of local delivery, which could otherwise be handled by small businesses.
Question: how much of the mail you send goes farther than 100 miles? People tend to send bills, letters to friends and relatives, and "paid by sender" mail. Bills go to their local phone company, local cable company, etc. Letters and greeting cards to local friends are also common. "Paid by sender" mail doesn't even enter the equation.
Now let's talk business mail. Lots of businesses have a couple of offices or locations at various places across town (I can name a dozen such businesses in my hometown). Right now, they can either hire somebody to drive small stacks of letters around, or they can pay the first-class rate and have their mail delivered in 2-3 days. Without the first-class restriction, they could contract with a local mail delivery service and possibly save a lot of money.
From looking at their corporate report it seems like the only reason FedEx is still is business is because of the "two-times" rule. They aren't efficient enough to operate with the same cost structure as the USPS, apparently.
Great - so not only is the two-times rule keeping out new competitors and keeping the USPS entrenched, it's also a form of corporate welfare for FedEx. After all, FedEx wouldn't like it too much if a competitor arrived and offered the same reliability, at half the price. Thanks heavens we have the two-times law to prevent that from happening!
[Note: that prices might come down and other companies might enter the market is also not a fact.]
It sure isn't. But eliminating price-floor laws sure won't make prices go up. I think you're missing the point: there's no reason to support laws that prevent businesses from entering markets like this, but it sounds like that's exactly what you're doing. You say that my "guarantees" may not happen, but that's not an argument that the two-times law is, in itself, good.
There's no compelling reason to give preference to any particular service. If the two-times law and its friends are repealed, and FedEx still charges the same prices, and nobody else springs up to offer cheaper service, then nothing has been lost. But if local mail and package services do appear and flourish, then everyone wins. The USPS isn't going anywhere: it's been around for almost 200 years, and it's a government agency (we know how hard those are to get rid of). So let's just allow people and businesses the choice of service, price, and reliability that they want.
The USPS may not be a "monopoly" in the classical sense of the word, but there are a lot of federal laws that ensure that it stays entrenched, and that bar competition. For example:
The USPS is the only entity, by law, that is allowed to deliver first-class mail. That's a biggie - because I guarantee that otherwise, businesses would spring up to deliver local mail for a fraction of the 33c per letter we pay now.
The "two-times" rule: wonder why USPS delivers for $3.20 and FedEx for $6-8? It's because private business cannot, by law, charge anything less than twice the USPS rate for comparable package delivery service. This is also huge: it again locks out businesses that could provide cheap local service, and keeps prices artificially high.
This business about the USPS "turning a profit" is bunk. The accounting methods that the federal government uses would be illegal a dozen times over if they were attempted by private businesses. The USPS gets taxpayer money, no doubt about it. Besides, where would this "profit" go? It definitely doesn't go back into the federal budget. Is anybody here receiving dividends from holding stock in the USPS? I didn't think so. "Profit" is conceptually impossible in the context of government (or "pseudo-government", a euphemism some prefer) agencies.
The bottom line is, some people hate the service the USPS offers. Those people are already convinced. To those who like the service, I point out to the countless laws and benefits that favor the USPS, keeping it entrenched no matter how poor its service may get in the future, and locking out private businesses from doing an even better job at a cheaper price.
Hey everyone, this is not encryption. Why? The message itself is never obfuscated or transformed in any way, instead it is merely hidden among a lot of other DNA, on a very small dot that wouldn't be noticeable under brief scrutiny. The only similarity between this and encryption is the existence of a secret (the base-pair sequence of the DNA strand "caps") between two parties.
There is a term for this type of message-hiding, but it's eluding me (someone around here knows it, I'm sure...). Other popular examples include:
Putting a message into a.GIF or.JPEG image by slightly altering the colors of some of the pixels (where the system of alteration is known to both the sending and receiving parties).
Putting a message into a very small dot of ink (like the period at the end of a sentence) on an otherwise benign piece of correspondence. The receiver can see the message under a microscope, if he knows where to find the dot.
Again, this is different from encryption because the important message is hidden in an otherwise benign and useless message. So the hard part of breaking the system is knowing whether a message is hiding another message. Once you know that, breaking the scheme is pretty trivial - there's no computational complexity behind the system.
There have been a few good answers to this question in this thread, but there's one thing that hasn't been pointed out yet: journaling file systems don't (immediately) overwrite a file when it is changed.
To elaborate, imagine a long tape that represents your hard drive. The tape is written from left to right. When a file is changed, the new version is appended to the end of the existing data, while the old version remains "untouched" farther to the left. When the kernel has finished updating all pending file writes, it can write a "checkpoint" at the end of the existing data. Essentially the checkpoint says "everything up to the point is kosher." If the disk gets really full, then the filesystem can double-back and overwrite the really old data at the beginning of the tape.
Now, let's see how this works to help recover from crashes; say the computer crashes as it's writing out a file to disk. In a conventional filesystem, a lot of things could go wrong: it could have been overwriting the old data, but finished only half of the job. Then, at best, you've got a corrupted file with a hybrid of new data and old data. The file allocation table may not have been updated, so the file may be completely lost. It's a bad situation.
Conversely, if the crash happened with a JFS, the computer would run an "fsck" and look for the last checkpoint. It's guaranteed that all data preceding the checkpoint has integrity. Then the filesystem would just work from that checkpoint and ignore any non-checkpointed data. This can still lead to some data loss, but never to filesystem corruption.
Of course, this is a simplified account, and there are implementation details. But that's the gist of it.
Slashdot Mirror
I'm either missing something or the boys at the MIT lab are thinking too hard.
:)
You are missing something... one of the authors is a woman.
He's also a damn cool guy.
:).
We can always count on help from him on the toughest NY Times crossword puzzles, and sometimes he even picks up the tab at our student social nights. Plus, he was too modest to even mention winning this award, so the whole theory group was just as surprised as everyone else when it was announced.
And oh yeah, he's gotten a haircut since the picture on his web page
This is good work, because it illustrates the real-world importance (i.e., feasibility) of "chosen-ciphertext attacks." PGP and GnuPG are vulnerable to these attacks *by design*. It's not a mathematics problem, or an implementation problem, or a standards problem, but simply a requirements problem. Nobody thought to use CCA-secure encryption in PGP et al. Nor is anyone really to blame: these kinds of attacks weren't even formalized, nor reasonable solutions proposed, until a few years ago. It requires specialized cryptosystems, built from the ground up, to offer provable security against such attacks.
Chosen-ciphertext attacks take advantage of some kind of "malleability" in the ciphertext. For example, say Eve intercepts some RSA ciphertext C of a message M from Alice to Bob. She wants to know M, but can't solve RSA. Well, she just multiplies C by, say, 3^e (mod n) [where e is the encryption exponent in the public key] and sends it off to Bob. Bob decrypts it and gets some junky-looking message M', and sends it along to Alice, saying "what gives?" Little does he know that M' = 3M, whence Eve intercepts M', divides by 3, and viola. In reality the situation is more complicated (RSA is used to encrypt session keys, not full messages), but the principle is the same.
Chosen-ciphertext-secure cryptosystems generally embed some "proof" that whoever generated the ciphertext "knows" the message to which it decrypts. For example, they use (idealized) hash functions, or encryption of the same message under two different keys. This way, Eve can't generate a valid ciphertext by modifying something Alice sent to Bob. If the proof doesn't check out, then Bob can tell that he may be under a chosen-ciphertext attack, and will throw away the ciphertext. In the previous scenario, Bob can't tell whether the ciphertext was built maliciously, or was just the encryption of some garbage that Alice legitimately sent. Here, he can.
I like this work because it moves chosen-ciphertext attacks from the realm of "paranoid academics modelling an unrealistically powerful adversary" to the "real world." Now people may think twice before chosing weaker crypto than is currently available.
The overwhelming standard in computer science academia is to list the authors in alphabetical order, by last name. This is even true when the first author is a grad student, and the second is a fully tenured and famous professor. (See, e.g. the Liskov and Rivest paper in Crypto'02 this summer.)
In other fields (biology and other physical sciences, most specifically) the principal investigators tend to be listed first, followed by the "lesser" contributors (even if most of the work was performed by the latter).
How does it translate: "All your base are belong to us"?
At Asiacrypt this year, Nick Hopper presented a paper (by he and Manuel Blum, both of CMU) on a related theme. The goals were to come up with an authentication process that could be performed:
..."). A challenge would consist of the scene with a random digit superimposed over every object.
By a naked person,
In a glass house,
Without any calculation aids (i.e., scratch paper).
The idea was to have a large (say, 20 by 20) grid of squares. The user remembers a few (say, 7) of those squares by their positions. This can be aided by shading the grid, so the user can remember "one of my squares is that white one in the black blob at the upper-right."
A challenge is performed in the following way: random digits, 0-9, are assigned to each square in the grid, and presented to the user. He adds up the digits inside his squares, and enters the last digit of the sum (mod 10 arithmetic). Here's the kicker: the user has to do this 7 times (with 7 different random assignments), but he MUST answer EXACTLY ONE challenge (of his own random choice) wrong!
It turns out that you can prove some pretty strong things about this scheme: even if an adversary has tons of computation power, can watch "over the user's shoulder," and make the user authenticate himself a million times (way more than any user could ever do), the adversary's odds of authenticating as the user are extremely low. The authors' experiments showed that most people (well, OK, CMU grad students) can authenticate themselves correctly within one or two tries.
To aid memory, I suggested using a complex scene (like a "Where's Waldo" picture) and having the user remember a few objects in the picture (e.g., "hammer, red-haired woman, church,
The major problem with this scheme is the time it takes to authenticate (about a minute or more). I don't know if they are going to do more experiments, but it sounds like it has potential.
IIRC, Guy Steele (one of the designers of the Java spec) wrote his thesis on converting Scheme code into continuation-passing style, then compiling that. This gives you tail-recursion (briefly, writing code in a recursive style, but making it behave iteratively) for free!
Continuations are really nice for *formally* defining how languages should behave under forking (with data dependencies among threads), and other wacky control features that may or may not be useful. I've only seen this stuff done rigorously for Lisp-like languages, in the lambda calculus. I doubt it's used at all for imperative languages.
Oh, gee, thanks Mr. Hatch. The same guy who got us into a huge software-copyright mess with the DMCA is now offering to save us by threatening compulsory licensing of music? You'll pardon me if I ask you kiss my pecker. (With apologies to Kevin Spacey aka Verbal Kint of "The Usual Suspects.")
Let's not forget that the DMCA is the very law that screwed over fair use, the very law that caused the recent DeCSS mess, the very law that Metallica used to bully Napster, the very law that makes you guilty until proven innocent of copyright violation, and the very law that Hatch himself admits was supposed to encourage online music distribution. Yes, Mr. Hatch has amply demonstrated his qualifications for crafting reasonable copyright legislation.
Go ahead, whoop it up over Hatch and his Congressional inquiry. You'll find that any law that comes out of it will further stifle innovative models for music distribution down the road. Pay attention to your history before you go crying to Congress to fix your problems for you.
I think the problem derives from you think "true" means. When you prove that T is undecidable, you're formally proving that there is no finite sequence of statements that prove T, and no finite sequence of statements that prove "not T". In other words, you can't prove that every system containing the axioms has a counterexample. There is, in fact, a counterexample in a suitably extended system!
The example of (non-)Euclidean plane geometry and the parallel postulate is a good one. That axiom is undecidable wrt the other axioms. In other words, it's not provably true, but you can't prove that there is a counterexample in every logically consistent geometry that includes the other axioms. Therefore good ol' high school geometry tacks on the parallel postulate, but non-Euclidean geometries (which contain all the other axioms) define lines and points such that there is greater/less than one parallel line through the point.
Conversly, the statement "for all x, x>=2" is provably false in every system which obeys Peano's axioms for the natural numbers, because the element known as "1" is a counterexample.
If you show that a statement T is undecidable, then it is "true" in the sense that there are no counterexamples, but the "way that it goes" is up to you. You can extend your system into two logically consistent systems: one in which T is provable (by making T an axiom, for example), and one in which T is false (by making "not T" an axiom).
So, in conclusion, proving the undecidability of T does not constitute a proof of T.
Several of Hilbert's problems in 1900 were of the form "find an algorithm for such-and-such", where such-and-such was something like "determining whether a polynomial of arbitrary degree and arbitrary number of variables has integer roots." These problems were closed, but not strictly solved, since it was proved that there were no such algorithms to do what he wanted.
I would find it extremely interesting if, in the 21st century, it were shown that many of these conjectures were also proved to be undecidable. It would certainly explain why some of them have taken so long to figure out.
If you show that the conjecture is undecidable, you haven't proven or disproven it - so do you still get the million $$? :)
In both cases, the average class/section will be taught by a graduate student and you'll be quite lucky if the professor even knows the names of ten people in the entire course.
That's a laugh. My freshman physics recitation (8.01) was taught by Alan Guth (an almost-certain Nobel prize winner in Physics for his work on cosmology). He knew my name within two class sessions - but that was easy, because there were only 18 of us in the recitation.
Maybe that was a fluke, but I don't think so - because my introductory computer science recitation (6.001) was taught by Rod Brooks. Yeah, the guy who created AI robots with insect-like intelligence (his current project is a artificial human).
Or let's take a look at my sophomore year, when my Computer Systems Engineering recitation was taught by Ron Rivest, "the R in RSA." I enjoyed that so much I took his Computer and Network Security class the next term. And he remembered me!
Mind you, these are just recitations - the lectures were taught by equally luminous professors. Like my 8-person topology seminar with James Munkres, who is basically the top guy in the field. Or my graduate AI class with Patrick Winston. Or any of several classes by Marvin Minsky or Noam Chomsky.
Lest I be accused of name-dropping, this illustrates the point quite clearly: you really can get a personalized education from the very best in a field if you go to a Really Expensive School. If you have the opportunity, go for it!
If you're looking for straight answers to the kinds of questions that you listed, check out Harry Browne's site, and the Libertanian Party site. Whether or not you agree with his/their views, you won't be treated like a fool; you'll get straight answers. Hopefully you'll like the answers and be persuaded to vote Libertarian, but if not, you can at least make an informed decision.
Any dialect of LISP (e.g., Scheme) will treat tuples (OK, pairs) as first-class objects. Even better, programs themselves are essentially complex structures built from pairs. This is all a consequence of LISP's incredibly simply syntax (even simpler than Python, I'm sure). That makes LISP a great language for writing programs that manipulate programs (evaluators, compilers, etc.). I've seen simple compilers implemented in hundreds (not tens of thousands) of lines of LISP code. If you like Python's ability to built complex structures from basic pieces, you'll really like LISP.
In a class called "Computer and Network Security" taught by Ron Rivest, a group of students did an interesting project on how one might completely destroy the security of a Linux machine. To wit:
One could write a kernel module that doesn't allow itself to be listed with lsmod. It even steps on certain system calls so that the file containing it doesn't get listed with ls. It also adds itself to several key executables but alters the system calls so that the file sizes don't appear to change. It provides a backdoor that allows a cracker to own the machine remotely, and disables any kind of logging that would result from the cracker's actions. This module could be sent through any kind of buggy network daemon, and spread like a worm. The machine's admin would have a hell of a time even discovering that the machine was infected! It seems that running a virus in kernel space gives you significantly more power than even running it as root.
Of course, the students didn't implement this virus/trojan/worm - it would require some crazy skillz, but they really had their bases covered when it came to design.
It should be noted that this kind of thing could probably pulled off on many different types of operating systems, and might be even more successful since commercial systems have more homogenous kernels (I can imagine all kinds of "unresolved symbol" errors with all the custom Linux kernels out there...)
During a 1:20am commercial break of "Late Night w/ Conan O'Brien" here in Michigan, there was a 10-second news bite delivered by the usual tired-looking local newsperson. After mentioning some Texas schoolteacher wanted for murder, she said (approximately) "a California judge has denied a restraining order for software that allows copying of DVDs."
While I'm sure none of us would be happy with the content and length of the report, it does show how big of an event this was! I'm sure that the great turnout by interested and well-behaved parties plays a big part in the news coverage that we're seeing.
Let's say, for the sake of argument, that the NSA made this announcement. The inevitable response?
"The NSA must have found some huge security flaws in Linux! They're trying to get us to run it so they can packet-sniff our diffs! Then they can have the newest kernel releases before the Slashdot effect bogs down kernel.org! Conspiracy! (Run BSD instead!)"
I'll quit while I'm ahead, now that I've pissed off just about every special-interest group here...
An idea I've been batting around for awhile: micro-payments in conjunction with open-source software. The software developer maintains a website with documentation, links to archived mailing lists, and packages with binaries and source code. In order to download the binaries or source from that site, you make a micropayment of, say, ten cents to the lead developer/organization behind the project. With all the people using the software, there would be enough money coming in to prevent the developer from going broke, and maybe enough to be a good chunk of supplemental income.
Nothing else would change: the software would still be free (so it might be available for free from lots of other ftp and web sites), but by going to the "official" distributor, you'd get the latest version and be able to make a small, but appreciated, contribution. Right now it's just too inconvenient to support free software financially, and in order to make a difference, you've got to hand over a much bigger chunk of cash. This would allow a developer to make a difference for himself, and probably a lot more money too.
Of course, in theory this could all be done with banner ads on the official site. But that probably doesn't bring in nearly as much cash. I can't think of a real good reason why more people aren't already doing this, actually...
At any rate, this doesn't become practical until there is a solid micropayment infrastructure set up. Wake me up in ten years and we'll see how good my predictions were...
Gosh, all I see is whining about how this is "old news" - I don't recall ever seeing exactly what license XFS was going to be distributed under.
Regardless, let's showing a little fscking gratitude (forgive the pun) to SGI! They're supporting Linux on their workstations, their developers have always contributed to the kernel, and now they're freeing a huge, important chunk of code that is desperately needed and would be a massive development effort to start from scratch! Hoorah for SGI!
So what if it's a pre-emptive strike against IBM's journaling file system? More free software is good free software! Now we have more choices, and people can pick what's right for their uses, and may the best product "win", because in the end, we're all going to win. Huzzah! :)
Well, you can compile e-lisp code (EMACS's dialect of lisp) into a sort-of e-lisp bytecode. Check your site-lisp directory; it probably has a mixture of .el and .elc files - the .elc ones are precompiled.
To merge with another thread farther up the discussion, this is exactly why the power to create a post office was written into the US Constitution. It was believed that the social benefits of having an accessible, universal communication device that by definition served the entire nation outweighed any savings from local delivery efficiencies.
Even if I agree with your entire post, you haven't given a single reason why independent, non-governmental businesses should be locked out from providing first-class service, or package delivery at as low of a price as they can provide. The entire thesis of my original post, if you look at the first paragraph and the first two items, was that these laws are ridiculous and hurt the consumer (keeping in mind that "repealing the two-times law" != "destruction of USPS through market forces" != "destruction of USPS by act of law"). The USPS, large delivery services, and local delivery services could all coexist, that is, if federal law didn't effectively eliminate the possibility of local delivery services. I repeated these issues in my rebuttal. Why have none of the replies come even remotely close to addressing this issue??
What kind of guarantee are you offering? If private businesses charge 34c per letter are you personally going to reimburse the letter senders of America one billion dollars?
Yes, of course I will. Just send the bill to the me, c/o Dept of Dumb Rhetorical Questions. Now that we're both done being silly, let's get the heart of the matter.
Or are you offering the same guarantees that accompanied the other deregulations and mergers that have thus far failed to pass along any cost savings to customers (i.e. none whatsoever)?
Arguments about the value of mergers aside, you'll notice my original message stressed the unnecessarily high cost of local delivery, which could otherwise be handled by small businesses.
Question: how much of the mail you send goes farther than 100 miles? People tend to send bills, letters to friends and relatives, and "paid by sender" mail. Bills go to their local phone company, local cable company, etc. Letters and greeting cards to local friends are also common. "Paid by sender" mail doesn't even enter the equation.
Now let's talk business mail. Lots of businesses have a couple of offices or locations at various places across town (I can name a dozen such businesses in my hometown). Right now, they can either hire somebody to drive small stacks of letters around, or they can pay the first-class rate and have their mail delivered in 2-3 days. Without the first-class restriction, they could contract with a local mail delivery service and possibly save a lot of money.
From looking at their corporate report it seems like the only reason FedEx is still is business is because of the "two-times" rule. They aren't efficient enough to operate with the same cost structure as the USPS, apparently.
Great - so not only is the two-times rule keeping out new competitors and keeping the USPS entrenched, it's also a form of corporate welfare for FedEx. After all, FedEx wouldn't like it too much if a competitor arrived and offered the same reliability, at half the price. Thanks heavens we have the two-times law to prevent that from happening!
[Note: that prices might come down and other companies might enter the market is also not a fact.]
It sure isn't. But eliminating price-floor laws sure won't make prices go up. I think you're missing the point: there's no reason to support laws that prevent businesses from entering markets like this, but it sounds like that's exactly what you're doing. You say that my "guarantees" may not happen, but that's not an argument that the two-times law is, in itself, good.
There's no compelling reason to give preference to any particular service. If the two-times law and its friends are repealed, and FedEx still charges the same prices, and nobody else springs up to offer cheaper service, then nothing has been lost. But if local mail and package services do appear and flourish, then everyone wins. The USPS isn't going anywhere: it's been around for almost 200 years, and it's a government agency (we know how hard those are to get rid of). So let's just allow people and businesses the choice of service, price, and reliability that they want.
The USPS may not be a "monopoly" in the classical sense of the word, but there are a lot of federal laws that ensure that it stays entrenched, and that bar competition. For example:
The bottom line is, some people hate the service the USPS offers. Those people are already convinced. To those who like the service, I point out to the countless laws and benefits that favor the USPS, keeping it entrenched no matter how poor its service may get in the future, and locking out private businesses from doing an even better job at a cheaper price.
Hey everyone, this is not encryption. Why? The message itself is never obfuscated or transformed in any way, instead it is merely hidden among a lot of other DNA, on a very small dot that wouldn't be noticeable under brief scrutiny. The only similarity between this and encryption is the existence of a secret (the base-pair sequence of the DNA strand "caps") between two parties.
There is a term for this type of message-hiding, but it's eluding me (someone around here knows it, I'm sure...). Other popular examples include:
Again, this is different from encryption because the important message is hidden in an otherwise benign and useless message. So the hard part of breaking the system is knowing whether a message is hiding another message. Once you know that, breaking the scheme is pretty trivial - there's no computational complexity behind the system.
There have been a few good answers to this question in this thread, but there's one thing that hasn't been pointed out yet: journaling file systems don't (immediately) overwrite a file when it is changed.
To elaborate, imagine a long tape that represents your hard drive. The tape is written from left to right. When a file is changed, the new version is appended to the end of the existing data, while the old version remains "untouched" farther to the left. When the kernel has finished updating all pending file writes, it can write a "checkpoint" at the end of the existing data. Essentially the checkpoint says "everything up to the point is kosher." If the disk gets really full, then the filesystem can double-back and overwrite the really old data at the beginning of the tape.
Now, let's see how this works to help recover from crashes; say the computer crashes as it's writing out a file to disk. In a conventional filesystem, a lot of things could go wrong: it could have been overwriting the old data, but finished only half of the job. Then, at best, you've got a corrupted file with a hybrid of new data and old data. The file allocation table may not have been updated, so the file may be completely lost. It's a bad situation.
Conversely, if the crash happened with a JFS, the computer would run an "fsck" and look for the last checkpoint. It's guaranteed that all data preceding the checkpoint has integrity. Then the filesystem would just work from that checkpoint and ignore any non-checkpointed data. This can still lead to some data loss, but never to filesystem corruption.
Of course, this is a simplified account, and there are implementation details. But that's the gist of it.