<p>If it is the μ-recursive functions you are interested in (and not the μ-calculus, which is a totally different thing as slimton pointed out) it makes the most sense if you start looking at the <em>primitive recursive functions</em> (PRFs). The set of PRFs is interesting in it self and it turns out that the μ-recursive functions can be introduced by an extension of it.</p>

<p>Here are some slides that seems to be a relatively gentle introduction:
<a href="http://homepage.cs.uri.edu/faculty/hamel/courses/2011/spring2011/csc544/lecture-notes/11-recursive-functions.pdf" rel="nofollow">Link</a></p>

CC BY-SA 4.0
2022-03-04T14:49:05.847Z
The link returns a 404
Despertar
CC BY-SA 3.0
2010-12-10T12:00:30.780Z
2011-05-18T18:08:25.967Z
2011-05-18T18:08:25.967Z
Tobias Raski
<p>The two topics are, as mentioned, quite different. The $\mu$-recursive functions occur in computability theory. The $\mu$-calculus is a logic. Here is a very simple (I hope) description, in keeping with your request. </p>

<p>Regarding $\mu$-recursion: you can ask, if we viewed Turing machines as defining mathematical functions, what kind of functions do you have? The machine has a value $x$ on its input tape and writes a value $f(x)$ on its output tape. A Turing machine is not guaranteed to terminate. What does this mean for the function represented? It means that Turing machines encode partial functions. Which class of partial functions? Do they have a nice inductive definition, built up from simpler functions and composition operations? The answer to both these questions is given by the class of $\mu$-recursive functions. I assume most computability textbooks will contain details. The book by Boolos Burgess and Jeffrey worked for me. </p>

<p>Now for the $\mu$-calculus. Think of the behaviour of a discrete dynamic system like a program or any computing device. The device has a state consisting of the current control location and the contents of various data storage mechanisms. The behaviour of the device is encoded by a transition relation between states. This is exactly the transition relation, if you have a finite automation. For more complex devices, it is the relation between two states when the device makes a step. Suppose you want to logically specify the behaviour of such a device. </p>

<p>One way to think of this is to label states. For example, if you have a pushdown automaton and are interested in states where a symbol $a$ is on top of the stack, you could label such states "$aTop$". Say you want to logically express the set of states from which you can reach a state with $a$ on top of the stack. Modal logic has an operator $\Diamond$, pronounced "next". The formula $\Diamond \theta$  is true in a state $s$ if $s$ has a successor satisfying $\theta$. 
The set of states that in up to $2$ steps lead to $a$ on top of the stack are 
$(aTop \vee \Diamond aTop \vee \Diamond \Diamond aTop)$. You can keep nesting formulae to express reaching a state with $a$ on top in $k$ steps. To capture all such states, one introduces recursion and writes: $\mu X. (aTop \vee \Diamond X)$. </p>

<p><em>A $\mu$-calculus</em> is a system of function symbols with fixed point operators. The most popular $\mu$-calculus is the modal $\mu$-calculus, an extension of modal logic with fixed point operators. The <a href="http://homepages.inf.ed.ac.uk/jcb/Research/bradfield-stirling-HPA-mu-intro.ps.gz" rel="nofollow">survey</a> by Bradfield and Stirling is a good introduction. </p>

CC BY-SA 3.0
2011-05-19T00:21:41.030Z
2011-05-19T00:21:41.030Z
Vijay D
<p>I saw in <a href="https://cstheory.stackexchange.com/questions/3650">this question</a> a reference to <a href="http://en.wikipedia.org/wiki/%CE%9C-recursive_function" rel="nofollow noreferrer">$\mu$-recursive functions</a> or <a href="http://en.wikipedia.org/wiki/Mu_calculus" rel="nofollow noreferrer">$\mu$-calculus</a> as some computation model equivalent to <a href="http://en.wikipedia.org/wiki/Turing_machine" rel="nofollow noreferrer">Turing machines</a> and <a href="http://en.wikipedia.org/wiki/Lambda_calculus" rel="nofollow noreferrer">$\lambda$-calculus</a>. I know about these two but never heard of $\mu$-calculus. Can you briefly describe it and compare it with the other models? Bonus points for link references and books for beginners. Thanks in advance.</p>

<p><strong>Edit:</strong> Ok, just for clarification i'm interested in both $\mu$-recursive functions and $\mu$-calculus.</p>

CC BY-SA 2.5
2010-12-09T14:01:32.780Z
See http://en.wikipedia.org/wiki/%CE%9C-recursive_function
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-09T14:46:12.123Z
For book references, see also the related question: http://cstheory.stackexchange.com/questions/3131/books-on-mu-calculus
Ohad Kammar
CC BY-SA 2.5
2010-12-09T15:16:49.123Z
You should not confuse $\mu$-recursive functions with the $\mu$-calculus. These are totally different things.
slimton
CC BY-SA 3.0
2017-01-15T17:39:54.467Z
There is a connection though in that the $\mu$ in both cases represents a minimal solution - the minimal zero of a function, or the least fixpoint of a set transformer, respectively.
Klaus Draeger
<computability><lo.logic><books><mu-calculus>
What are "$\mu$-recursive functions" and $\mu$-calculus?
Ither
# What are "$\mu$-recursive functions" and $\mu$-calculus?

