# μCurse

µCurse is a Turing-complete, purely functional language based on µ-recursive functions. It was created on May 21st, 2014 by User:Sacchan.

## Structure

Each µCurse-program describes a function from a tuple of natural numbers to a natural number. As it is a purely functional language, there are no side-effects and no output besides the computed result.

## Syntax and Semantics

There are six basic building blocks in µCurse, all of which describe either a primitive function or an operation to create a function from other functions. These are:

• S, the unary successor function
• C, the constant zero function
• Pi, the tuple projection function for the i-th element (i.e. Pi(x1,...,xn) = xi)
• A, the function application/concatenation operator
• R, the primitive recursion operator
• M, the µ-Minimization operator

S, C and Pi are functions by themselves, A, R and M can be used to create new functions from other functions. The syntax is as follows (note that x is a vector of input values, of arbitrary size):

```Ag(h1) means g(h1(x))
Ag(h1h2h3) means g(h1(x),h2(x),h3(x))

Rgh gives function f: f(x,0) = g(0), f(x,S(y)) = h(x,y,f(x,y))
Mg gives function f: f(x) = The minimal y such that g(x,y'), y' < y is defined and g(x,y) = 0
```

Note that Mg does not have to be determined and can lead to partial functions.

A program in µCurse is just the function definition written in a single line. For instance, a program that calculates the sum of two inputs is:

```RP0AS(P2), read: f(x,0) = P0(x) [ = x ], f(x,S(y)) = S(P2(x,y,f(x,y))) [ = f(x,y) + 1 ]
```

## Example Programs

### Sign Function

``` RCAS(C)
```

### Boolean NOT

``` RAS(C)C
```

### Boolean OR

``` ARCAS(C)(RP0AS(P2))
```

### Boolean AND

(via DeMorgan's Laws)

``` ARAS(C)C(AARCAS(C)(RP0AS(P2))(ARAS(C)C(P0)ARAS(C)C(P1)))
```

### Elaborate Identity Function

(Idea: x == y iff y is the smallest value s.t. x - y = 0 => f(x) = µy(x-y))

``` MRP0ARCP0(P2)
```

### Bijective Pair Function

f(x,y) = 2x * (2y+1)-1

``` ARP0ARCP0(P2)(ARCARP0AS(P2)(P0P2)(AARAS(C)ARCARP0AS(P2)(P0P2)(P0P2)(AS(AS(C))P0)(P0)ARP0AS(P2)(ARCARP0AS(P2)(P0P2)(AS(AS(C))P1)AS(C)))AS(C))
```

## Literate µCurse

In the dialect "Literate µCurse", one can write multiple function definitions (one per line) and use them for other definitions with the U prefix. The main function has to be called main. A function definition may only contain lower-case letters. For example, take the Boolean AND function from above:

``` sign=RCAS(C)
plus=RP0AS(P2)
not=RAS(C)C
or=AUsign(Uplus)
and=AUnot(AUor(AUnot(P0)AUnot(P1)))
main=Uand
```

Since it is forbidden to create cycles with this definiton, it amounts to not much more than string replacement.

## Symbolic Syntax

By replacing the function letters with symbols and erasing the syntactically unnecessary open parenthesis, a more brainfuck-esque program look can be achieved.

```S -> +
C -> 0
Pi -> !<i times _>
Ag(h1..hi) -> [gh1..hi]
R -> @
M -> µ
```

### Example

``` ARAS(C)C(AARCAS(C)(RP0AS(P2))(ARAS(C)C(P0)ARAS(C)C(P1)))
=>
[@[+0]0[[@0[+0]@![+!__]][@[+0]0!][@[+0]0!_]]]
```

for the Boolean AND described above

## Trivia

According to the Kleene normal form theorem, every recursive function f can be expressed as

``` f(x) = UµyTexy
```

for fixed, primitive recursive predicates U and T. A consequence is that every µCurse program can be written with at most one M.