Re: Turing completeness of the functional paradigm?



Chris Menzel wrote:
|On Mon, 18 Jul 2005 17:42:09 +0100, Robert Low <mtx014@xxxxxxxxxxxxxx>
said:
|> Babylonian wrote:
|>> PA does not define a unique notion of natural numbers. No formalism
|>> ever will.
|>
|> By 'formalism' do you mean 'first order'? Because there are
certainly
|> sets of axioms which uniquely define the natural numbers: the second
|> order Peano axioms do this.
|
|Assuming, of course, a standard model theory for second-order
languages.
|As I'm sure you know, though, there is also a "general" model theory
for
|second-order languages that Henkin introduced in proving the
|completeness of simple type theory, and second-order languages
|interpreted by this model theory are no more expressive than
first-order
|languages. Hence, so interpreted, second-order PA has nonstandard
|models. But standard, second-order *model theory* is no more forced
|upon us by the axioms of second-order PA alone than is the standard
|*model* forced upon us by the axioms of first-order PA. In this
sense,
|anyway, it seems to me that Babs is right; the formalism alone isn't
|enough. You also need to make an assumption about the background
model
|theory relative to which you are defining what it is for a theory to
|define a certain class.

Formalism is syntactic. The notion of "definition" is
semantic. So while it's true that the syntax doesn't
"force" a sematics on us, because it's true in general,
I wouldn't say that it's a special problem for the
natural numbers.

When people refer to a formalism as defining something,
they tend to mean the formalism accompanied by its
usual semantics. There are plenty of formalisms that
when interpreted in a standard way permit one to
define the natural numbers.

Keith Ramsay

.