• Mood: happy
• Music: Type O Negative, 12 Black Rainbows

Reducability!

anniesj makes negative comments, over the line to a few of her readers, about Bush. Secret Service pays them a visit.

Speaking of slamming the administration (congrats runstaverun), I wish I could have seen my great great great grand boss last night.

But instead I reviewed the 8 fundamental truths of the universe, and learned what is possible with an oracle on your side.

0. If machine M doesn't decide language L, then L can still be decidable.
1. If L is decidable then L is recognizable.
2. If L is recognizable, then L isn't necessarily decidable.
3. If L is recognizable, then L is enumerable.
4. If L is enumerable, then L is recognizable.
5. If L is decidable, then L' is recognizable.
6. If L and L' are recognizable, then L is decidable (and so is L').
7. There is an L that is not recognizable.