Results 1 to 2 of 2

Thread: Induction Ackerman function

  1. #1
    Junior Member
    Nov 2012

    Induction Ackermann function


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

    $\displaystyle A(x,y) =$ $\displaystyle \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 $\displaystyle \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; Jan 16th 2013 at 01:56 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Oct 2009

    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: Jan 10th 2013, 04:42 PM
  2. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: Apr 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: Dec 16th 2010, 10:51 AM
  4. Replies: 10
    Last Post: Jun 29th 2010, 12:10 PM
  5. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 8th 2009, 09:33 PM

Search Tags

/mathhelpforum @mathhelpforum