1cnis
1cnis is an esoteric programming language created by User:ais523 in 2007. It is deliberately designed to be Turing-incomplete; its purpose is to provide a language in which to express single-counter neighbour-independent substitution systems, and therefore can create the same output as those systems can; it is designed to create infinite initial conditions for use by systems such as Turing machines, and has features designed to make infinite output possible, even though it's a rewriting language with finite input programs.
Syntax
A 1cnis program consists of three sections, the initial condition, rules, and translation sections, started with lines containing [initial], [rules], and [translation] respectively. (In all syntax of the language, whitespace is significant, although case isn't, and trailing spaces on a line are ignored; this means that, for instance, programs can't contain blank lines. Programs must end with a newline.) 1cnis programs must be finitely long.
The initial condition consists of a list of elements; each element consists of one of a finite set of symbols (a program can use any finite number of symbols), represented as a case-insensitive string of letters, followed immediately by a nonnegative integer. Elements in the list are separated by whitespace. For instance,
[initial] l0 o0 x0 v0 v0 r0
(In this case, all the integers were 0, but it's legal to use other values, and all the symbols were one-character, although they could have been longer. The integers are meant to be unbounded, although the implementation below doesn't currently handle this.) The language works by maintaining one list and continuously rewriting it; this section gives the initial value of the list.
The rules section contains a list of transformation rules that are used to rewrite the elements of the language. They consist of a one-element list, then the string > (that's a greater-than sign with a space each side of it), then a list that gives the replacement for the one-element list. Instead of specifying the lists as constant lists, though, with a constant symbol and integer, the only values that can be specified for the integer are 0 (zero) and ? (nonzero) for the element to replace, and + (one more than the integer of the element being replaced), - (one less than the integer of the element being replaced; this shouldn't be used if the integer is given as 0 on the left-hand side), and = (equal to the integer of the element being replaced). This means that the integer in effect acts like a single counter. Here's an example rules section to show the formatting (note that transformation rules that can never come up need not be given, but it's an error not to provide a rule for an element that comes up during the course of the program):
[rules] l0 > l= o= o0 > o= z0 > z= o= r? > x= v= v= v= x+ v+ v+ r+ r0 > x= v= v= v= x+ v+ v+ r+ x? > x- v- v- x0 > z= v? > v- v0 > o=
The translation section contains a mapping from symbols onto strings of output. It's not the internal list that's output by the program (although this can be useful for debugging); instead, the symbols in the elements of the internal list are mapped into strings of output using rules in the translation section, and that's what's output. It's legal to map a symbol onto the null string, or onto a string of any positive length; all symbols must be given a mapping. For instance:
[translation] l > o > 1 z > 0 r > x > v >
Execution
A 1cnis program starts out with the initial list, and that list is constantly rewritten according to the rewriting rules and output. To be precise, at each step of execution, each element in the list is replaced by its replacement according to the rules; then, the translation of the list is output. This is what happens with the example program given above (in this case, the internal list is also shown to give an idea of what's going on):
- l0 o0 x0 v0 v0 r0
- 1
- l0 o0 o0 z0 o0 o0 x0 v0 v0 v0 x1 v1 v1 r1
- 11011
- l0 o0 o0 o0 z0 o0 o0 o0 z0 o0 o0 o0 x0 v0 v0 v0 v0 x1 v1 v1 v1 x2 v2 v2 r2
- 11101110111
- l0 o0 o0 o0 o0 z0 o0 o0 o0 o0 z0 o0 o0 o0 o0 z0 o0 o0 o0 o0 x0 v0 v0 v0 v0 v0 x1 v1 v1 v1 v1 x2 v2 v2 v2 x3 v3 v3 r3
- 1111011110111101111
- l0 o0 o0 o0 o0 o0 z0 o0 o0 o0 o0 o0 z0 o0 o0 o0 o0 o0 z0 o0 o0 o0 o0 o0 z0 o0 o0 o0 o0 o0 x0 v0 v0 v0 v0 v0 v0 x1 v1 v1 v1 v1 v1 x2 v2 v2 v2 v2 x3 v3 v3 v3 x4 v4 v4 r4
- 11111011111011111011111011111
One special case of an input program is one where the initial list is one element long, and the replacement rule for that element contains exactly one copy of itself; this is known as a self-embedding 1cnis program. Such programs are capable of producing finite output or output infinite in one or both directions; the point is that each output contains the previous output as a substring, so that in a sense the successive outputs are converging to a (finite or infinite) limit, which is the finite output string. Here's an example (its output in the limit is the entire infinite Thue-Morse sequence):
[initial] x0 [rules] x0 > x= y= y0 > y= x= [translation] x > 0 y > 1
- x0
- 0
- x0 y0
- 01
- x0 y0 y0 x0
- 0110
- x0 y0 y0 x0 y0 x0 x0 y0
- 01101001
- x0 y0 y0 x0 y0 x0 x0 y0 y0 x0 x0 y0 x0 y0 y0 x0
- 0110100110010110
- x0 y0 y0 x0 y0 x0 x0 y0 y0 x0 x0 y0 x0 y0 y0 x0 y0 x0 x0 y0 x0 y0 y0 x0 x0 y0 y0 x0 y0 x0 x0 y0
- 01101001100101101001011001101001
Applications
The purpose of the language is for the set of possible outputs in the limit of self-embedding 1cnis programs that can be calculated from some input in a known-in-advance-to-be-finite time to serve as a set of possible legal initial conditions when deciding whether a system is Turing-complete or not. It's somewhat hard to determine what sort of inputs should be allowed and which ones shouldn't be; clearly, for instance, embedding an oracle, or a complete debug history of the program to be run, could make obviously Turing-incomplete systems seem Turing-complete. Using self-embedding 1cnis outputs is one way to solve this problem.
Implementation
This is a reference implementation in Perl (except that it can't handle arbitrary-size integers, and ought to be able to); sample usage would be perl 1cnis.pl -o count.1ni, where -o tells it to just output the output of the program. (-io is useful for debugging.) It will continue as long as it receives nothing but newlines on standard input.
#!/bin/perl -w
use strict;
$|=1;
# Check options.
my $opts='iou';
$ARGV[0]=~/^\-/ and $opts=shift @ARGV;
# Read in the program.
$_="\n";
$_=<> while $_ eq "\n";
/^\[initial\] *\n/i or do{print STDERR "[initial] line not found"; exit 1;};
my $list="\n";
$list=<> while $list eq "\n";
chomp $list;
$_="\n";
$_=<> while $_ eq "\n";
/^\[rules\] *\n/i or do{print STDERR "[rules] line not found"; exit 1;};
my %rules=("" => "");
while(<>)
{
chomp;
next if $_ eq "";
last if /^\[translation\] *$/;
/^([a-zA-Z]+[0\?]) >(( [a-zA-Z]+[+=-])*) *$/
or do{print STDERR "invalid rule format"; exit 1;};
$rules{lc($1)}=$2;
}
/^\[translation\] *$/ or
do{print STDERR "[translation] line not found"; exit 1;};
my %translations=("" => "");
while(<>)
{
chomp;
next if $_ eq "";
/^([a-zA-Z]+) > ?(.*?) *$/
or do{print STDERR "invalid translation format"; exit 1;};
$translations{lc($1)}=$2;
}
# Calculate the evolution of the system and the output as long as the user
# inputs nothing but blank lines.
$_=$list;
goto FIRSTLOOP; # we want to start in the middle of the loop
while(<> eq "\n")
{
my $temp;
$_=join "", (@_=map
{
/([a-zA-Z]+)([0-9]+)/ or
do{print STDERR "invalid element format"; exit 1;};
my $t=$2;
$t>0 and $_=$1 . "?";
defined $rules{lc($_)} or
do{print STDERR "no rule found for ".$_; exit 1;};
$_=$rules{lc($_)};
s/\+/$t+1/ge;
s/\=/$t/ge;
s/\-/$t-1/ge;
$_;
} split);
FIRSTLOOP:
$opts=~/i/ and print "$_\n";
$temp=join "", (map
{
/([a-zA-Z]+)([0-9]+)/ or
do{print STDERR "invalid element format"; exit 1;};
defined $translations{lc($1)} or
do{print STDERR "no translation found for ".$1;
exit 1;};
$_=$translations{lc($1)};
} split);
print "$temp\n" if $opts=~/o/;
print +(join ",", (map length($_), split("0",$temp))) . "\n"
if $opts=~/u/;
}