Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Topic: Concrete and Abstract in Mathematics, was "What's wrong with education..."
Replies: 10   Last Post: Jun 17, 1996 12:57 AM

 Messages: [ Previous | Next ]
 Alberto C Moreira Posts: 266 Registered: 12/6/04
Re: Concrete and Abstract in Mathematics, was "What's wrong with education..."
Posted: Jun 13, 1996 9:01 PM

b.scott@bscott.async.csuohio.edu (Brian M. Scott) wrote:
>In article <Dsv7z6.629@mv.mv.com>, Alberto C Moreira

>>An algorithm isn't necessarily exact, nor it needs to always give
>>the same solution to the same problem. And it's not clear whether
>>one defines machine solvability in terms of the concept of
>>"algorithm" or whether we rather define "algorithm" as anything
>>that can be handled by a computing machine. The way I see it,
>>Church's thesis goes exactly the opposite way you state: it is
>>an algorithm if it can be handled by a Turing Machine.

>I think that this is exactly backwards. My understanding of Church's
>Thesis is closer to Gerry LaValley's. We have an intuitive, informal
>understanding of the word 'algorithm' as (roughly) 'a well-defined
>procedure'. I take Church's Thesis to be that any algorithm (in the
>informal sense) can be formalized as a Turing machine. In other words,
>CT says that the precise concept of 'Turing machine' captures the
>informal notion of 'algorithm'. Such a statement is obviously not
>susceptible of proof, but the fact that all serious attempts to capture
>the notion of 'algorithm' are provably equivalent certainly encourages
>belief.

Your notion - and Gerry's - is the party line way of thinking.
But still, there's more to it: if we're trying to do computer
science, and all we have about an "algorithm" is an informal
understanding, we might as well dump it and use the formal
characterization instead, and define algorithm as anything
that can be described by that formal characterization. To the
extent that the claim is that there's nothing we would call an
"algorithm" that evades the formal characterization, why bother
with the informal notion ? We can just as well define an
algorithm as anything that can be negotiated by a Turing Machine, and
to show that something cannot be done in a computer requires one to
show that it cannot be done on a Turing Machine. There's a difference
here, mind you, between "we don't know how to express this as an
algorithm" and "we can prove that this cannot be expressed as an
algorithm".

So, we can safely ignore intuition here and define, an "algorithm"
is anything that's Turing-computable. If some day someone finds
one that isn't, then we'll have to change the definition. But by
the looks of it, it doesn't seem probable, at least with today's
knowledge.

>Your version, on the other hand, is not so much a thesis as a formal
>definition (albeit informally expressed) of 'algorithm'. This seems
>a waste of a good word: 'algorithm' already has a useful if imprecise
>meaning, and the term 'Turing-computable' is available for your version.

But doesn't Church's Thesis say that every "algorithm" is
"Turing-computable" ? It follows by contraposition that if it isn't
"Turing-computable" then it isn't an algorithm. Because Church's
thesis is dealing with an imponderable here, its formulation almost
takes the power of an axiom; to topple it, we would have to find
something that our intuition and insight definitely would consider
an "algorithm", and yet it cannot be computed. But even when we
try to characterize the notion of "algorithm" a bit deeper, f.ex.,
see Rogers' book ("Theory of Recursive Functions and Effective
Computability", MIT Press), that characterization quickly leads us
towards recursive functions.

This is a bit like the issue of characterizing cardinals. We have
a pretty good (intuitive) idea of what a cardinal is; but when we
try to formally characterize them, the ground disappears from
underneath our feet, and we must be content with defining them
in ways that do not at all match our intuition. Same thing with
"algorithm", at least the way I see it.

Alberto.

Date Subject Author
6/13/96 Alberto C Moreira
6/14/96 Brian M. Scott
6/14/96 Herman Rubin
6/15/96 Brian M. Scott
6/16/96 Herman Rubin
6/16/96 Lee Rudolph
6/17/96 Brian M. Scott
6/15/96 Alberto C Moreira
6/15/96 Brian M. Scott
6/14/96 Mike McKeown