Μ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 definition, 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 -> !
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.
Category:Languages
Category:2014
Category:Turing complete
Category:Turing tarpits