I am going to skip the number theory and concentrate on computability, in particular

"the $n$th Turing machine halts" (we can also forget the statement and consider just its "truth value" function $P:N\to\{0,1\}$.

It is completely inappropriate to use a discrete two-element set for the "truth values" of such a proposition.

We can **swap** $0$ and $1$.

We **cannot** swap the statements "the $n$th Turing machine halts" and "the $n$th Turing machine runs forever". They are fundamentally different: we can just wait for the first to happen and then if it does we know that it is true. We can never know that the second is true.

Granted, you can add an oracle to your Turing machine that can say whether the $n$th ordinary Turing machine halts, but it does not answer the question for the enhanced machine. A similar argument applies to "Turing machines" for (finding proofs in) stronger logical theories, which I guess is what the second question and Noah's answer are about.

However, the point that I want to make here is that a gratuitous confusion is introduced in the meanings of words like **decidable** and **recursive** by imposing two-valued logic on them.
At least say **semidecidable** and **semirecursive** (or, better, **semicomputable**).

In the case of computable functions, the Kleene normal form theorem says that any semicomputable predicate $\phi(n)$ is of the form
$$ \phi(n) \iff \exists h.T(p,n,h) $$
for some code $p$, where $T$ is a (standard) decidable ternary predicate.

This means that, in the appropriate truth-value object for such predicates, which I call $\Sigma$, any truth value is a computable disjunction of decidable ones ($\bot$ and $\top$).

Reconsidering the second question, trying to prove that a statement follows from a given theory is like running a Turing machine to search all possible proofs.

(This is a pretty daft way of doing mathematics, but then computability theory was traditionally written in a similarly infeasible manner. With small modifications it can be made to look much more like modern practical computation. Using binary trees instead of integers makes a huge difference.)

If we are going to discuss which symbols to use for true and false then I suggest the following. In the second question there is an object language (statements that might be deduced from theories) and a metalanguage (searching for proofs). We might think of the object language as a kind of algebra, so it makes sense to write $0$ and $1$ for its truth values, especially if the theory under discussion is a classical one.

In the metalanguage success and failure are not interchangeable ideas, so my $\bot$ and $\top$ are preferable and they certainly belong to the space $\Sigma$ and not a two-element discrete set.

In other words, the confusion to which the original question referred is slightly sloppy language based on fundamentally the same idea. Imposing two-valued logic on termination of computations is also a misuse of language, but in my opinion one that seriously obstructs understanding.

decision procedureto determine $T \vdash \varphi$, namely search for a proof of $T \vdash \varphi$ and $T \vdash \neg \varphi$. This will halt iff$\varphi$ is not independent of $T$. With Gödel's and Tarski's theorems, the theory of the natural numbers (all statements true of the natural numbers) is not a decidable set of sentences. However, some theories like the theory of real closed fields (all true first order sentences of the real numbers) is decidable. $\endgroup$ – Jason Rute May 16 '13 at 5:52