Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



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 welldefined >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 Turingcomputable. 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 'Turingcomputable' is available for your version.
But doesn't Church's Thesis say that every "algorithm" is "Turingcomputable" ? It follows by contraposition that if it isn't "Turingcomputable" 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.



