Skip to main content
Loading Explore guides…
Turing Degrees · Acedra
Home
Explore
Mathematics
Turing Degrees
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
55 segments
Copy
Hide video
0:00
Hello! In this video, I'd like to introduce you to the Turing degrees. They're a really neat mathematical structure that comes from studying relative computability: if we could give our computer magical access to one noncomputable function, what other noncomputable functions would this give us the ability to compute? This gives us an "is more powerful than" ordering on functions, and the study of
0:26
the properties of this ordering is part of the field of recursion theory. There are a number of really beautiful proofs in this field involving progressive constructions: working out an infinite sequence entry by entry to make it satisfy certain desired properties, and I'd like to share some of these proofs with you. To get the most out of this video, it will help to be familiar with the halting problem,
0:52
the notion of computability, what it means to be a partial ordering, and also I sneakily mod out by an equivalence relation in this video, so if you're familiar with that, all the better. Our goal here is to reason about what sorts of functions a computer can compute. When trying to reason mathematically about computability, one can of course talk about Turing machines or register machines or some other mathematical formalism, but nowadays you can also get really good intuition
1:22
for formal computation just by thinking about your favorite computer programming language. But we're going going to have to modify our notion of computer program ever so slightly: In this field of study, it is traditional to restrict our attention to functions from the natural numbers to Booleans, 0 or 1 with 0 representing false and 1 representing true. This restriction is quite nice: we can view these functions as infinite sequences of 0s and 1s,
1:53
or as sets of natural numbers, specifically the set of inputs making the function true. But we don't actually lose much making this restriction: if we want to analyze functions that take in more complicated data structures as input, we can represent those data structures as natural numbers, in a way similar to how computers represent those data structures as sequences of 0s and 1s, and then decode those natural numbers inside of our program.
2:24
Having only one bit of output also isn't more than a mere inconvenience in terms of what we can program. If we want more complicated outputs, we can represent y = f(x) as a new function g which takes in two inputs x and y and tells us if y is the correct output given the input x. This process is called relationalization, and we can just carefully check through all possible outputs until we find the correct one.
2:52
We'll also need to limit our programming language's access to certain functions, such as our random number generator. Specifically, we would like to study computable /functions/, function here in the mathematical sense: the same input must give us the same output every time. So, we need our function to be deterministic: it should have no access to data that might change each time the program is run, such as the random number generator, the current time, or active user input.
3:24
Real programs run on real computers only have access to some finite, limited amount of memory, and as a concession to that may put limits on the size of the natural numbers they store, or how long arrays can be. But we're mathematicians, we're perfectly willing to allow our programs access to as much memory as they want, not just through arcane memory allocation routines, but also, why not, in terms of the size of integers that we're allowed and
3:54
also the size of arrays that we're allowed. In fact, this actually makes the math easier to do since we don't have to constantly keep track of how much memory our programs take to run and if they're going to overfill the available memory: it's just one less thing to have to worry about. Computer programs are just strings, which again, computers store in binary and so we can interpret as corresponding to natural numbers. As such, it makes sense to talk about
4:24
the n-th computer program: take the number n, translate it into a string, and interpret that as a computer program. I'll call this function Phi_n. So Phi_n(x) will be 0 if the program, when we input x, gives us 0, and it'll be 1 if the program gives us 1. It's also possible that the program will never give us an output, that is, it will never halt, in which case, I'll define Phi_n(x) to be infinity. There are many ways for a program not to halt. Most simply,
5:01
it could get caught in an infinite loop: if our program ever winds up in exactly the state it was in before, it's just going to keep looping around and never terminate. But we could, for instance, write a program that searches for a counterexample to Fermat's Last Theorem in which case it's never going to halt because there's no counterexamples to Fermat's Last Theorem but proving it's never going to halt, well that's very difficult.
5:28
Note that most strings are nonsensical programs, so we expect a lot of these programs to not output anything, in which case, again, we'll define Phi_n(x) to be infinity as well. The key thing here is that any computable function from the natural numbers to {0,1} will be Phi_n for some n, and in fact for many n, and we're really not concerned if lots of these Phi_n are redundant or uninteresting. One might want to reduce the redundancy in this list,
6:00
but doing so makes it much harder to convert back and forth between indices and functions Phi_n. And that's really the key thing: we're going to want to be able to convert back and forth very easily between natural numbers and the programs that they correspond to. Our list Phi_n will contain every computable function from the natural numbers to {0,1}, but it won't contain all functions from the natural numbers to {0,1}.
6:31
There's an easy proof of this fact: there are uncountably many functions from the natural numbers to the set 0,1. This is usually shown by considering these functions as infinite binary sequences. On the other hand, there's only countably many Phi_n, one for each n, so we're actually going to miss out on most of the functions from the natural numbers to {0,1}. This proof is important, but it's a little disappointing:
6:58
it doesn't give us any sense of what these noncomputable functions wind up looking like. Let me show you how we can explicitly construct a noncomputable function d. Remember that we can also think of d as an infinite binary sequence. I'll start by keeping track of a list of conditions that we would like d to satisfy. First, we would like the function d to not be the function Phi_0. There should be some
7:26
input that we can input to the function d to get a different output than if we input that input into the zero-th computer program. Similarly, we also want d to not be Phi_1, to not be the function computed by the first computer program. And so on and so forth. To make sure d satisfies our first condition, I'm going to assign the value of d at 0 to not agree with Phi_0. Specifically, if Phi_0(0) is 0, I'd like d(0) to be 1. If Phi_0(0) is 1,
8:11
I'd like d(0) to be 0. Phi_0(0) could also be (and probably is) infinity, in which case I can choose d(0) to either be 0 or 1, let's say that if this case happens we're always going to give a 0. Next, I similarly want to make sure that d disagrees with Phi_1. Specifically I'm going to want d(1) to not be equal to Phi_1(1). And that's going to force these two things to be different as functions. And then of course
8:46
I should pick d(2) to not be equal to Phi_2(2). And so on and so forth. All told, if we construct our function d in this way it will give us a d which disagrees with each of the Phi_n and thus isn't any one of them: a noncomputable function. This might seem a little strange: all our function d is doing is, given an n, telling us a value that is definitely not Phi_n(n). This seems computable -- if the n-th computer program on input n,
9:23
if Phi_n(n) actually does halt, then we simply run the computer program until it halts, look at the value that it outputs and then output the opposite value. But, if the program doesn't halt, it might be the case that we never figure that out. While the program is running we're left in kind of a limbo: we don't know if our program might eventually output something. If Phi_n(n) eventually outputs a 0, we need
9:54
our d to return a 1. And otherwise we should return a 0. But while we're waiting on Phi_n(n), we don't know which situation we're in and so we don't know what to output. So far this has all been fairly standard computable/noncomputable stuff, but here's the clever bit: what happens if we add our noncomputable function d to our programming language, allow our programs to call d(x) for any natural number x and
10:27
get an accurate 0 or 1 in response? We like to call these new functions we're adding oracles, since they can grant us knowledge a mere mortal computer program cannot calculate for itself. Again, we can define Phi_n with oracle d via the same process: we can enumerate the programs in our new, augmented, programming language, again, we're just adding one new function, that's not a big deal, and we'll let Phi_n with oracle d of x be either 0 or 1 if the program outputs 0
11:03
or 1 on input x, and we'll let it be infinity if the program doesn't halt or is incoherent. So is this all? Does adding in this one noncomputable function to our programming language suddenly make everything computable? Well, no. The cardinality argument works exactly the same: there are only countably many Phi_n with oracle d (and this is, by the way, going to include all of the functions which are given by programs that don't make use of d,
11:36
those are also included as part of this, it's just a program that doesn't use one of the features that's available), and there are countably many functions, countably many n, countably many Phi_n. So again there are going to be functions that are not computable even with access to our oracle d. And again, we can explicitly construct a new function d' which isn't any one of our Phi_n's with oracle d, just by adding some superscript d's to our argument from before.
12:11
And of course, we can continue this process to produce a d'' which is noncomputable even with access to d', and a d''', and so forth. It will be useful to be able to talk about some functions being even more noncomputable than others. Given functions A and B from the natural numbers to Booleans, we say that A is computable from B, which we write as an inequality with a T subscript, if there is a computer program
12:42
to compute A in our favorite programming language augmented with the function B as an oracle. That is, being able to call B as a function, being able to ask our oracle for whatever values of B we need, gives our programming language the ability to compute A. And again, we can translate back and forth between programs in this language where we've augmented by an arbitrary oracle B and the natural numbers, and I'll call these programs Phi_n with oracle B.
13:15
And this notation, saying that A is computable from B, is just saying that there exists an n where A is the n-th computer program with oracle B. That these two functions are the same.
13:30
The or-equals-to here is a little bit misleading: this relation isn't antisymmetric. It's very easy to have two functions that have the same data, just presented in a different way, two functions that each allow us to compute each other. If we can compute A from B and we can compute B from A we say that A and B are Turing equivalent, and we write it like this. For instance, if a function A is computable, then it is computable from anything:
14:03
we just completely ignore our oracle function B and just use the program to calculate A directly. As such, any two computable functions are computable from each other, and so they must be Turing equivalent. In order to make our relation antisymmetric, we need to consider all Turing equivalent functions as a single unit, which we call a Turing Degree. The Turing degree of a function is the set of all functions that are Turing equivalent to it,
14:34
so Turing degrees are just maximal collections of functions that are all equivalent to each other. So this gives us a mathematical structure: the set of Turing degrees with Turing computability as a notion of ordering. And whenever you have a mathematical structure like this, it's always fun to study its properties. We can easily see that Turing computability defines a partial ordering: any function can
15:00
be computed from itself, so we have reflexivity. We enforced antisymmetry by considering any two Turing equivalent functions to represent the same Turing degree, (this is a bit of a cheat, but it gets the job done). And Turing computability is transitive: if we can compute A from B and compute B from C, then we can combine these two programs that do these to compute A from C. There's also, as we've seen, a least Turing degree: any computable function is computable
15:36
from anything, and all computable functions are equivalent. So the computable functions form a Turing degree which is less than or equal to anything. We denote it by 0: you can think of this as picking out the constant function 0 as a representative of the computable Turing degree. Also, we can combine the computing power of any two functions. If we have two functions f and g, we can combine them into a function h that gives us the values of f on even inputs and
16:09
the values of g on odd inputs. That is, we're interlacing the values. This h can of course be used to compute both f and g, you just access the correct values of h and it tells you the values of f and g that you're looking for and it's the the least powerful such function: a least upper bound in our partial ordering. The Turing degrees are also equipped with what's called a jump operation. Given a function f, we define the jump of f as the function f' which solves
16:45
the halting problem on programs with access to oracle f. That is, f'(n) is 1 if the n-th program with oracle f halts on input n, and 0 if it doesn't. This operation is well-defined on Turing degrees: if we take any two functions in the same Turing degree, their jumps will also be Turing equivalent, and so it makes sense to talk about the jump of a Turing degree. The jump of a function is strictly more powerful in terms of computability than the original
17:21
function. We can, by doing some cheap tricks, compute our original function from the jump, and we can't compute the jump from the original function. This gives us, for instance, a chain of landmarks in the Turing degrees: starting from the bottom you have 0, the degree of the computable functions, then 0-jump, which solves the halting problem for computable functions, then 0-jump-jump which solves the halting problem for those functions, and so on and so forth.
17:53
The construction that we did earlier of the non-computable function d is another way of describing the Turing jump. d is Turing equivalent to 0-jump, d-prime is Turing equivalent to 0-jump-jump and so on and so forth. One might wonder: are the Turing degrees linearly ordered? That is, given two degrees, is one necessarily Turing computable from the other? Given two functions, is one necessarily strictly more computationally powerful than the other?
18:26
The answer is no: there are two Turing degrees corresponding to functions f and g neither of which can compute the other. To find these functions, we're going to do the same thing that we did before when constructing our noncomputable function d: we're going to list out a collection of conditions that our f and g need to satisfy, and progressively construct our functions f and g to ensure they satisfy those conditions.
18:55
And these conditions are really straightforward. In order to ensure that f is not computable from g, we need to make sure that f is not given by the 0-th program with oracle g: that these functions disagree with each other. And we need to make sure that f is not given by the 1-st program with oracle g, and so on and so forth. Together all of these conditions will ensure that f is not given by any of the computer programs with access to oracle g.
19:27
And, vice versa, in order to ensure that g is not computable from f, we need to make sure that g is not given by the 0-th program with oracle f, or the 1-st program with oracle f, and so on and so forth. So, again, to make sure all these conditions wind up being satisfied, we're going to construct f and g progressively. At each stage of our construction we'll start off having worked out some initial
19:55
set of values for f and g, if we're thinking of them as infinite sequences of 0s and 1s, we'll have worked out some finite initial part of these sequences, and then at each stage, we'll work out some more values of f and g to ensure that they satisfy the desired condition. Each condition will get its own stage: we'll go through this list of conditions from left to right then top to bottom
20:26
to make sure we get to all of the conditions so that in the limit we wind up working out all of the values of f and g, and we'll have worked out an f and g that satisfy all of these conditions. So let's look at a step in this construction of f and g. Suppose we've worked out the values of f(0) through f(n) and g(0) through g(m) and we're now at the step where we want to extend our known values of f and
20:58
g in order to ensure that, let's say, f is not given by the k-th program with oracle g. And again, we're going to have to do this in reverse in some of the other steps to make sure that g is not given by the k-th program with oracle f. But it's going to be the same process, just with the roles of f and g reversed. To do this, we simply have to pick f(n+1) to disagree with Phi_k with oracle g of n+1: to disagree with the result of running the k-th program with oracle g on input
21:36
n+1. That will make sure that f is not given by the k-th program with oracle g. But, unlike in the case where we were constructing our noncomputable d, right now we might not have worked out enough values of g to figure out what Phi_k with oracle g of n+1 is. It might be the case that this program, the k-th program, asks what g(m+2) is, for instance, or worse, maybe it asks for a bunch of g values that we haven't worked out yet,
22:11
and which g values it asks for depends on some of those g values we haven't worked out yet. So we're going to have to work out some new values of g in addition to new values of f. We fall into one of two cases: First, it could be the case that there's some extension of g that ensures that when we run the k-th program with oracle g on the input n+1 we get some value, either a 0 or a 1. In this case, the k-th program on input n+1 has a finite run:
22:47
it goes through a finite sequence of steps because it finishes and returns a value in some finite amount of time. So this program can only call the g function finitely many times, it only has enough time to call the g function finitely many times. So we just need to fix those values of g. So, fix those values of g and that will determine Phi_k with oracle g on input n+1,
23:16
and then we can just make sure that f disagrees with Phi_k with oracle g by making sure that it gives us a different value on input n+1.
23:27
The second case is that there's no finite extension of g that ensures that, when we're finished constructing our g, the k-th program with oracle g on input n+1 actually returns a value. In this case, no matter how we wind up extending our current partial g, our partial sequence, to a complete g, a complete sequence, a complete function, the k-th program with oracle g on input n+1 definitely won't output anything.
24:00
And this is easy to see by contradiction. Suppose that it did. Then the program would have a finite run, and it would only run through finitely many program steps, and so could only call g finitely many times, so specifying the finitely many values of g that actually get asked about would be enough to ensure that the program ran like it was running, that is, it would be enough to ensure that the program returned a value, contradicting our assumption.
24:32
So in this case the k-th program with oracle g on input n+1 will never return a value. So we can pick f(n+1) to be either 0 or 1 and it will disagree with the program, because the program doesn't return anything. Let's pick 0 just so that we're not making anything more complicated than necessary. So that's the proof: we're just going back and forth between these conditions, slowly working out more and more values of the functions f and g, so that in the limit,
25:03
we've worked out all the values of f and g and ensured all of these conditions hold, thus producing two functions neither of which compute each other. One can actually get pretty far in the study of the structure of the Turing degrees with more and more advanced progressive constructions like the ones in this video. For instance, you can easily modify our proof that there are two incomparable functions to find countably many incomparable functions.
25:34
Recursion theorists have come up with a very general tool for describing these sorts of constructions called a "forcing". The forcing proofs that I've seen, and that's not very many of them, in recursion theory, were all hiding a really nice mechanical progressive construction at their hearts. And this hiding, this being able to do these proofs without having to think about the mechanics of their constructions, on the one hand is really useful because it allows researchers to
26:04
come up with new proofs with one less thing to have to think about, and it makes some really clear connections between different proofs that use forcings. But it's also a real detriment, particularly to someone unfamiliar with the field, since it hides what's really going on, this really nice construction, by phrasing it in terms of something that a novice won't be familiar with. And this sort of phenomenon isn't specific to recursion theory:
26:34
in lots of different fields of math, it's common to make broad, powerful, generalizations that hide a simple idea at their hearts, making it really difficult to understand what's going on if one doesn't know the notation and the key ideas. My advice if you encounter such notation is this: try a bunch of examples, particularly specific cases where you already understand what's going on, or have alternative ways of proving results.
27:05
All that being said, getting a complete picture of the Turing degrees is really tricky: they're a very complicated partial ordering. But some properties that might help get you a better sense of what this partial ordering looks like include: You can find, actually, a continuum-sized collection of pairwise incomparable Turing degrees, so our diagram for the Turing degrees is actually very wide. There are minimal degrees, so degrees that are strictly above 0,
27:41
but there's no degree in between them and 0. Every countable partial ordering can be embedded in the Turing degrees, so you can find all sorts of configurations in there. And the set of degrees computable from a particular degree is countable. And this one's actually really easy to see: there's only countably many programs, and so there's only countably many functions which are computable from a specific function.
28:16
So, thanks for watching! I don't really consider myself to be an expert in recursion theory but I thought that this proof was just so nice and this idea of a progressive construction for a proof was so nice that I wanted to share this with you. Let me know if you have any questions or comments below, and I'll try my best to answer them, and be kind to each other!
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat