Results 1 to 3 of 3

Math Help - Primitive Recursive vs Recursive Functions

  1. #1
    Newbie
    Joined
    Nov 2007
    Posts
    8

    Primitive Recursive vs Recursive Functions

    Please could someone explain to me the difference between a primitive recursive function and a recursive function. I don't really need a formal definition, I would like to understand the difference between them so I can learn more about Ackermann's functions.

    All I know so far is that all PR functions are recursive, I don't really understand do-loops or while-loops which are used in some definitions of recursion that I've found.

    Is a recursive function or a primitive recursive function a function which can be implemented with a Turing machine? Also what is a partially recursive function?

    Many thanks

    Steph
    Follow Math Help Forum on Facebook and Google+

  2. #2
    nvv
    nvv is offline
    Newbie
    Joined
    Jan 2009
    Posts
    14
    Hi, Treblesteph

    The difference bettwen this two classes(a primitive recursive function and a recursive function) isusing operation of operation minimization to obtain recursive functions.

    Def(recursive functions) :
    --operations: superposition, Primitive recursion, minimization
    --functions: 0-function, S(s)-'next' function, N[n, m] - 'selec' function

    Def(primitive recursive function) :
    --operations: superposition, Primitive recursion
    --functions: 0-function, S(s)-'next' function, N[n, m] - 'selec' function


    Ackermann's function is an example of computable not a primitive recursive function
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2007
    Posts
    8
    Sorry but I still don't understand - I can't follow the notation you've used. Could you (or someone else) please explain it more simply?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Primitive Recursive Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 2nd 2010, 11:24 AM
  2. sequences by primitive recursive rules?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: January 31st 2010, 03:45 AM
  3. Definin recursive functions in Mathematica
    Posted in the Math Software Forum
    Replies: 5
    Last Post: January 19th 2010, 10:42 AM
  4. Show Primitive Recursive
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: July 31st 2009, 07:23 PM
  5. Primitive Recursive
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: June 20th 2009, 02:17 PM

Search Tags


/mathhelpforum @mathhelpforum