# μCurse

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

## Contents

## 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(x
_{1},...,x_{n}) = x_{i}) - 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) = 2^{x} * (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.

## External resources

- A reference implementation of the interpreter, written in Haskell.