Prev: math symbols in unicode collection
Next: Computable reals
From: Frederick Williams on 27 Jun 2010 09:58
Back in August 2008 (!) I claimed that the Church-Turing thesis,
despite its name, was a definition of computable function (on N
specifically, but given pairing and coding it doesn't matter much).
Aatu Koskensilta and Chris Menzel said that it wasn't and I quoted
something from Kleene in support of my opinion. I have since found
quotations from Church and Turing themselves in support of my claim.

The page numbers are references to [TU] wherein references to the
original works may be found.

Church, p 100:

We now define the notion, already discussed, of an _effectively
calculable_ function of positive integers by identifying it with the
notion of a recursive function of positive integers^{18} (or of
a lambda-definable function of positive integers). This definition
is thought to be justified by the considerations which follow, so
far as positive justification can ever be obtained for the
selection of a formal definition to correspond to an intuitive
notion.

[Footnote 18:] The question of the relationship between effective
calculability and recursiveness (which it is here proposed to answer
by identifying the two notions) was raised by G�del in conversation
with the author. The corresponding question of the relationship
between effective calculability and lambda-definability had
previously been proposed by the author independently.

Turing, p 160 (I'll omit Turing's references):

A function is said to be "effectively calculable" if its values can
be found by some mechanical process. Although it is fairly easy to
get an intuitive grasp of this idea, it is nevertheless desirable to
have some more definite, mathematically expressible definition.
Such a definition was first given by G�del at Princeton in 1934,
following in part an unpublished suggestion of Herbrand, and has
since been developed by Kleene. These functions were described as
"general recursive" by G�del. We shall not be much concerned here
with this particular definition. Another definition of effective
calculability has been given by Church, who identifies it with
lambda-definability. The author has recently suggested a definition
corresponding more closely to the intuitive idea. It was stated
above that "a function is effectively calculable if its values can
be found by some purely mechanical process". We may take this
statement literally, understanding by a purely mechanical process
one that could be carried out by a machine. It is possible to give
a mathematical description, in a certain normal form, of the
structures of these machines. The development of these ideas leads
to the author's definition of a computable functions, and to an
identification of computability with effective calculability. It is
not difficult, though somewhat laborious, to prove that these three
definitions are equivalent.

E&oe.

***

If someone has [TU] to hand, can they please look at page 160? At the
start of a line just about in the middle of the page appears "by
Kleene [2])". Where should the left hand bracket to match that right
hand one be? My guess is that "by Kleene (Kleene [2])" is meant.

***

[TU] 'The Undecidable: basic papers...' edited by Martin Davis, Raven
Press, 1965.

Ho, ho, ho again. Maybe it's the warm weather?
From: Frederick Williams on 28 Jun 2010 08:51
Frederick Williams wrote:
>
> Back in August 2008 (!) I claimed that the Church-Turing thesis,
> despite its name, was a definition of computable function (on N
> specifically, but given pairing and coding it doesn't matter much).

At news:48A6CEE5.EDBE9DB6(a)tesco.net specifically.

> Aatu Koskensilta and Chris Menzel said that it wasn't and I quoted
> something from Kleene in support of my opinion.

At news:48B7F2E5.F914A592(a)tesco.net> specifically.

--
I can't go on, I'll go on.
From: Aatu Koskensilta on 1 Jul 2010 00:02
Frederick Williams <frederick.williams2(a)tesco.net> writes:

> Back in August 2008 (!) I claimed that the Church-Turing thesis,
> despite its name, was a definition of computable function (on N
> specifically, but given pairing and coding it doesn't matter much).
> Aatu Koskensilta and Chris Menzel said that it wasn't and I quoted
> something from Kleene in support of my opinion. I have since found
> quotations from Church and Turing themselves in support of my claim.

Church and Turing both referred to the thesis as a "definition" at
times. This is a bit odd since they both also gave arguments in support
of the definition, and it's difficult to see what sort of arguments,
except perhaps arguments for terminological aptness, one can give for a
definition, or a definition could stand in need of. But quoting from the
Patton paper you were trying to decipher in an another post:

This expository paper borrows from three main sources to present
a proof of Church's theorem in the form

(1) The set of valid quantificational formulas is not
effective.

...

[W]e arrive at

(2) The set of Gδdel numbers of valid quantificational
formulas is not recursive.

While (2) is provable, however, in order to infer (1) we need an
additional premise, a version of Church's Thesis, namely,

(3) All effective sets of numbers are recursive.

And indeed this is the sense we today speak of the Church-Turing
thesis. Without some such thesis, relating the purely mathematical
notions to the intuitive notion of effective computability -- which has
no mathematical definition -- we can't speak of e.g. a solution to the
Entscheidungsproblem. Similarly, without some argument relating formal
proofs to mathematical provability in the ordinary sense we can't draw
any conclusion regarding mathematical provability from, say, the formal
undecidability of the continuum hypothesis in ZFC.

The situation here is analogous to what we find in mathematical
physics. In order to draw physical conclusions from mathematical models
the physical significance of the various components and mathematical
properties of the model must be spelled out. Otherwise the mathematical
machinations tell us nothing about the physical phenomena they are
supposed to shed light on.

> If someone has [TU] to hand, can they please look at page 160? At the
> start of a line just about in the middle of the page appears "by
> Kleene [2])". Where should the left hand bracket to match that right
> hand one be? My guess is that "by Kleene (Kleene [2])" is meant.

That's a plausible guess. Incidentally, on page 160 Turing explicitly
discusses the relationship between the intuitive idea of "effectively
calculable" and the formal notion of "computable function". This is an
odd thing to do if "effectively calculable" simply means "computable by
a computable function" by stipulation.

--
Aatu Koskensilta (aatu.koskensilta(a)uta.fi)

"Wovon man nicht sprechan kann, darüber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
 | 
Pages: 1
Prev: math symbols in unicode collection
Next: Computable reals