TwoDucks

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.

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 at time t (in past or future) to the current value of v.
• 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.

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;

It has been alleged that the halting problem for a program can be solved in a similar manner to the last 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.)

// This program outputs an integer. Any integer.
SET x TO 0;
SET y TO 1;
NOUT x;
SEND x TO 1~0~{y}=1;

// This program is the halting oracle. NOTE: The program entered must not use SEND, otherwise a contradiction can arise.
SET halts TO 0
SET mark TO 1
NOUT halts
// Program goes here
SET halts TO 1
SEND halts TO 1~0~{mark}=1

However, attempting to run the oracle on anything that takes longer than about 10 seconds causes it to output 0. This will inevitably cause the user to abort the oracle, believing the code to take infinitely long, but aborting the program will retroactively cause the confusing output of 0. A possible solution is to resolve to wait for longer, say 100 seconds, before aborting, but the oracle will then produce 0 for anything that takes longer than 100 seconds. Even if you run the oracle until the end of the universe, the oracle will still only tell you if the program will take longer than until the end of the universe. Thus the oracle program given is little better than:

// This program is the halting oracle. Feel free to use SEND wherever you like.
// Run the oracle for an infinite length of time. If the oracle halted in that time, the input program halts.

// Program goes here

For the moment, the super-Turing-ness of TwoDucks is an open problem.