But what's more puzzling is @NeildeBeaudrap's comment after the answer and @GeorgeChen's unresponsiveness to my question. I don't know why he did that. Was my question too trivial @user21820?
@user170039: There's one more interesting bit; if you have the halting oracle, you can decide the entire theory of the natural numbers. The halting oracle is so low in the hierarchy of computability that this fact feels slightly strange.
