Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [mu-recursion]

The tag has no usage guidance.

0
votes
0answers
27 views

Witnessing for partial recursive functions

For all $f\colon \mathbb{N}^2 \rightarrow \mathbb{N}$ partial recursive there exists partial recursive $g\colon \mathbb{N} \rightarrow \mathbb{N}$ such that a) $x \in \operatorname{Dom}(g) \...
4
votes
2answers
62 views

Can Turing machines simulate the unbounded minization operator applied to a partial function?

I am a little bit confused with the unbounded minimization ($\mu$ operator of the $\mu$ recursive functions). The $\mu$ operator is $\mu(f)(x) = \min(n | f(x, n) > 0)$ and the operator is said ...
0
votes
1answer
40 views

prove that $h(x)$ is partial recursive

If $f:A^*\rightarrow A*$ and $g:A^* \rightarrow A^*$ are partial recursive we want to prove $h:A^* \rightarrow A^*$ with the following definition is partial recursive $$ h(x) = \begin{cases} \...
0
votes
1answer
59 views

Does it matter for this function if the set we check membership of is finite?

I have the following problem. Let $\Phi$ be an admissible numbering of the single-parameter partially-recursive functions. That is, $\Phi(i, x) = f_i(x)$ with $f_i$ the $i$th partially-recusive ...
3
votes
3answers
315 views

Are partial recursive functions analogous to recursive languages or r.e. languages?

From Ullman and Hopcroft's Introduction to Automata Theory, Language, and Computation 1ed 1979: The assumption that the intuitive notion of "computable function" can be identified with the class ...
3
votes
0answers
64 views

Prove that variable projection is recursive

Let $\varphi:\mathbb{N}\to\mathbb{N}^*$ be an arbitrary recursive enumeration of finite strings and $\mathcal{I}^n_i(x_1,...,x_n) = x_i $ be the $i$-th projection over $n$ variables. I would like to ...
3
votes
1answer
158 views

What does the exact $\mu$-recursive program for minimization look like?

The minimization of a given primitive recursive function $f$ is computed by the following expression: $ \newcommand{\pr}[2]{\text{pr}^{#1}_{#2}} \newcommand{\gpr}{\text{Pr}} \newcommand{\sig}{\text{...
3
votes
2answers
118 views

Undefined behaviour when composing primitive-recursive with $\mu$-recursive functions?

It is quite easy to show that the following two functions are primitive recursive and thus also $\mu$-recursive: $$ifthen(n,a,b) = \begin{cases}a & n > 0 \\ b & else\end{cases} $$ $$ eq(x,...
3
votes
3answers
322 views

Does the normal form theorem imply that every partially computabe function is primitive recursive?

This is Normal Form Theorem (Second Edition of Computability, Complexity, and Languages written by Martin Davis page 75): Let $f(x_1,...,x_n)$ be a partially computable function. Then there is a ...