Re: A qn on primitive recursive functions

From: peter_douglass (baisly_at_gis.net)
Date: 08/31/04 

Date: Tue, 31 Aug 2004 13:17:30 GMT

"peter_douglass" <baisly@gis.net> wrote in message
news:1L_Yc.99200$mD.71079@attbi_s02...
> "Peter Smith" <ps218@cam.ac.uk> wrote in message
> news:ps218-5624F5.09593031082004@pegasus.csx.cam.ac.uk...
>
> > The following is true:
>
> > There is no effective way of deciding, of some arbitrary primitive
> > recursive function f(x), whether there are values x such that
> > f(x) = 0.
>
> > You can prove that readily if you already know about Turing machines and
> > halting problems, or already know that the total recursive functions are
> > not effectively enumerable [for if we can effectively tell which p.r.
> > functions are regular, we could effectively enumerate the total
> > recursive function, because we could tell which recipes for functions
> > involved regular minization].

> > But how about a more direct proof that doesn't go via results about
> > Turing machines or recursive functions?

Addendum: If you aren't interested in machines per se, but just
primative recursive functions, replace "machine" everywhere in the
proof by "partial function". i.e. M is a set of partial functions,
m is an element of that set etc.

--PeterD

Relevant Pages

  • Notions of computation
    ... formalizing the same notion of computation: Turing machines, ... recursive functions, lambda calculus, combinatory logic, etc. ... basic facts as "the union of recursive languages is recursive" and "if ... one on that tape, and then these all tapes on this one tape" instead ...
    (comp.theory)
  • Re: A qn on primitive recursive functions
    ... > discussing recursive functions BEFORE we meet Turing machines, ... > course, remember, before we've heard of Turing machines, etc.] speculate ... > that the total recursive functions are ALL the intuitively computable ... then the diagonalization trick will necessarily generate ...
    (sci.logic)
  • Re: Computable functions/reals.
    ... abstraction or extension, IMHO, by the Church-Turing thesis. ... can extend Turing machines the way Mr. Ullrich or anyone else does. ... machines are intuively computable functions on N and all intuively ... all recursive functions on N are turing machines. ...
    (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: Computable functions/reals.
    ... When we are speaking about Turing machines some other posters say we ... functions on the naturals. ... some posters avoid that restriction to reintroduce it indirectly in ... essentially recursive functions on N by the literature, ...
    (sci.logic)