Mu6
Paradigm(s)  functional 

Designed by  BMO 
Appeared in  2018 
Computational class  Turing complete ([1]) 
Major implementations  mu6 
File extension(s)  .mu 
μ6 derives its name from the μoperator and base6 because the language is an extension of the μrecursive functions and it uses numbers in base6. Working solely with μrecursive is very tedious because they are N^n > N and thus one needs to encode the datastructures as integers, thus μ6 adds the following three functions to the 6 μrecursive operators:
,
is the encoding function, taking n integers and encoding them as a nested tuple<
is one of the decoding functions, taking a tuple and returning the left element>
is the other decoding function, taking a tuple and returning the right element
Syntax
A program consists of one function and possibly of an arbitrary number of constant inputs to that function. The source is parsed in nibbles, in case the number of nibbles of the source is odd a 0000
nibble is prepended (no valid μ6 program starts with that).
This is the list of all available tokens:
nibble  ASCII  Description 

0000

0

digit 0 
0001

1

digit 1 
0010

2

digit 2 
0011

3

digit 3 
0100

4

digit 4 
0101

5

digit 5 
0110

[

begin of function composition 
0111

]

end of function composition 
1000

/

projection 
1001

.

constant zerofunction 
1010

+

successorfunction 
1011

,

pairingfunction 
1100

<

left of pair or const 
1101

>

right of pair or const 
1110

#

primitive recursion 
1111

@

μoperator (minimisation) 
Program structure
PROGRAM = FUNCTION [ INPUTS ]? NUMBER = [ '0' .. '5' ]+ INPUTS = NUMBER [ ',' NUMBER ]* FUNCTION = ATOM  PROJ  COMP  PRIM  MU ATOM = '.'  '+'  ','  '<'  '>' PROJ = '/' NUMBER COMP = '[' FUNCTION FUNCTION* ']' PRIM = '#' FUNCTION FUNCTION MU = '@' FUNCTION
Semantics
A program encodes one function  say F  and optionally several constant inputs c_{0}...c_{N}, running a program with user provided inputs x_{0}...x_{N} will evaluate F(c_{0}...c_{N},x_{0}...x_{N}) and print its result. No arguments default to zero.
In case the a
(ascii
) flag is given to the interpreter, the result will be flattened, each number converted to ASCII and the resulting string will be printed instead.
Overview of the operators
This is a quick overview of all the available operators:
.
constant zero function
This function returns zero for any inputs.
+
successor function
This function extracts the first argument, increments it and returns the result (defaults to 0+1 = 1 if no inputs are given).
,
encoding/decoding function
This operator works on the first argument:
 if it's a single argument: map it to an integer using the internal decoding function
 else: builds a nested tuple of all its arguments
<
and >
decoding/encoding operators
These work on the first argument:
 if it is a tuple: they will extract the left or right element of it
 else: they will use the internal encoding function to map the integer to a tuple
/
the projection operator
This operator followed by a base6 number N will extract the Nth argument (0indexed) and return it, if there is no Nth argument it will default to zero.
[
..]
function composition
This construct must contain at least one function F and any number of functions G_0 to G_N, it composes F with (G_0,...,G_N), so:
[F G_0 .. G_N](x0..xK) = F(G_0(x0..xK)..G_N(x0..xK))
#
the ρoperator
The primitive recursion operator must be given two functions F and G (note how they are expected to have different arities), it works like this:
ρ(F,G)(0,x0..xN) = F(x0..xN) ρ(F,G)(n+1,x0..xN) = G(n, ρ(F,G)(n,x0..xN), x0..xN)
@
the μoperator
The minimisation operator takes one function F and evaluates as follows:
μ(F)(x0..xN) = min_z { z  F(z,x0..xN) == 0 }
Internal decoding/encoding function
The additional operators ,<>
allow us to work with nested tuples, usually these are not stored as a single integer for performance reasons (at least in the original mu6
implementation), but you can still map tuples to integers and vice versa. The mapping is bijective.
It's based on a primitive recursively computable bijection NxN ⟷ N, its usage to compute the mappings from nested tuples to integers and back is total. From that follows that the language itself without @
is not Turing complete.
Examples
Since reading nibbles is not fun, these examples use the ASCII tokens enabled by using the v
flag:
Hello, World!
,200,245,300,300,303,112,52,223,303,310,300,244,53
Addition
#/0[+/1]
Subtraction
#/0[#./0/1]
Multiplication
#.[#/0[+/1]/1/2]
Fibonacci
[<#[,.[+.]][[,>[#/0[+/1]<>]]/1]]
Truthmachine
As there is no I/O during a computation a truthmachine is not possible to program. However this will print 0
with 0
as input and loop indefinitely with a nonzero input:
@[#/0[+/1]/1]