You are currently browsing the tag archive for the ‘primitive recursive’ tag.

The Gödelian argument afresh!

In a talk given on 25/5/96 at a BSPS conference in Oxford, J. R. Lucas [1] articulated his original Gödelian argument [2] afresh as follows:

“The Mechanist claims to have a model of the mind. We take the Mechanist seriously only if he will warrant that his purported model of the mind is consistent. In that case it passes the First Public Examination, but comes down at the Second, because knowing that it is consistent, we know that its Gödelian formula is true, which it cannot itself produce as true.

More succinctly, we can, if a Mechanist presents us with a system that he claims is a model of the mind, ask him simply whether or not it can prove its Gödelian formula (according to some system of Gödel numbering).

If he says it can, we know that it is inconsistent, and would be equally able to prove that 2 and 2 make 5, or that 0=1, and we waste little time on examining it.

If, however, he acknowledges that the system cannot prove its Gödelian formula, then we know it is consistent, since it cannot prove every well-formed formula, and knowing that it is consistent, know also that its Gödelian formula is true.

In this formulation we have, essentially, a dialogue between the Mechanist and the Mentalist, as we may call him, with the Mechanist claiming to be able to produce a mechanist model of the Mentalist’s mind, and the Mentalist being able to refute each particular instance offered.”

Do we really hope to get away with this argument?

Actually, if we were to ask Lucas’ hypothetical Mechanist whether, or not, his model can prove its Gödelian formula, he would, most likely, retort:

`Before I commit my resources to something that may be impossible, can you assure me that it is provable?’

Of course we cannot, since we, too, cannot give a finitary proof of the formula that we are asking of the Mechanist’s finitary model.

If we, nevertheless, attempt to assert our superiority over the Mechanist by claiming, somewhat superciliously, that we do know, however, that the formula in question is true, but that it is one which the Mechanist’s model “cannot itself produce as true”, we would cut an even sorrier figure.

A prompt—seemingly astonished but subtly cunning—reply could be:

`Whatever gave you that idea! My model can even prove that it’s true.’

The Mechanist’s Challenge

If, unwittingly, we were to express incredulity, we would face the humiliating challenge:

`The Gödelian formula—which Gödel [3] refers to by its Gödel number—17Gen r, is of the form [(\forall x)R(x)].

Neither of us can prove it from the agreed set of premises by the specified rules of inference of the Arithmetic in question [4].

However, for a large enough numeral [n], my model can always produce a proof sequence for [R(1) \& R(2) \& \ldots \& R(n)] from the premises faster than you.’

The reason we would have to sheepishly concede defeat, without even addressing the challenge, is that Gödel has constructed [5] a primitive recursive relation, xBy, which ensures that the Mechanist can show that the Gödelian sentence is true, in the Tarskian sense, by providing a Turing machine that can “compute” [R(n)] as TRUE for any given numeral [n] [6] as input.

Specifically, Gödel defines xBy (primitive) recursively [7]—over the structure \mathbb{N} of the natural numbers—so that it holds for natural numbers x, y, if, and only if, x is the Gödel number of a proof sequence—in any Arithmetic of the natural numbers—for the formula of the Arithmetic whose Gödel number is y.

Since our definition of the truth of a formula under an interpretation in \mathbb{N} is also based on Tarski’s specification that it hold exhaustively, i.e., every instantiation of it must hold in the interpretation, our argument for our intellectual superiority over the Mechanist’s model fails miserably in this particular instance.

End of story?

Not quite.

There’s more

We could perhaps try to find solace—and console ourselves—with the thought that our brains are not designed ideally to tackle problems that can only be tackled by brute force; but they are, surely, superior to the Mechanist’s model when it comes to proofs that require ingenuity.

However, we will, then, face even greater discomfiture.

Gödel has given [8] another primitive recursive predicate, Bw(x), that the Mechanist can program on a UTM to—given sufficient time—create a set of theorems that will contain, and continue to be larger than, the set of all the arithmetical theorems that we have ever proven—and verified—collectively using only pencil, paper, and our “superior” intellects!

Gödel [9] defines Bw(x) (primitive) recursively so that it holds for any natural number x if, and only if, x is the Gödel number of a proof sequence in the Arithmetic.

Moreover, the set would contain theorems that we could not even conceptualise, since we would be unable to grasp even the statement, leave alone the proof, of these theorems!

So, what is really wrong with the Gödelian argument?

Well, ironically—and perhaps paradoxically—it’s simply another instance of human insecurity applying very common, and very human, double standards!

Namely, matching our selective interpretation of Tarski’s ambiguously defined concept of intuitive truth (we highlight this ambiguity here[10]) against the Mechanist’s unambiguously defined concept of provability to subtly load the dice in our favour semantically when faced with formal arguments that threaten to expose the continuing reluctance of the human ego to come to terms adequately with, and tap constructively into, the awesome conceptual power, diversity, and potential of any Intelligence, human or otherwise.

References

Go31 Kurt Gödel. 1931. On formally undecidable propositions of Principia Mathematica and related systems I. Translated by Elliott Mendelson. In M. Davis (ed.). 1965. The Undecidable. Raven Press, New York. pp.5-38.

Lu61 J. R. Lucas. 1961. Minds, Machines and Gödel. Philosophy, XXXVI, 1961, pp.112-127; reprinted in The Modeling of Mind. Kenneth M. Sayre and Frederick J. Crosson, eds., Notre Dame Press, 1963, pp.269-270; and Minds and Machines, ed. Alan Ross Anderson, Prentice-Hall, 1954, pp.43-59.

Lu03 John R. Lucas. 2003. The Gödelian Argument: Turn Over the Page. In Etica & Politica / Ethics & Politics, 2003, 1.

An07 Bhupinder Singh Anand. 2007. The Mechanist’s challenge. in The Reasoner, Vol(1)5 p5-6.

An12 Bhupinder Singh Anand. 2012. Evidence-Based Interpretations of PA. In Proceedings of the Symposium on Computational Philosophy at the AISB/IACAP World Congress 2012-Alan Turing 2012, 2-6 July 2012, University of Birmingham, Birmingham, UK.

Notes

Return to 1: See Lu03.

Return to 2: See Lu61.

Return to 3: Go31, p.25.

Return to 4: ibid., p.25(1), “17Gen r is not \kappa-provable”.

Return to 5: ibid., p.22(45)

Return to 6: ibid., p.26(2).

Return to 7: ibid., p.22, def. 45.

Return to 8: ibid., p.22(44).

Return to 9: ibid., p.22, def. 44.

Return to 10: See An12.

Bhupinder Singh Anand

Advertisements

Readability

Try reading in +125 magnification

Start here

Enter your email address to follow this blog and receive notifications of new posts by email.

Join 84 other followers

Recent posts

LobeLog

Critical Perspectives on U.S. Foreign Policy

What's new

Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Tao

Quanta Magazine

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

The Brains Blog

Since 2005, a leading forum for work in the philosophy and science of mind

Logic Matters

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

A Neighborhood of Infinity

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

Combinatorics and more

Gil Kalai's blog

Mathematics and Computation

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

Foundations of Mathematics, Logic & Computability

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

John D. Cook

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

Shtetl-Optimized

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

Nanoexplanations

the blog of Aaron Sterling

Eric Cavalcanti

Quantum physicist

East Asia Forum

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

Tanya Khovanova's Math Blog

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

The polymath blog

Massively collaborative mathematical projects

Gowers's Weblog

Mathematics related discussions