Nu

Nu is an object-oriented Turing tarpit designed by User:Caenbe. Despite its lack of numbers or arithmetic, it can express other Turing tarpits that involve incrementation and dereferencing, such as I/D machine and Three Star Programmer. The name was chosen to be reminiscent of Iota, and also to sound like "new", which is the keyword to create an object in C-like languages. Completely by accident, Nu has some similarities with #hell.

Syntax & Semantics

A name is a string of alphanumeric characters or underscores. An expression is a dot-separated list of one or more names.

The first name in an expression is a variable. Any subsequent names are properties, just like you would expect in C or Java. If a variable or property is referenced before it contains anything, it is automatically assigned to a new object.

The first type of command is assignment:

expression = expression;

The second type of command is jumping. A program may contain exactly one jump label, written as a single semicolon. At the end of the program is an implicit jump back to the jump label. So, the jump label separates the program into a "preamble" which runs once, and a loop which runs infinitely many times.

Examples

Here is a translation of the (boring) I/D Machine program IDIID:

ptr = 0;
max = 0;
;
max.d = 0;
max = max.i;
max.d = 0;
max = max.i;
max.d = 0;
max = max.i;
max.d = 0;
max = max.i;
ptr.d = ptr.d.i;
ptr = ptr.d;
ptr.d = ptr.d.i;
ptr.d = ptr.d.i;
ptr = ptr.d;

The preamble sets up the pointer and a variable called max, which is used to create numbers during the loop. Numbers are encoded as in Peano arithmetic (e.g. 5 is 0.i.i.i.i.i) and the .d property of a number is the value currently stored at that array index.

Here is a translation of the Three Star Programmer program 3 6 9, written along the same lines:

max = 0;
max.d = 0;
max = max.i;
max.d = 0;
max = max.i;
max.d = 0;
max = max.i;
max.d = 0;
max = max.i;
max.d = 0;
max = max.i;
max.d = 0;
max = max.i;
max.d = 0;
max = max.i;
max.d = 0;
max = max.i;
max.d = 0;
max = max.i;
max.d = 0;
max = max.i;
;
max.d = 0;
max = max.i;
max.d = 0;
max = max.i;
max.d = 0;
max = max.i;
0.i.i.i.d.d.d = 0.i.i.i.d.d.d.i;
0.i.i.i.i.i.i.d.d.d = 0.i.i.i.i.i.i.d.d.d.i;
0.i.i.i.i.i.i.i.i.i.d.d.d = 0.i.i.i.i.i.i.i.i.i.d.d.d.i;

Graph rewriting

Nu can be interpreted as a (multi-) graph rewriting automaton. The initial state is an infinitely deep directed tree, where each node has a countable infinity of out-edges, labeled with all possible names. An assignment manipulates the graph in this way:

• The left-hand side specifies an edge.
• The right-hand side specifies a node.
• The edge is redirected to point at the node.

In this view, the preamble can be seen as specifying the initial graph, and the loop can be seen as a rewrite rule.

In fact, the initial tree doesn't even need infinite branching, only as many branches per node as there are unique names in the program. The Three Star Programmer example above can be rewritten to use 2 names (by substituting max -> i and 0 -> d), and thus, a binary tree.

Binary Nu

Binary Nu is a version of Nu which allows 2 distinct names, and is written in binary. The first condition doesn’t hinder the expressivity of the language, because if every expression has a number of names divisible by n, this is equivalent to having 2ⁿ names.

The names are 00 and 01. Expressions are separated by 10 (dots and equal signs are inferred). The jump label is represented by 11. So, for example,

i = i.d; d = d.i; ; d.d.i = i.i.d;

could be encoded as

00 10 00 01 10 01 10 01 00 11 01 01 00 10 00 00 01

There is currently no implementation of Binary Nu.

Implementation

This is a Python 3 implementation with no error checking.

from collections import defaultdict
import re
def Nu(prgm):
	new_obj = lambda: defaultdict(new_obj)
	vars = new_obj()
	lines = re.sub('\s','',prgm).split(';')[:-1]
	i = 0
	while True:
		if lines[i] == '': jump_label = i
		exec("vars['"+lines[i].replace('.',"']['").replace('=',"']=vars['")+"']")
		i += 1
		if i == len(lines): i = jump_label

Computational class

Since I/D Machine is Turing-complete, so is Nu.