So, we already know that TI-BASIC's control flow stack can be used to implement subroutines in TI-BASIC by abusing the "memory leak bug" to implement a return stack:

Code:
:"calling a subroutine
:For(A,0,1)
:If not(A
:Goto AA
:End
:
:"definition of subroutine
:Lbl AA
:Disp "AA
:End

Another weird bug-thing that has been established before is that you can use unnamed For-loop variables to store data on the same control stack (on CSE and higher). Theoretically, this should make it possible to implement proper recursion in TI-BASIC by making use of just the control stack. Theoretically, of course. This would be entirely too impractical and unreasonable to actually try to implement. It could be a thought experiment at best. A hypothetical edge case in the development of static analysis tools, and even then probably not, because who would be insane enough to actually write something like that.

Therefore, behold, the Ackermann function:

Code:
:Lbl A2
:1->N
:M-1->M
:
:Lbl AK
:If not(M
:  Goto A1
:If not(N
:  Goto A2
:
:0->B
:1->C
:N-1->N
:For(L1(1),0,M
:  B+1->B
:  If C
:    Goto AK
:End
:A->N
:B-1->M
:Goto AK
:
:Lbl A1
:0->B
:0->C
:N+1->A
:End

To use, set M and N to those respective arguments, call AK using the method described above, and the result is in A. L1 needs to exist and have at least one element (but it is not accessed nor changed, and there are several alternatives available). We only need to store M and a return address on the stack, and it uses two tail calls. Stack depth scales with N, so it is likely to overflow. This means M is better stored in unary. This makes extraction slow, but it is clear we already didn't care about speed here. This has been an exercise in inanity from the very beginning.

Note: I haven't actually been able to test this. I don't have a CSE or a CE, which support the "unnamed For var" feature (yes I'm calling it a feature now). I'm pretty sure it should work though. (EDIT: Zeroko checked, it works)

Just in case that wasn't enough, a version that doesn't use real variables either:

Code:
:Lbl 2
:{Ans(1)-1,1
:Lbl 0
:If not(Ans(1
:Goto 1
:If not(Ans(2
:Goto 2
:{Ans(1),Ans(2)-1,0,1
:For(L1(1),0,Ans(1
:{Ans(1),Ans(2),Ans(3)+1,Ans(4
:If Ans(4
:Goto 0
:End
:{Ans(3)-1,Ans(5
:Goto 0
:Lbl 1
:{Ans(1),Ans(2),0,0,1+Ans(2
:End


Or, a version that returns a real in Ans, courtesy of Zeroko:

Code:
:Lbl 2
:{Ans(1)-1,1
:Lbl 0
:If not(Ans(1
:Goto 1
:If not(Ans(2
:Goto 2
:{Ans(1),Ans(2)-1,0,0
:For(L1(1),0,Ans(1
:Ans{1,1,1,1}+{0,0,1,0
:If not(Ans(4
:Goto 0
:End
:{Ans(3)-Ans(4)-1,Ans(4
:Goto 0
:Lbl 1
:1+Ans(2
:End

(both of these should be called using {M,N} in Ans)

Isn't this great? Non-primitive recursion using no reals and no lists! How cool is that! TI-BASIC is such a powerful and fully-featured language!
Programs abusing the End-stack are among the strangest extant species of TI-BASIC creature. I applaud you for your actually quite readable demonstration.

I hesitate to wonder aloud if it's possible to do push-down automata things with the control flow stack.
This is really, really slow.

For the variable-free version that returns a real:
To compute A(3,0)=5 takes 1 second.
To compute A(3,1)=13 takes 4 seconds.
To compute A(3,2)=29 takes 18 seconds.
To compute A(3,3)=61 takes 91 seconds.
To compute A(3,4)=125 takes 479 seconds.
(Times computed using startTmr & checkTmr, so they are only accurate to within ±1 second.)

A(4,1) (probably? definitely A(4,2), at least) & higher (& also some of A(<4,—)) will overflow the stack.
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Page 1 of 1
» All times are UTC - 5 Hours
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

 

Advertisement