TwoDucks

From Esolang

TwoDucks is an esoteric programming language by User:Zzo38 which allows you to go back in time and change things. It is uncomputable on a Turing machine; it even allows you to solve the halting problem.

[edit] Syntax

Variables:

• You can have as many as you want, they can store any integers, and also can be array indexed as much as you want, for example: v, v[1], v[1][4], vv, vv[1], vv[2], are all distinct variables. The number in brackets can also be replaced by a expression.
• A label name is like a variable name, except that only constants (not expressions) are allowed inside brackets.

Commands: (n=number/expression, v=variable-name, l=label-name, c=command, t=time-expression)

• OUT n; Output a character
• IN v; Input a character
• NOUT n; Output a number
• NIN v; Input a number
• LABEL l; A label here
• GOTO l; Goto a label
• IF v THEN c; Conditional
• SET v TO n; Set value of a variable
• SEND v TO t; Assignment across time; assign the value of variable v (in the present) to the variable v as it existed at time t (in the past or future).
• GOSUB l; Call subroutine at label
• RETURN; Return from subroutine
• FORGET n; Discard the top return value on the call stack, like the INTERCAL FORGET command
• THREAD l; Make a new thread at label l from here, as a copy of the current thread, but with its own variable storage.
• END; End program or current thread
• "str"; Output the text
• Comments run from // to the end of the line.

Expressions:

• + - * / % Arithmetic operators (/ is integer division, % always returns positive if right operand is positive)
• = < > Compare (1=true, 0=false)
• Variable names are accepted in expressions; they return the value of the variable.
• & | ^ Bitwise operators
• () Parentheses are used to group expressions
• {n} Use in time expressions to use the value at that time instead of at now
• @n Can be used in place of a variable name, which uses variable n of parent thread
• 'c' Use ASCII value of the character (''' returns the ASCII value of an apostrophe)

Time-expressions:

• a~b~c b'th time since a is true that expression c is true (b=0 is first (right after it happens), b=1 second time, etc.) This can either refer to a time in the past or a time in the future.

[edit] Examples

// This program doesn't work because if it would output 1,
// that would cause it to have outputted 0 and vice versa,
// thus causing a time-travel paradox.
SET x TO 0;
SET y TO 1;
NOUT x;
SET x TO 1-x;
SEND x TO 1~0~{y}=1;

// This program returns the sum of two numbers (which are input after
// the sum has been printed).
SET a TO 1;
NOUT z;
NIN x;
NIN y;
SET z TO x+y;
SEND z TO 1~0~{a}=1;

The halting problem for a program can be solved in a similar manner to the previous example; add a command at the end of the program that assigns a value to a variable existing at the start of the program. If the program would end, that assignment is reached and changes that variable, which can be printed out right at the start; the program will then run. (If it turns out that it is, in fact, infinite, the user is advised to intervene and abort execution; if the program is finite, the user must not do this, so as not to cause a paradox.)