Mu6

μ6

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 zero-function
1010	+	successor-function
1011	,	pairing-function
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₀...c_N, running a program with user provided inputs x₀...x_N will evaluate F(c₀...c_N,x₀...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 (0-indexed) 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]]

Truth-machine

As there is no I/O during a computation a truth-machine is not possible to program. However this will print 0 with 0 as input and loop indefinitely with a non-zero input:

@/1