Talk:Iterate

would there be a way to prove what computational class Iterate is? not really sure how to go about this I know it isn't a Finite-state automaton simply from this code:

(*)∞<
  *=1< @ > // loops once on the second pass, then twice on the third, three times on the fourth, and so on
           // "", "1", "12", "123", "1234", "12345", ...
  (*1)1< > // increment
>

and it also isn't a Push-down automata... what could it be? —aadenboy (talk|contribs) 17:39, 22 January 2025 (UTC)

Perhaps Iterate can embed flowcharts, allowing something like the wikipedia:structured program theorem to apply. Corbin (talk) 18:03, 22 January 2025 (UTC)

I think I can come up with something with the $# command, but I'm still very interested to see what its computational class is without it, since it still looks like it could be but it's much less clear (at least to me). -PkmnQ (talk) 01:17, 24 January 2025 (UTC)

I was able to get conditionals implemented, more likely we can find the class of Iterate this way. but memory might be an issue as there's not really a way to store unbounded memory—we're limited to the finite, existing labels —aadenboy (talk|contribs) 04:06, 25 January 2025 (UTC)

arbitrary memory

I figured out a way to store arbitrary memory, it was actually pretty simple (the iterations easily get crazy big though, as expected)

(*)1<
  *?< (1*)<> > // L1 = program (reversed)
  (9*)∞<
    *10< (2*)<> (4*)<> > // single bit of info is a unit of 10 -> [0 ... 9] are commands
    (6*)=1<              // input ÷ unit = next commands REMAINDER current command
      (3*)<>
      $5
      *=4< (5*)<> >
      $4
      *=5<           
        *~n< (4*)<> >
        !
      >
      *=4< &6 >
      $3            // L7 = input % input (next commands)
      *=2< (4*)<> >
      (7*)<>        // L3 = input ÷ unit (current command)
    >
    (8*)=3< // basic example: 1-9 print 1-9
      *~n< &8 >
      @
      $1
      *=7< (1*)<> >     // set L1 to L7
      $2 $3 $4 $5 $6 $7 // reset for next command
      &9
    >
    !^ // basic example: 0 halts the program
  >
>

this is one step closer to turing completeness! —aadenboy (talk|contribs) 03:53, 2 March 2025 (UTC)

this can be adapted to implement a stack:

Pushing:
L1 = stack     // initial
L2 = 0         // temp
L2 = L1 * unit // loop L1: loop 10: increment L2
L1 = L2
L1 = L1 + n (where n < unit)

Popping:
L1 = stack
L2 = L1 / unit // the rest of the stack
L3 = L1 % unit // the element popped
L1 = L2        // L1 is now popped

then two stacks can make a tape —aadenboy (talk|contribs) 03:50, 9 March 2025 (UTC)

Remember that you have access to counter machines (including structured forms) and tag systems as proof targets. You do not have to simulate Turing machines directly, which can be far from ergonomic for languages like this. Counter machine proofs already deal with the dual stack handling business, and can greatly simplify proofs when working with languages that have access to unbounded integer variables. I'm confident you will be able to prove this language Turing complete. stkptr (talk) 09:09, 9 March 2025 (UTC)

I looked into tag systems and found BCT would be the easiest to implement—the binary nature already works well with Iterate's implicit execute–unless–zero rule —aadenboy (talk|contribs) 02:01, 16 March 2025 (UTC)