909. L-expressions I

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

• a natural number;

• the symbol $A$$A$;

• the symbol $Z$$Z$;

• the symbol $S$$S$;

• a pair of L-expressions $u,v$$u, v$, which is written as $u(v)$$u(v)$.

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

• $A(x)\to x+1$$A(x) \to x + 1$ for any natural number $x$$x$;

• $Z(u)(v)\to v$$Z(u)(v) \to v$ for any L-expressions $u,v$$u, v$;

• $S(u)(v)(w)\to v(u(v)(w))$$S(u)(v)(w) \to v(u(v)(w))$ for any L-expressions $u,v,w$$u, v, w$.

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

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

Find the result of the L-expression $S(S)(S(S))(S(S))(S(Z))(A)(0)$$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.

909. L-表达式 1

我们按如下规则递归定义 L-表达式：

• 一个自然数是 L-表达式。

• 符号 $A$$A$ 是 L-表达式。

• 符号 $Z$$Z$ 是 L-表达式。

• 符号 $S$$S$ 是 L-表达式。

• 一对 L-表达式 $u,v$$u, v$ 是 L-表达式，这个 L-表达式记作 $u(v)$$u(v)$。

我们可以按如下规则对 L-表达式进行转化：

• 对诸自然数 $x$$x$，$A(x)\to x+1$$A(x) \to x + 1$；

• 对任意 L-表达式 $u,v$$u, v$，$Z(u)(v)\to v$$Z(u)(v) \to v$；

• 对任意 L-表达式 $u,v,w$$u, v, w$，$S(u)(v)(w)\to v(u(v)(w))$$S(u)(v)(w) \to v(u(v)(w))$。

例如，不断使用上述规则可以将 L-表达式 $S(Z)(A)(0)$$S(Z)(A)(0)$ 转化为数字 $1$$1$：

同样的，不断使用上述规则可以将 L-表达式 $S(S)(S(S))(S(Z))(A)(0)$$S(S)(S(S))(S(Z))(A)(0)$ 转化为数字 $6$$6$。

不断使用上述规则，求出 L-表达式 $S(S)(S(S))(S(S))(S(Z))(A)(0)$$S(S)(S(S))(S(S))(S(Z))(A)(0)$ 对应的数字。你只需给出答案的末 9 位数字。

注释： 可以证明，本题中涉及的 L-表达式只能被转化有限次，且转化的最终结果和转化的顺序无关。

点 这个链接 回到源站。

点 这个链接 回到详细版题目目录。