User:Zzo38/Untitled 4

The program is a list of commands, with spaces in between. Each command is either passive or active. Comments are allowed, and start with a semicolon and end at a line break.

In the lists below, n means a name (zero or more characters which can be uppercase and lowercase ASCII letters and digits, and underscores); c means another command (which can be any passive or active command, including another of the same kind).

The passive commands are:

• ]
• n+
• n*c

The active commands are:

• n[ - Find the matching ] command; if there is none, then it is an error. This is nested blocks of commands where only [ and ] commands count (a [ or ] command that is the argument of a * command doesn't count). Delete this command and all commands up to and include the matching ] command, and replace them with the number of copies of all of the commands within the outer [ and ], where the number of copies is equal to the number of + commands with the same name that precede it.
• n= - Delete itself and all (passive) commands before it that have the same name.
• n! - Replace it with a copy of all * commands before it that have the same name, but with n* removed, followed by a copy of all passive commands before this ! command that have the same name as this one, and then also delete all passive commands before this command that have the name of this command.

The execution is then as follows: Find the first active command in the program, execute it, and repeat until the program contains no active commands.

Examples

The IINL ("increment in nested loops") function can be defined as:

; Prefix by the number of X+ of the input.
X[ A*X[ ] A*X+ X[ A*] ] A! A=
; The result is the number of X+ of the output.

You can then calculate IINL^IINL(3)(0) by:

X+ X+ X+ X[ A*X[ ] A*X+ X[ A*] ] A! A=
X[ B*X[ B*A*X[ B*] B*A*X+ B*X[ B*A*] B*] B*A! B*A= ]
X= B! B=

U4_0 function

The U4_0(X) function is defined as the largest number that can be computed by a Zzo38/Untitled 4 program with X commands. Once the program reaches the final state with only passive commands, choose the name with the most + commands that have that name; the value of U4_0(X) is how many + commands with that name. Programs with errors are not counted.

The function U4_1 is like U4_0 but also allowing a command to compute U4_0. U4_2 is like U4_0 and U4_1 but allowing a command to compute U4_0 and also a command to compute U4_1 is available too. These extra commands are considered to be active commands with only a name. Find the number of + commands with the same name that come before it, delete them, use that number as input, and replace this active command with the number of + commands of that same name which is the answer of that function.

Another function is also defined: I4_0(X) is the length of the shortest program which computes X. (This must be less than or equal to X, while U4_0(X) must be greater than or equal to X.) I4_1(X) allows the program to calculate U4_0 (not I4_0) with one command, like U4_1 does.

The function with two underscores is also defined: U4__0 is like U4_1, but instead of allowing a command to compute U4_0(X), it allows a command to compute U4_X(X). Similarly, U4__1 allows calculating U4__0(X) in addition to U4_X(X), and U4__2 allows calculating U4__1(X) in addition, too.