1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Ackermann function

Discussion in 'Support' started by K_Meinhard, Apr 21, 2010.

  1. K_Meinhard

    Joined:
    May 20, 2008
    Messages:
    310
    Likes Received:
    0
    Hi all,

    has anybody seen this site:
    <http://rosettacode.org/wiki/Ackermann_function> ?

    How would the function look in TCC code? Which level of recursion is
    reached by TCC? Could we add it to the Rosetta code page?

    Best Regards,

    * Klaus Meinhard *
    <www.4dos.info>
     
  2. Péter Köves

    Joined:
    Jun 1, 2008
    Messages:
    58
    Likes Received:
    0
    Why would you want to do this? Ackerman's function (or to be precise </www.4dos.info>the Ackermann–Péter function) is know to all (ehem) people who've done anything with computability theory. It's value is to show that there exist recursive (one of the terms for computable aka Turing-computable, Markov-computable, lambda-computable, etc) functions that are not primitive-recursive (roughly a simpler, better behaved subclass).

    Being Hungarian, I of course take pride in knowing that Péter (this is her surname) is Rózsa Péter, an excellent 20th century Hungarian mathematician. She taught at the Hungarian university I went to, but I just missed her (she retired in '75 and died in '77). According to well-known anecdotes, in the 50-s she would bring back condoms from her foreign trips and distribute them to her students (these were impossible to obtain in Hungary at the time due to a state program of encouraged population growth).
     
  3. samintz

    samintz Scott Mintz

    Joined:
    May 20, 2008
    Messages:
    1,190
    Likes Received:
    11
    Using this batch script I can compute up to Ackermann(4,1). 4,2 blows up.
    And there is an upper limit of Ackermann(3,33219) also. If you comment
    out the "if %1 == 3" line then TCC's alias loop checking prevents too much
    recursion. Ackermann(3,15) is the biggest. 3,16 croaks with an alias
    loop error.

    Code:
    REM Ackermann Function
    if %1.==. .or. %2.==. goto usage
    if %1 LT 0 .or. %2 LT 0 goto usage
    echoerr ack: %1 %2
    if %1 == 0 (echos %@eval[%2+1] & quit)
    if %1 == 1 (echos %@eval[%2+2] & quit)
    if %1 == 2 (echos %@eval[3 + 2 * %2] & quit)
    if %1 == 3 (echos %@eval[5 + 8 * (2**%2 - 1)] & quit)
    iff %2 == 0 then
            echos %@execstr[call %0 %@dec[%1] 1]
            quit
    endiff
    set ack1=%@execstr[call %0 %1 %@dec[%2]]
    echo  %@execstr[call %0 %@dec[%1] %ack1]
    quit
    
    :usage
            echo usage %0 m,n
            text
    The Ackermann function is a classic recursive example in computer science. 
    
    It is a function that grows very quickly (in its value and in the size of 
    its call tree). 
    It is defined as follows:
    
        A(m, n) =  n+1, if m = 0 
                =  A(m-1, 1), if m > 0 and n = 0 
                =  A(m-1, A(m, n-1)), if m > 0 and n > 0
    
    Its arguments are never negative and it always terminates. 
    Write a function which returns the value of A(m,n). 
    Arbitrary precision is preferred (since the function grows so quickly), 
    but not required.
            endtext
            quit
    
    -Scott

    PòGer Kþ×es <> wrote on 04/21/2010 01:33:33 PM:


     
  4. vefatica

    Joined:
    May 20, 2008
    Messages:
    7,962
    Likes Received:
    30
    I think I have the formule correct below but I'm running into corruption that I
    can't explain. Does anyone see what's going wrong at level 4? Where are the
    extra []'s coming from?

    set level=0

    on error quit
    echo answer = %@exec[gosub ack %1 %2]
    quit

    : ack [m n]
    set level=%@inc[level]
    echo level = %level m = %m n = %n
    iff %m == 0 then
    set rv=%@inc[%n]
    elseiff %n == 0 then
    set rv=%@exec[gosub ack %@dec[%m] 1]
    else
    set rv=%@exec[gosub ack %dec[%m] %@exec[gosub ack %m %@dec[%n]]]
    endiff
    return %rv

    v:\> ackerman.bat 1 1
    level = 1 m = 1 n = 1
    level = 2 m = 1 n = 0
    level = 3 m = 0 n = 1
    level = 4 m = [1] n = 2
    level = 5 m = [1] n = 1
    level = 6 m = [1] n = 0
    level = 7 m = [[1]] n = 0
    level = 8 m = [[1]] n = 0
    answer = 0
    --
    - Vince
     
  5. vefatica

    Joined:
    May 20, 2008
    Messages:
    7,962
    Likes Received:
    30
    OK, I see the typo (%dec). Now it works but breaks down pretty quickly.

    On Wed, 21 Apr 2010 16:11:36 -0400, vefatica <> wrote:

    |I think I have the formule correct below but I'm running into corruption that I
    |can't explain. Does anyone see what's going wrong at level 4? Where are the
    |extra []'s coming from?
    |
    |set level=0
    |
    |on error quit
    |echo answer = %@exec[gosub ack %1 %2]
    |quit
    |
    |: ack [m n]
    |set level=%@inc[level]
    |echo level = %level m = %m n = %n
    |iff %m == 0 then
    | set rv=%@inc[%n]
    |elseiff %n == 0 then
    | set rv=%@exec[gosub ack %@dec[%m] 1]
    |else
    | set rv=%@exec[gosub ack %dec[%m] %@exec[gosub ack %m %@dec[%n]]]
    |endiff
    |return %rv
    |
    |v:\> ackerman.bat 1 1
    |level = 1 m = 1 n = 1
    |level = 2 m = 1 n = 0
    |level = 3 m = 0 n = 1
    |level = 4 m = [1] n = 2
    |level = 5 m = [1] n = 1
    |level = 6 m = [1] n = 0
    |level = 7 m = [[1]] n = 0
    |level = 8 m = [[1]] n = 0
    |answer = 0
    --
    - Vince
     
  6. samintz

    samintz Scott Mintz

    Joined:
    May 20, 2008
    Messages:
    1,190
    Likes Received:
    11
    In your else clause you missed an @ sign on your DEC function.

    -Scott

    vefatica <> wrote on 04/21/2010 04:11:34 PM:


    are the

     
  7. K_Meinhard

    Joined:
    May 20, 2008
    Messages:
    310
    Likes Received:
    0
    Rex,

    both versions of an ackermann.btm posted in this group by Vincent and
    Scott croak relatively early, at different levels of recursion. Is it
    okay that TCC croaks miserably, without an onerror warning? Couldn't
    that condition be caught somehow?

    Best Regards,

    * Klaus Meinhard *
    <www.4dos.info>
     
  8. rconn

    rconn Administrator
    Staff Member

    Joined:
    May 14, 2008
    Messages:
    9,863
    Likes Received:
    83
    I'm not aware of anything "croaking". Scott said it stops with an "Alias loop" error, which seems a perfectly reasonable result for an unreasonable app.
     
  9. vefatica

    Joined:
    May 20, 2008
    Messages:
    7,962
    Likes Received:
    30
    On Fri, 07 May 2010 21:07:39 -0400, rconn <> wrote:

    |I'm not aware of anything "croaking". Scott said it stops with an "Alias loop" error, which seems a perfectly reasonable result for an unreasonable app.

    Using my batfile, TCC "encounters a problem" (a good old crash).

    Try ACKERMAN 3 3

    REM ackerman.bat
    set level=0

    on error quit
    echo answer = %@exec[gosub ack %1 %2]
    quit

    : ack [m n]
    set level=%@inc[level]
    echo level = %level m = %m n = %n
    iff %m == 0 then
    set rv=%@inc[%n]
    elseiff %n == 0 then
    set rv=%@exec[gosub ack %@dec[%m] 1]
    else
    set rv=%@exec[gosub ack %@dec[%m] %@exec[gosub ack %m %@dec[%n]]]
    endiff
    return %rv
    --
    - Vince
     
  10. vefatica

    Joined:
    May 20, 2008
    Messages:
    7,962
    Likes Received:
    30
    On Fri, 07 May 2010 21:50:04 -0400, vefatica <> wrote:

    |Using my batfile, TCC "encounters a problem" (a good old crash).

    Here's a better implementation of the "level" counter, showing that it crashes
    when it's 14 deep.

    set level=0

    on error quit
    echo answer = %@exec[gosub ack %1 %2]
    quit

    : ack [m n]
    set level=%@inc[level]
    echo IN: level = %level m = %m n = %n
    iff %m == 0 then
    set rv=%@inc[%n]
    elseiff %n == 0 then
    set rv=%@exec[gosub ack %@dec[%m] 1]
    else
    set rv=%@exec[gosub ack %@dec[%m] %@exec[gosub ack %m %@dec[%n]]]
    endiff
    set level=%@dec[level]
    echo OUT: level = %level m = %m n = %n
    return %rv
    --
    - Vince
     
  11. rconn

    rconn Administrator
    Staff Member

    Joined:
    May 14, 2008
    Messages:
    9,863
    Likes Received:
    83
    That's what I'd expect with a 10Mb stack. If you really need to run this,
    crank your stack size up.

    Rex Conn
    JP Software
     
  12. vefatica

    Joined:
    May 20, 2008
    Messages:
    7,962
    Likes Received:
    30
    On Fri, 07 May 2010 22:46:27 -0400, rconn <> wrote:

    |---Quote---
    |> Here's a better implementation of the "level" counter, showing that it
    |> crashes when it's 14 deep.
    |---End Quote---
    |That's what I'd expect with a 10Mb stack. If you really need to run this,
    |crank your stack size up.

    I cranked it up to 100MB with editbin and it would do 3,3, getting 36 deep ...
    the result was not correct.

    Even in small cases I get crazy results 1,2 and 2,1 give different results (they
    shouldn't). It only gets 6 deep. Here's the algorithm briefly. Would you
    expect TCC to get confused?

    on error quit
    echo answer = %@exec[gosub ack %1 %2]
    quit

    : ack [m n]
    iff %m == 0 then
    set rv=%@inc[%n]
    elseiff %n == 0 then
    set rv=%@exec[gosub ack %@dec[%m] 1]
    else
    set rv=%@exec[gosub ack %@dec[%m] %@exec[gosub ack %m %@dec[%n]]]
    endiff
    return %rv
    --
    - Vince
     
  13. K_Meinhard

    Joined:
    May 20, 2008
    Messages:
    310
    Likes Received:
    0
    Vincent,


    Yes, that's what I mean by croaking. Your "on error" never gets invoked.
    Scott's version shows an "überlauf" (overrun?) several times before "TCC
    encounters a problem". I never saw the alias loop error.

    My question was just if this can't be caught and stopped before TCC
    crashes.

    herzliche Grüße,

    Klaus Meinhard








     
  14. vefatica

    Joined:
    May 20, 2008
    Messages:
    7,962
    Likes Received:
    30
    On Fri, 07 May 2010 23:38:12 -0400, vefatica <> wrote:

    |Even in small cases I get crazy results 1,2 and 2,1 give different results (they
    |shouldn't).

    My mistake. They should be different. TCC gets them right.
    --
    - Vince
     
  15. rconn

    rconn Administrator
    Staff Member

    Joined:
    May 14, 2008
    Messages:
    9,863
    Likes Received:
    83
    If you mean you want me to trap the stack overrun -- no, you *really* don't
    want me to do that.

    Rex Conn
    JP Software
     

Share This Page