0%

Problem 909


Problem 909


$L$-expressions I

An $L$-expression is defined as any one of the following:

  • a natural number;
  • the symbol $A$;
  • the symbol $Z$;
  • the symbol $S$;
  • a pair of $L$-expressions $u, v$, which is written as $u(v)$.

An $L$-expression can be transformed according to the following rules:

  • $A(x) \to x + 1$ for any natural number $x$;
  • $Z(u)(v) \to v$ for any $L$-expressions $u, v$;
  • $S(u)(v)(w) \to v(u(v)(w))$ for any $L$-expressions $u, v, w$.

For example, after applying all possible rules, the $L$-expression $S(Z)(A)(0)$ is transformed to the number $1$:
$$S(Z)(A)(0) \to A(Z(A)(0)) \to A(0) \to 1.$$
Similarly, the $L$-expression $S(S)(S(S))(S(Z))(A)(0)$ is transformed to the number $6$ after applying all possible rules.

Find the result of the $L$-expression $S(S)(S(S))(S(S))(S(Z))(A)(0)$ after applying all possible rules. Give the last nine digits as your answer.

Note: it can be proved that the $L$-expression in question can only be transformed a finite number of times, and the final result does not depend on the order of the transformations.


$L$-表达式(一)

一条$L$-表达式可以是以下任意一种:

  • 一个自然数;
  • 符号$A$;
  • 符号$Z$;
  • 符号$S$;
  • 一对$L$-表达式$u, v$,并记作$u(v)$。

$L$-表达式可以按照以下规则进行转换:

  • 对任意自然数$x$,$A(x) \to x + 1$;
  • 对任意$L$-表达式$u, v$,$Z(u)(v) \to v$;
  • 对任意$L$-表达式$u, v, w$,$S(u)(v)(w) \to v(u(v)(w))$。

例如,在应用所有可能的规则后,$L$-表达式$S(Z)(A)(0)$可以被转换为数$1$:
$$S(Z)(A)(0) \to A(Z(A)(0)) \to A(0) \to 1.$$
类似地,$L$-表达式$S(S)(S(S))(S(Z))(A)(0)$在应用所有可能的规则后被转换为数$6$。

求$L$-表达式$S(S)(S(S))(S(S))(S(Z))(A)(0)$在应用所有可能的规则后的结果,并给出最后九位数字作为你的答案。

注意:可以证明,本题所涉及的$L$-表达式只能被应用有限次转换,且最终结果不依赖于转换的顺序。