October 27th, 2004

Reducability, Barry&Oracle


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.
  1. If machine M doesn't decide language L, then L can still be decidable.
  2. If L is decidable then L is recognizable.
  3. If L is recognizable, then L isn't necessarily decidable.
  4. If L is recognizable, then L is enumerable.
  5. If L is enumerable, then L is recognizable.
  6. If L is decidable, then L' is recognizable.
  7. If L and L' are recognizable, then L is decidable (and so is L').
  8. There is an L that is not recognizable.
  • Current Music
    Type O Negative, 12 Black Rainbows