Re: A qn on primitive recursive functions

From: peter_douglass (baisly_at_gis.net)
Date: 09/02/04 

Date: Thu, 02 Sep 2004 14:42:54 GMT

"Peter Smith" <ps218@cam.ac.uk> wrote in message
news:ps218-F7E4EF.10281401092004@pegasus.csx.cam.ac.uk...

> So consider the following class-room situation in a course where we are
> discussing recursive functions BEFORE we meet Turing machines, register
> machines, etc.

> 1) We prove by diagonalizing out that there computable but not primitive
> recursive (p.r.) functions. This proof doesn't require any close
> analysis of the idea of computability -- it just requires us to
> recognize the diagonal function as intuitively computable.

You could generalize this as follows. For any set of functions which
can be "diagonalized", the diagonalization (and modification of each
position in the diagonal) constructs a new function which is not in the
original set. For example, an anti-diagonal of the set of primitive
recursive functions is not p.r.
At this point there is no need to say that these functions are necessarily
computable, because you are about to achieve that end in your step 2.

> 2) We explain why the p.r. functions aren't all the computable functions
> by pointing out that we allow intuitive computations to involve
> unbounded searches. We motivate expanding the class of p.r. functions by
> allowing use of the minimization operator, to get recursive functions.
> We note that recursive functions won't be total unless minimization is
> applied to "regular" functions. We also [at this early point in the
> course, remember, before we've heard of Turing machines, etc.] speculate
> that the total recursive functions are ALL the intuitively computable
> total functions.

OK

> 3) Bright and Persistent Student now asks: "Why can't we run a parallel
> argument to (1) and diagonalize out of the class of total recursive
> functions and get computable but not recursive functions". Because we
> can't effectively enumerate the total recursive functions. BPS: "Why
> not?" Because, for a start, we'd have to be able to effectively tell in
> which recipes -- from an effectively enumerable list of potential
> recipes for functions -- the minimization operator is applied to a
> "regular" p.r function, and we can't do that. BPS: "Why not?" Because
> ["The Claim"] we can't effectively tell if an arbitrary p.r. function is
> regular. BPS "Why not ...?".

If we have a set of all "computable" functions, for some definition of
"computable", then the diagonalization trick will necessarily generate
a function that is *not* computable. In your step one, we really didn't
know that the diagonal was *computable* until we added unbounded
search and partiality to p.r. functions to get general recursive functions.

If someone could add a new "realizable" method of constructing
functions to the set of methods used to construct general recursive
functions, and if one further could show that this method allowed the
construction of an anti-diagonal of the total recursive functions,
then one would have validly constructed computable functions that
are not recursive, thus disproving the Church-Turing Hypothesis.

You could allow for that possibility at this stage.

> 4) Given the speculation that total recursive functions are ALL the
> intuitively computable total functions is at this point in the classroom
> dialectic just that, a speculation, we would LIKE now to be able to
> deliver an argument for The Claim that -- like the argument at step (1)
> -- doesn't depend (or at least, doesn't depend too overtly!) on the
> Church-Turing Hypothesis. Otherwise our Bright and Persistent Student
> may think she smells a rat! :-)) For she'll say "I wanted an argument
> for The Claim so I can block one potential line of argument against the
> Church-Turing Hypothesis that the total recursive functions are all the
> total computable functions. You don't want me to go round in circles do
> you?".

I don't think you need to claim that the constructed diagonal of the
p.r. functions is "intuitively" computable in step 1. You *prove* that
there are non p.r. functions that are computable in step 2.
I *think* the problem with your student "smelling a rat" would go
away.

> OK, at this point Harrassed Lecturer (or at least THIS Harrassed
> Lecturer in the past) says in effect "Bear with me, we are going to be
> looking at lots more stuff on ideas of computation, and how they are all
> equivalent, and then you too, BPS, will get to accept the Church-Turing
> Hypothesis which you can then use to get neat informal proofs of all
> kinds of things, including The Claim". And BPS looks sceptical and
> mutters about rigour not being what it was ....

> How does HL do a bit better? :-))))

In my wild imagination, the thoughts above should allow your
class to progress step by step without rodent odor. I certainly
won't claim that I'm right about this, or that it is the best way
to teach the subject. But since you asked... ;-)

--PeterD

Relevant Pages

  • Re: Where is the error?
    ... > more or less given a proof that there is no such effective procedure). ... first post, but the above is not true. ... What is not possible is to use recursive functions ... the diagonalization that is incorrect. ...
    (sci.logic)
  • Re: A qn on primitive recursive functions
    ... or already know that the total recursive functions are ... >> Turing machines or recursive functions? ... proof by "partial function". ...
    (sci.logic)
  • Re: A qn on primitive recursive functions
    ... or already know that the total recursive functions are ... >> Turing machines or recursive functions? ... proof by "partial function". ...
    (sci.math)
  • Re: Where is the error?
    ... >The set R of all recursive functions is not inductively generable. ... >diagonalization a recursive function f not in R, that is absurd because R is ... >axiomatic theory. ... more or less given a proof that there is no such effective procedure). ...
    (sci.logic)
  • Re: Where is the error?
    ... >>The set R of all recursive functions is not inductively generable. ... >>diagonalization a recursive function f not in R, that is absurd because R is ... >>But the set R can be inductively generated by a British Museum procedure. ... Prev by Date: ...
    (sci.logic)