Ackermann function

#2
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>
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).
 

samintz

Scott Mintz
May 20, 2008
1,272
11
Solon, OH, USA
#3
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:


> ---Quote (Originally by K_Meinhard)---
> Hi all,
>
> has anybody seen this site:
> <http://rosettacode.org/wiki/Ackermann_function> (http:
> //rosettacode.org/wiki/Ackermann_function%3E) ?
>
> 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>
> ---End Quote---
> Why would you want to do this? Ackerman's function (or to be precise
> </www.4dos.info>the Ackermann¨CP¨¦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).
>
>
>
>
 
#4
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
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
 

samintz

Scott Mintz
May 20, 2008
1,272
11
Solon, OH, USA
#6
In your else clause you missed an @ sign on your DEC function.

-Scott

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


> 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
>
>
>
>
 
#7
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>
 

rconn

Administrator
Staff member
May 14, 2008
10,506
94
#8
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?
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
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
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
 
#12
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
Vincent,


> |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).
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








>
> 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
>
>
>
>
 
#14
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