How to resolve the algorithm Ackermann function step by step in the J programming language

Published on 12 May 2024 09:40 PM
#J

How to resolve the algorithm Ackermann function step by step in the J programming language

Table of Contents

Problem Statement

The Ackermann function is a classic example of a recursive function, notable especially because it is not a primitive recursive function. It grows very quickly in value, as does the size of its call tree.

The Ackermann function is usually defined as follows:

Its arguments are never negative and it always terminates.

Write a function which returns the value of

A ( m , n )

{\displaystyle A(m,n)}

. Arbitrary precision is preferred (since the function grows so quickly), but not required.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Ackermann function step by step in the J programming language

Source code in the j programming language

ack=: c1`c1`c2`c3 @. (#.@,&*) M.
c1=: >:@]                        NB. if 0=x, 1+y
c2=: <:@[ ack 1:                 NB. if 0=y, (x-1) ack 1
c3=: <:@[ ack [ ack <:@]         NB. else,   (x-1) ack x ack y-1


   0 ack 3
4
   1 ack 3
5
   2 ack 3
9
   3 ack 3
61


   Ack=. 3 -~ [ ({&(2 4$'>:  2x&+') ::(,&'&1'&'2x&*'@:(-&2))"0@:[ 128!:2 ]) 3 + ]


   0 1 2 3 Ack 0 1 2 3 4 5 6 7
1  2  3  4   5   6   7    8
2  3  4  5   6   7   8    9
3  5  7  9  11  13  15   17
5 13 29 61 125 253 509 1021
   
   3 4 Ack 0 1 2
 5    13                                                                                                                                                                                                                                                        ...
13 65533 2003529930406846464979072351560255750447825475569751419265016973710894059556311453089506130880933348101038234342907263181822949382118812668869506364761547029165041871916351587966347219442930927982084309104855990570159318959639524863372367203002916...
   
   4 # @: ": @: Ack 2 NB. Number of digits of 4 Ack 2
19729
   
   5 Ack 0
65533


   o=. @: NB. Composition of verbs (functions) 
   x=. o[ NB. Composing the left noun (argument)
   
   (rows2up=. ,&'&1'&'2x&*') o i. 4 
2x&*      
2x&*&1    
2x&*&1&1  
2x&*&1&1&1
   NB. 2's multiplication, exponentiation, tetration, pentation, etc.
    
   0 1 2 (BuckTruncated=. (rows2up  x apply ]) f.) 0 1 2 3 4 5
0 2 4  6     8                                                                                                                                                                                                                                                  ...
1 2 4  8    16                                                                                                                                                                                                                                                  ...
1 2 4 16 65536 2003529930406846464979072351560255750447825475569751419265016973710894059556311453089506130880933348101038234342907263181822949382118812668869506364761547029165041871916351587966347219442930927982084309104855990570159318959639524863372367203...
   NB. Buck truncated function (missing the first two rows)
   
   BuckTruncated NB. Buck truncated function-level code
,&'&1'&'2x&*'@:[ 128!:2 ]
   
   (rows01=. {&('>:',:'2x&+')) 0 1 NB. The missing first two rows
>:  
2x&+
   
   Buck=. (rows01 :: (rows2up o (-&2)))"0 x apply ]
   
   (Ack=. (3 -~ [ Buck 3 + ])f.)  NB. Ackermann function-level code
3 -~ [ ({&(2 4$'>:  2x&+') ::(,&'&1'&'2x&*'@:(-&2))"0@:[ 128!:2 ]) 3 + ]

You may also check:How to resolve the algorithm Interactive programming (repl) step by step in the Perl programming language
You may also check:How to resolve the algorithm Simple windowed application step by step in the JavaFX Script programming language
You may also check:How to resolve the algorithm Square but not cube step by step in the Tcl programming language
You may also check:How to resolve the algorithm Go Fish step by step in the Mathematica / Wolfram Language programming language
You may also check:How to resolve the algorithm Discordian date step by step in the C# programming language