Newer version: R function v2.0.1

R function II is the second version of R function. It's not an extension of original R function.



The syntax of R function II is nRS, where -

  • n is a positive integer, here called "base number"
  • R is a symbol for the function
  • S is a string made up of lbrace ("{"), rbrace with left-superscript "+m" (here m is a non-negative integer) (i.e. "+m}")and non-negative integers; S must suit these properties shown below:
  1. In any part of S, the nested level must be greaterequal to 0, and the end of S must has nested level 0
  2. In S, the rbrace of any brace mustn't be immediately after the lbrace of that brace
  3. We call a brace separator iff the superscript of it is "+m" with m > 0. In S, there must be a number or a brace not separator immediately after the lbrace or the rbrace of any separator

And there're some shorthands:

  • The left-superscript "+0" can be omitted, and the left-superscript "+1" can be written as "+".
  • {0+1} can be also written as a comma.

Main process

Scan and apply rules. Case A1, A2, A3, B1 and B2 are terminal, but A4, B3 and C are not. After you apply a terminal rule, you'll return here, then you can choose any R to start scanning.

Scanning starts at the R symbol. Scan from left to right. There're 3 kinds of things we scan - 0, non-0 numbers and braces not a separator. Before scanning, set s = 1, and save the whole string to A1 (that's for case A3).

  • Case A: If there's a 0,
  • Case A1: If nothing is after it(or an R symbol immediately after it, this also mark the end), then apply \(nR0=2^n\). And return.
  • Case A2: If a simple rbrace (m=0, or no +m's for shorthand) is immediately after it, that means the brace is equvalent to {0}. So change it into number 1. And return.
  • Case A3: If an rbrace with +m's (m > 0) is immediately after it, that means the whole brace is the standard m-separator \(\{0^{+m}\}\).
  1. Let Ss = \(\{0^{+m}\}\), set t = s
  2. Repeat this:
    1. Subtract t by 1
    2. Let St be the brace such that "nested level of St = nested level of St+1 - 1" and "St+1 is inside St"
    3. If t = 1, then break the repeating, or else continue repeating.
  3. Set k = m, s(m) = s, B(m) = \(\{0^{+(m-1)}\}\), string X(m) = \(\{0\) and Y(m) = \(1^{+(m-1)}\}\).
  4. Repeat this:
    1. Subtract k by 1
    2. Set s(k) = s(k+1)
    3. Repeat this:
      1. Subtract s(k) by 1
      2. If level of As(k) < level of As(k+1), then break the repeating, or else continue repeating.
    4. If level of As(k) < level of B(k+1), then let string P and Q be such that A1 = P As(k)+1 Q, then change the original brace A1 into P X(k+1) As(k)+1 Y(k+1) Q, and return. Or else -
    5. If k = 0, then break the repeating, or else -
    6. Let string X(k) and Y'(k) be such that Ss(k) = X(k) Ss(k+1) 1 Y'(k), set Y(k) = 1 Y'(k) and set B(k) = X(k) Y'(k).
  5. Let string P and Q be such that Ss(0) = P Ss(1) Q, then apply Ss(0) = P P ... P P Q Q ... Q Q with n P's and n Q's, and return.
  • Case A4: Otherwise, continue scanning to right.
  • Case B: If there's a non-0 number, delete 0's immediately before it until there isn't one, then
  • Case B1: If R is immediately before it, then apply \(nRa+1\odot=(\cdots(nRa\odot) Ra\odot\cdots) Ra\odot\) with n \(Ra\odot\)'s. And return.
  • Case B2: If lbrace is immediately before it, then apply \(\{a+1\odot\}=\{a\odot\}0\{a\odot\}0\cdots0\{a\odot\}\) with n \(\{a\odot\}\)'s (here n is the base number). And return.
  • Case B3: If a separator is immediately before it, then apply \(\{\odot\}a+1=\{\odot\}1\{\odot\}a\), add s by 1 then set As = \(\{\odot\}\), then scan on the first \(\{\odot\}\).
  • Case C: If there's a brace not separator, add s by 1 then set As to that brace, then continue scanning inside it.

The \(\odot\) can be any string or empty.


First, we see the whole string after the "R" as an invisible brace here and it has the lowest level (and it cannot appear in other places), 0 has the second lowest level, and others have higher level. We can compare the level of A and B as follows:

  • Use subrule on A and B until the subrule cannot apply any more.
  • Change all the positive integer k into {0}{0}...{0} with k {0}'s.
  • Let \(A=\{A_I^{+a}\}\) and \(B=\{B_I^{+b}\}\)
  • If a>b then A>B on level; If a<b then A<B on level. or else -
  • All the separators of A are {A1}, {A2},... {An}. And the same as B.
  • Compare levels of {Ai}'s and find highest-level ones - {AM}. And the same as B.
  • If level of {AM}>{BM}, then A>B; if {AM}<{BM}, then A<B. or else -
  • If the amount of {AM}>{BM}, then A>B; if the amount of {AM}<{BM}, then A<B. or else -
  • Find the last {AM} of A, and A={A-{AM}A+} and the same as B.
  • If the level of {A+}>{B+}, then A>B; if {A+}<{B+}, then A<B. or else -
  • If the level of {A-}>{B-}, then A>B; if {A-}<{B-}, then A<B; if {A-}={B-}, then A=B.


What's new in R function II:

  • Remove the ill-definition of enclosers. The cost is, the rules become more complex.
  • Using superscript "+m" to present the "brace rank" \(\{A^{+m}\}\). This allow something like \(nR\{0\{0^{+8}\}2\}\), which must be written as many braces as nR{0{0{0{0{0{0{0,,,,,,,2}1}1}1}1}1}1} in the version 1.
  • The "brace rank" has an offset. {0+1} (or the comma, or {0+}) in version 2 is corresponding to the {0,1} in version 1, {0+2} in version 2 is corresponding to the comma in version 1, {0+(m+1)} in version 2 is corresponding to the m-ple comma in version 1. That make LAN in R function II much weaker, but the final strength of the two version are the same.
  • The {0} doesn't reduce to n, but reduces to 1. So we can use an expression such that numbers over 1 don't appear in the string.
  • Change the base rule a little. But this doesn't affect much.

Up to linear array notation

Basic R function remains almost the same. Just the base rule changes - now It's nR0 = 2^n.

The {0} doesn't reduce to n, but reduces to 1, so the brace notation change a little.

Here I bring something called standard string. A standard string doesn't contain numbers over 1, that means, only 0 and 1 appear. For example, 3R2 = 3R1R1R1, and at the same time 3R{0}{0} = 3R1{0} = 3R{0}R{0}R{0} = 3R1R1R1 - they are the same! nR{{2}{3}} and nR{{1{0}}{1{0}{0}}} are the same, too. Notice that a {0} reduces to 1 no matter what the base number n is, so we can change {0} into 1, change 1 into {0} at any time (but we must use {0}'s when compare levels). So a number k is equivalent to the string {0}{0}...{0} with k {0}'s.

