Results 1 to 2 of 2

Math Help - Induction Ackerman function

  1. #1
    Junior Member
    Joined
    Nov 2012
    From
    Poland
    Posts
    40

    Induction Ackermann function

    Hello,

    I have to prove by induction that the following Ackerman function that takes pairs \mathbb{N} \times \mathbb{N} always halts:

    A(x,y) = \begin{cases} y + 1, &\text{dla } x=0\\A(x - 1, 1) &\text{dla } x>0 \ i \ y=0\\A(x - 1, A(x,y - 1)) &\text{dla } wpp \end{cases}

    How should I go about proving that when the function halts, then it returns a natural number? I don't need this assumption to prove that the first two cases of the formula halt, but for the third one, which takes \langle x-1,A(x,y-1) \rangle I think I need to know that the second value is positive, which I have no idea how to surmise this.
    Last edited by MachinePL1993; January 16th 2013 at 01:56 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Induction Ackerman function

    You do nested inductions: the outer one on x and the inner one on y. The induction statement (and hypothesis) for x is that A(x - 1, y) terminates for all y. It is important that the universal quantifier on y is included in the induction statement.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: January 10th 2013, 04:42 PM
  2. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  3. [SOLVED] Theorem involving delta function: proof by induction
    Posted in the Advanced Math Topics Forum
    Replies: 7
    Last Post: December 16th 2010, 10:51 AM
  4. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  5. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM

Search Tags


/mathhelpforum @mathhelpforum