Action symbol

Action symbol is a simple Matrioshka language based on the danish word for ". It was created by User:Yayimhere.

How it works

The program has two types of syntax:

• x[y](z) will create an operator x with input y, that will return the result of expression

z, which allows y as a variable, which will be replaced with the input.

• x!y will apply x to y (this is an optional piece of the language, as two non-bracketed symbols next to each other is also application).
• "x will evaluate x. Normally an expression is not evaluated unless its needed (which is lazy evaluation). " will however always be evaluated.
• »x« brackets around x.
• #x will not allow x to be evaluated until it is fed to a ".

Programs are evaluated left to right. Functions are allowed to be left without an input, however are still "waiting" for one.

Relation to lambda calculus

Here is a translation from Action symbol to lazy lambda calculus with variables:

• {x[y](z)} is x = λy.{z}
• {"x} is (λy.y) {x}
• {x!y} is {x} {y}
• {»x«} is ({x})
• {#x} is {x}

where {...} converts ... to lambda calculus.

Examples

Create the omega operator as o:

w[x]("»x!x«)
o[x]("»w!w«)

Create the K operator from SKI:

j[y]("x)
k[x]("j)

Computational class

Action symbol is trivially Turing-compete via translation from Underload. P denotes the whole program string, while xyz... denotes every command within the program string:

{P} -> :[x](#»"x "x«)
"»{xyz...}«

{xyz...} -> {x}{y}{z}{...}

{(x):} -> :{(x)}

{(x)^} -> "{(x)}

(x) -> #»{x}«

Recursive application of this translation will result in an Action symbol program. As visible, only []()#"»« is needed for Turing-completeness. To give an example of the translation, I will give one of the Underload program (:^):^:

:[x](#»"x "x«)
"»":#»":««