However, linear array notation changes a lot. For example, 3R{{0,2},2} = 3R{{0{0{01,1}1,1}1,1},2} = 3R{{{{1,1}{0},1}{0},1},2} (exactly) = 3R{{{{1,1},1},1},2} (approximately), while in version 1 3R{{0,2},2}= 3R{{{{{{0,2},1},2},1},2},1}, the latter one is larger.

A more complex example: how to solve 3R{0,{0,0,2},3}{0,0,{1}}. First scanning, when we scan to the comma, the brace become 3R{0,{0,0,1,1},3}{0,0,{1}}, and now we meet case A3. Here A1 = {0,{0,0,2},3}{0,0,{1}}, A2 = {0,{0,0,2},3}, A3 = {0,0,2}, A4 is comma. Then step 1 and 2: S1 = {0,{0,0,1,1},3}{0,0,{1}}, S2 = {0,{0,0,1,1},3}, S3 = {0,0,1,1}, S4 is comma. Then step 3: m = 1, so set k = 1, s(1) = 4, B(1) = {0}, X(1) = "{0", Y(1) = "1}". Then step 4. Step 4.1: set k = 0. Step 4.2: set s(0) = 4. Step 4.3 is the "searching process", we get s(0) = 3 finally. Passing step 4.4, and break the repeating in step 4.5. Step 5: P = "{0,0", Q = "1,1}", then apply {0,0,1,1} -> {0,0{0,0{0,01,1}1,1}1,1} = {0,{0,{0,1,1}{0},1}{0},1}. When we finally return, we get 3R{0,{0,0,2},3}{0,0,{1}} = 3R{0,{0,{0,{0,1,1}{0},1}{0},1},3}{0,0,{1}}.

In LAN, it seems that B(k), X(k), Y(k) and step 4.4 are no use, and we just simply get s(0) = s(1) -1 in step 4.3 of case A3.

And more, we can write a ruleset for LAN as follows. The 5th rule changes and make LAN weaker.

  1. \(nR0=2^n\)
  2. \(nRa+1\odot=nRa\odot Ra\odot...Ra\odot\) with n R's.
  3. \(nR\oslash\{0\}\odot=nR\oslash 1\odot\)
  4. \(nR\oslash\{a+1\odot_1\}\odot_2=nR\oslash\{a\odot_1\}\{a\odot_1\}...\{a\odot_1\}\odot_2\) with n \(\{a\odot_1\}\)'s.
  5. \(nR\oslash_2\{\oslash_10,a+1\odot_1\}\odot_2=\)  \(nR\oslash_2\{\oslash_1\{\oslash_1...\{\oslash_11,a\odot_1\}...1,a\odot_1\}1,a\odot_1\}\odot_2\) with n \(\{\oslash_1\)'s and n \(1,a\odot_1\}\)'s.
  6. 0 is default, so 0's immediately before a brace can be removed, and the same to 0's at the end of an array. i.e. 0{={ and ,0}=}
Community content is available under CC-BY-SA unless otherwise noted.