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.
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;
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 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 2n 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.
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
Since I/D Machine is Turing-complete, so is Nu.