Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.)

share|improve this question

migrated from cstheory.stackexchange.com Jun 30 '11 at 8:09

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

2 Answers 2

It looks as if Turing is defining representability in a manner that goes in the opposite direction from current practice, with the implication going from the representing formula to the function value than the other way around.

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.

share|improve this answer

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".

share|improve this answer
    
When you say α doesn't exist, you mean α isn't a computable sequence (number)? –  DuckMaestro Jul 4 '11 at 23:32
    
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.