I'm just starting to learn computability. Some treatments of the subject use a relation they call $T$, which I think is called the universal recursive relation. It's defined something like this (http://www.its.caltech.edu/~jclemens/courses/02ma117a/handouts/handout6.pdf p. 3):
$T_n(m, c, x_1, \ldots , x_n) \iff \operatorname{Final}(m, c)\land c$ is a computation starting from $\ast 1^{x_1}B\cdots B1^{x_n}$, i.e. $c$ codes a halting computation for the machine m computing a function with inputs $x_1, \ldots , x_n$
As I understand this relation, it holds when and only when the program with code $m$ and input $(x_1,\ldots , x_n)$ halts with output $c$.
This relation is said to be recursive (and primitive recursive - see p. 2 of the handout I linked). What I don't see is how this is compatible with the halting problem being undecidable. If the relation was recursive, couldn't you use it to check whether the program halts for some given input? (I've probably misunderstood what the relation is but I can't see how else to interpret it.)
Thanks a lot.
You have misunderstood $c$ here. It is not an output. It is a complete description of a computation, including all the state transitions, tape head movements, and tape modifications that the machine makes on its way to the final state.
It is computable to check whether a single step of this long description is correct. Each step contains a description of the tape, where the tape head is, the machine's start state and its end state, and which symbol the machine will write. Checking a single step means to check to make sure the tape matches the description in the previous step, except for the one tape symbol that was changed; checking that the one symbol was the one under the tape head; checking that the new symbol is the one that the machine's transition function said it should write, given its state and the value of the old tape symbol; and so on.
$c$ is a long list of such steps, and since it is finite, and the steps can be checked one by one, $c$ can be checked in its entirety.
Given a machine $m$, an initial input, and a proposed computation $c$, one can check to see if the machine will in fact compute the way $c$ says and reach a final state at the end. $c$ describes a particular computation, of say $S$ number of steps, and if $m$ would actually compute for longer than $S$, you can easily detect that and halt and report that $c$ is not an accurate description of what the machine would do.
In particular if $m$ fails to halt on the given input, you can still be sure to calculate that $c$ was an inaccurate description of what $m$ would have done, and halt and say so.
This doesn't help you in deciding if the machine would ever halt. If $m$ never halts, then $c$, being finite, is necessarily an inaccurate description of what $m$ would do, and you can certainly detect this. But knowing that $c$ is an inaccurate description of the behavior of $m$ is obviously no use at all if you want to know what $m$ actually does!