Iterate/Turing-completeness proof

← Back to Iterate

This proves Iterate's Turing completeness by implementing Bitwise Cyclic Tag.

Specification

Let L1 be a single cycle of the execution sequence, stored in base 10.
Let L2 be the length of L1.
Let L3 be the data string, stored in base 10.
Let L4 be the size of L3.
Let L5 and L6 be intermediary values.

Execution:
    Halt the program if L4 is equal to 0 (that is, L2 is empty).
    Cycle L1:
        Reset L5 and L6.
        Divide L1 by 2. Store the quotient into L5 and the remainder into L6.
        Set L1 to L5.
        Add L6 times L2 to L1.
    If L6 == 1:
        Cycle L1:
            Reset L5 and L6.
            Divide L1 by 2. Store the quotient into L5 and the remainder into L6.
            Set L1 to L5.
            Add L6 times L2 to L1.
        Peek from L3:
            Reset L5.
            Modulo L3 by 2. Store the remainder into L5.
        If L5 == 1:
            Add 1 to L4.
            Add L6 times L4 to L3.
    Else:
        Subtract 1 from L4.
        Pop L3.
    Repeat.

Code

This will use the first example program provided on BCT's page.

(*)1<
  // Initial values
  * 7< (1*)<> > // 0b00111 = 7
  *32< (2*)<> > // 2^5 = 32
  * 5< (3*)<> > // 0b101 = 5
  * 8< (4*)<> > // 2^3 = 8

  // Execution
  (7*)∞<
    // Halt if L4 == 0
    (8*)< *=4< !8 > !^ >

    // Cycle L1
    *1<
      // Pop L1
      $5 $6 $11
      *2< (11*)<> >
      (9*)=1< // Divide L1 by 2
        (6*)<>
        $10
        *=11< (10*)<> >
        $11
        *=10<           
          *~n< (11*)<> >
          !
        >
        *=11< &9 >
        $6
        *2< (11*)<> >
        (5*)<>
      >

      // Update L1 and push-bottom L6
      $1
      *=5< (1*)<> >
      *=6< *=2< (1*)<> > > // L6 * 2
    >

    // L1 == 1
    *=6<
      // Cycle L1
      *1<
        // Pop L1
        $5 $6 $11
        *2< (11*)<> >
        (9*)=1< // Divide L1 by 2
          (6*)<>
          $10
          *=11< (10*)<> >
          $11
          *=10<           
            *~n< (11*)<> >
            !
          >
          *=11< &9 >
          $6
          *2< (11*)<> >
          (5*)<>
        >

        // Update L1 and push-bottom L6
        $1
        *=5< (1*)<> >
        *=6< *=2< (1*)<> > > // L6 * 2
      >

      // Peek L3
      *1<
        $5 $11
        *2< (11*)<> >
        (9*)=3< // Divide L3 by 2
          (5*)<>
          $10
          *=11< (10*)<> >
          $11
          *=10<           
            *~n< (11*)<> >
            !
          >
          *=11< &9 >
          $5
          *2< (11*)<> >
        >
      >

      // L5 == 1
      *=5<
        // Push L6
        *2< *=4< (4*)<> > > // L4 * 2
        *=4< *=6< (3*)<> > >
      >

      // Continue
      &7
    >

    // Else
    // Pop L3
    *1<
      // Update length
      *1<
        // Divide L4 by 2
        $5 $6 $11
        *2< (11*)<> >
        (9*)=4< // Divide L4 by 2
          (6*)<>
          $10
          *=11< (10*)<> >
          $11
          *=10<           
            *~n< (11*)<> >
            !
          >
          *=11< &9 >
          $6
          *2< (11*)<> >
          (5*)<>
        >

        // Update L4
        $4
        *=5< (4*)<> >
      >

      // Pop L3
      *1<
        $5 $6 $11
        *2< (11*)<> >
        (9*)=3< // Divide L3 by 2
          (6*)<>
          $10
          *=11< (10*)<> >
          $11
          *=10<           
            *~n< (11*)<> >
            !
          >
          *=11< &9 >
          $6
          *2< (11*)<> >
          (5*)<>
        >

        // Update L3
        $3
        *=5< (3*)<> >
      >
    >
  >
>