1
$\begingroup$

Problem

I've got this function:

$f(x,y)=(6-3\cdot x)\cdot(y+2)$, with $(x,y)\in\mathbb{N}^2$

Now I have to find $g=\mu f$.

Proposed solution

My solution was to find the smallest $n\in\mathbb{N}$ to find $f(n,y)=0$ and show that $\forall 0\leq m\leq n : f(m,y)$ is defined:

$f(0,y)=(6-0)(y+2) = 6y+12$, defined $\forall y\in\mathbb{N}$

$f(1,y)=(6-3)(y+2) = 3y+6$, defined $\forall y\in\mathbb{N}$

$f(2,y)=(6-6)(y+2) = 0$, defined $\forall y\in\mathbb{N}$

So I've found $g=\mu f=2$.

Questions

  • Is above solution correct?
  • Is it always the first parameter that becomes $n$?
  • If $f(x,y)=(6-3\cdot x)\cdot(y-2)$ and $f(0,y) = (6-0)(y-2) = 6y-12$, wouldn't be $f(0,y)=0$, if $y=2$ and therefore my $n=0$ for this $y$, but for other $y$, my $n$ would be different?
$\endgroup$
  • $\begingroup$ Please restrain your self to one question per post; in particular, the last bullet is independent of the others. You may want to check out other questions about mu-calculus. Regarding "real world examples", not that mu-calculus is Turing complete so every computer programis a real world example, even if they are written in a weird way. $\endgroup$ – Raphael Jul 20 '14 at 13:51
  • $\begingroup$ @Raphael I moved the last bullet to a new question. If you can answer any of these questions (here or in the other thread) please don't hesitate to explain :) $\endgroup$ – polym Jul 20 '14 at 14:15
  • 1
    $\begingroup$ Could you clarify what you mean by "$\mu$-calculus"? The $\mu$-calculus I'm familiar with is an extension of modal propositional logic with least and greatest fixed-point operators but you seem to be talking about something else. $\endgroup$ – David Richerby Jul 20 '14 at 14:22
  • $\begingroup$ @DavidRicherby I am talking about mu recursive functions. Might be that the tag is wrong. Is it? The mu operator is defined here for example. $\endgroup$ – polym Jul 20 '14 at 14:31
  • $\begingroup$ @polym: That's how we have been using the tag. Not everyone encounters "classic" recursion theory these days, though, especially outside of Europe (?). $\endgroup$ – Raphael Jul 20 '14 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.