# Mu6

Paradigm(s) functional BMO 2018 Turing complete () mu6 `.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 c0...cN, running a program with user provided inputs x0...xN will evaluate F(c0...cN,x0...xN) 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
```

```#/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
```