(Asked by: username_0 on 2010-12-09)

I saw in [this question](https://cstheory.stackexchange.com/questions/3650) a reference to [$\mu$-recursive functions](http://en.wikipedia.org/wiki/%CE%9C-recursive_function) or [$\mu$-calculus](http://en.wikipedia.org/wiki/Mu_calculus) as some computation model equivalent to [Turing machines](http://en.wikipedia.org/wiki/Turing_machine) and [$\lambda$-calculus](http://en.wikipedia.org/wiki/Lambda_calculus). I know about these two but never heard of $\mu$-calculus. Can you briefly describe it and compare it with the other models? Bonus points for link references and books for beginners. Thanks in advance.

**Edit:** Ok, just for clarification i'm interested in both $\mu$-recursive functions and $\mu$-calculus.

**Tags:** computability, lo.logic, books, mu-calculus

> **Comments:**
> **username_1**: See http://en.wikipedia.org/wiki/%CE%9C-recursive_function  
> **username_2**: For book references, see also the related question: http://cstheory.stackexchange.com/questions/3131/books-on-mu-calculus  
> **username_3**: You should not confuse $\mu$-recursive functions with the $\mu$-calculus. These are totally different things.  
> **username_4**: There is a connection though in that the $\mu$ in both cases represents a minimal solution - the minimal zero of a function, or the least fixpoint of a set transformer, respectively.  

---

## 2 answers

### Answer by username_5 on 2010-12-10. Score: 4 | Accepted answer

If it is the μ-recursive functions you are interested in (and not the μ-calculus, which is a totally different thing as username_3 pointed out) it makes the most sense if you start looking at the *primitive recursive functions* (PRFs). The set of PRFs is interesting in it self and it turns out that the μ-recursive functions can be introduced by an extension of it.

Here are some slides that seems to be a relatively gentle introduction:
[Link](http://homepage.cs.uri.edu/faculty/hamel/courses/2011/spring2011/csc544/lecture-notes/11-recursive-functions.pdf)

> **Comments:**
> **username_6**: The link returns a 404  

---

### Answer by username_7 on 2011-05-19. Score: 3

The two topics are, as mentioned, quite different. The $\mu$-recursive functions occur in computability theory. The $\mu$-calculus is a logic. Here is a very simple (I hope) description, in keeping with your request.

Regarding $\mu$-recursion: you can ask, if we viewed Turing machines as defining mathematical functions, what kind of functions do you have? The machine has a value $x$ on its input tape and writes a value $f(x)$ on its output tape. A Turing machine is not guaranteed to terminate. What does this mean for the function represented? It means that Turing machines encode partial functions. Which class of partial functions? Do they have a nice inductive definition, built up from simpler functions and composition operations? The answer to both these questions is given by the class of $\mu$-recursive functions. I assume most computability textbooks will contain details. The book by Boolos Burgess and Jeffrey worked for me.

Now for the $\mu$-calculus. Think of the behaviour of a discrete dynamic system like a program or any computing device. The device has a state consisting of the current control location and the contents of various data storage mechanisms. The behaviour of the device is encoded by a transition relation between states. This is exactly the transition relation, if you have a finite automation. For more complex devices, it is the relation between two states when the device makes a step. Suppose you want to logically specify the behaviour of such a device.

One way to think of this is to label states. For example, if you have a pushdown automaton and are interested in states where a symbol $a$ is on top of the stack, you could label such states "$aTop$". Say you want to logically express the set of states from which you can reach a state with $a$ on top of the stack. Modal logic has an operator $\Diamond$, pronounced "next". The formula $\Diamond \theta$ is true in a state $s$ if $s$ has a successor satisfying $\theta$.
The set of states that in up to $2$ steps lead to $a$ on top of the stack are
$(aTop \vee \Diamond aTop \vee \Diamond \Diamond aTop)$. You can keep nesting formulae to express reaching a state with $a$ on top in $k$ steps. To capture all such states, one introduces recursion and writes: $\mu X. (aTop \vee \Diamond X)$.

*A $\mu$-calculus* is a system of function symbols with fixed point operators. The most popular $\mu$-calculus is the modal $\mu$-calculus, an extension of modal logic with fixed point operators. The [survey](http://homepages.inf.ed.ac.uk/jcb/Research/bradfield-stirling-HPA-mu-intro.ps.gz) by Bradfield and Stirling is a good introduction.


---

