Re: Specifying Sets



Mitch Harris wrote:
On Nov 30, 1:30 pm, Aatu Koskensilta <aatu.koskensi...@xxxxxx> wrote:
Chris Menzel <cmen...@xxxxxxxxxxxxxxxxxxxx> writes:

Church's thesis is that the (informal) notion of an intuitive
computable function is completely captured by the formal notion of
computability delivered by Turing machines, recursiveness, etc.

Quite so. What should also be stressed is that it is not a thesis
about algorithms, mechanical procedures, and so on, in themselves, but
about the functions calculated by algorithms, mechanical procedures,
and so on; or in other words, that it is a purely extensional
thesis. We may ask interesting "intensional" questions, such as
whether there is a mathematical elucidation of the notion of an
algorithm, a clear notion of when two algorithms count as the same, a
clear notion of what it means for two programs in a given language to
be implementations of the same algorithm, and so on. On these
questions the thesis tells us nothing.

There has been very little on this in the past, but more recently
Gurevich has attempted to address the question of 'can we pin down
what an -algorithm- is?' and the answer seems to lean toward the
negative, that is, there is no -possible- analagous thesis for the
concept algorithm. (google for 'algorithm gurevich')


I would like at this time to put on my crank hat and say,
the rather antique 'algorism' means the same thing and is
much nicer looking and easier to say. We should use that
instead.

Thank you.

--
hz
.

Relevant Pages