In other words, "A is no harder than B": if we had a hypothetical device to solve B, then we could also solve A.
Two problems are Turing-equivalent if each is Turing-reducible to the other.
Since Friedberg and Muchnik's breakthrough, the structure of the Turing degrees has been studied in more detail than you can possibly imagine.
Here's one of the simplest questions: if two problems A and B are both reducible to the halting problem, then must there be a problem C that's reducible to A and B, such that any problem that's reducible to both A and B is also reducible to C? But this is the point where some of us say, maybe we should move on to the next topic...
This question was first asked by Emil Post in 1944, and was finally answered in 1956, by Richard Friedberg in the US and (independently) A. Unfortunately, the resulting problems are extremely contrived; they don't look like anything that might arise in practice.
And even today, we don't have a single example of a "natural" problem with intermediate Turing degree.
This is important to determine what Turing actually accomplished.
Now, a Turing-degree is the set of all problems that are Turing-equivalent to a given problem. Well, we've already seen two examples: (1) the set of computable problems, and (2) the set of problems that are Turing-equivalent to the halting problem.Can we prove that this super halting problem is unsolvable, even given an oracle for the ordinary halting problem? We simply take Turing's original proof that the halting problem is unsolvable, and "shift everything up a level" by giving all the machines an oracle for the halting problem. Indeed, Friedberg and Muchnik actually proved a stronger result: that there are two problems A and B, both of which are solvable given an oracle for the halting problem, but neither of which is solvable given an oracle for the other.Everything in the proof goes through as before, a fact we express by saying that the proof "relativizes." Here's a subtler question: is there any problem of intermediate difficulty between the computable problems and the halting problem? These problems are constructed via an infinite process whose purpose is to kill off every Turing machine that might reduce A to B or B to A.How could the hidebound Turing reactionaries possibly object?(It reminds me of the joke about the supercomputer that was so fast, it could do an infinite loop in 2.5 seconds.) We should immediately be skeptical that, if Nature was going to give us these vast computational powers, she would do so in a way that's so mundane, so uninteresting. But admittedly, to really see why the hypercomputing proposals fail, you need the entropy bounds of Bekenstein, Bousso, and others -- which are among the few things the physicists think they know about quantum gravity, and which hopefully we'll say something about later in the course.(Incidentally, the answer to the question is no.) Alright, the main philosophical idea underlying computability is what's called the Church-Turing Thesis.It's named after Turing and his adviser Alonzo Church, even though what they themselves believed about "their" thesis is open to dispute!Already there's an obvious question: what sort of claim is this?Is it an empirical claim, about which functions can be computed in physical reality?But in my view, so far there hasn't been any serious challenge to the original Church-Turing Thesis -- neither as a claim about physical reality, nor as a definition of computable.' There have been plenty of non-serious challenges to the Church-Turing Thesis.In fact there are whole conferences and journals devoted to these challenges -- google "hypercomputation." I've read some of this stuff, and it's mostly along the lines of, well, suppose you could do the first step of a computation in one second, the next step in a half second, the next step in a quarter second, the next step in an eighth second, and so on.