# What is the importance of mentioning —U? (Turing 1936)

I'm trying to get my head around page 252 of Turing's "On Computable Numbers [...]", specifically near the end of the page where he talks about -U (logical negation of U, the German blackletter U).

The relevant context:

[...]

Now let α be a sequence, and let us denote by Gα(x) the proposition "The x-th figure of α is 1", so that —Gα(x) means "The x-th figure of α is 0".

Suppose further that we can find a set of properties which define the sequence α and which can be expressed in terms of Gα(x) and of the propositional functions N(x) meaning "x is a non-negative integer" and F(x,y) meaning "y = x + 1".

When we join all these formulae together conjunctively, we shall have a formula, U say, which defines α.

The terms of U must include the necessary parts of the Peano axioms, viz.,

(Eu)N(u)&(x)(N(x)->(ey)F(x,y))&(F(x,y) -> N(y)),

which we will abbreviate to P.

When we say "U defines α", we mean that —U is not a provable formula, and also that, for each n, one of the following formulae (An) or (Bn) is provable.

U & F(n) -> Gα(u(n)), (An),

U & F(n) -> —Gα(u(n)), (Bn),

where F(n) stands for F(u,u') & F(u',u'') & ... F(u(n-1),u(n)).

[...]

I understand (mostly) the motivation of this part of the paper, but I'm not grasping yet the reason for specifically stating "we mean that —U is not a provable formula".

My question --

When Turing mentions —U above, is he stating something we already know (or will know soon) about U, and if so, how? Or is he stating a requirement for which U's we'll be considering, and if so, why is this requirement important? I'm at little lost here; maybe I'm missing something simple.

(I'm currently reading Petzold's "The Annotated Turing". This is on page 226.)

-

## migrated from cstheory.stackexchange.comJun 30 '11 at 8:09

This question came from our site for theoretical computer scientists and researchers in related fields.

It should not change things very much, but if the negation of $\mathbb{U}$ is provable, we really do not want to use $\mathbb{U}$, since from the contradiction we could prove everything; the formula $\mathbb{U}$ would not separate the numbers $n$ such that $f(n)=0$ from those for which $f(n)=1$. It is the same minor issue as the fact that an inconsistent theory is technically complete, unless we make a specific exclusion.
If $-U$ is a provable formula then $\alpha$ doesn't exist. I think you can interpret this as "We do not consider a sequence to be defined if we can prove it doesn't exist".
@DuckMaestro, I haven't read any more context that what you've posted, and I can't immediately relate this to the concepts of computability I'm familiar with. But what I mean is more "It is impossible for there to exist an $\alpha$ which satisfies $U$". – Peter Taylor Jul 5 '11 at 6:24