Questions tagged [mu-recursion]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
2 answers

Is the function that computes the minimum of a countable set computable?

Given $A$ a countable set of numbers and $\min$ the function returning the minimum of a set (if exists). Is $\min(A)$ computable? My first try is thinking $A$ as infinite list $A = [a_0, a_1, a_2,...]$...
Saber98's user avatar
  • 13
3 votes
2 answers

Intuition for Church-Turing thesis for Turing machines

I can very clearly see "why" mu-recursion is a universal model of computation, i.e. why the Church-Turing thesis -- that any physically computable algorithm can be executed with mu-recursion ...
Abhimanyu Pallavi Sudhir's user avatar
1 vote
0 answers

Predecessor function with recursive types

I am defining the type Nat of natural numbers a recursive sum type: $$ Nat = \mu X. Unit \oplus X$$ Now, I have defined zero ...
Noel Arteche's user avatar
4 votes
2 answers

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 ...
mouton5000's user avatar
0 votes
1 answer

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} \...
Karo's user avatar
  • 478
0 votes
1 answer

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 ...
David Hamide's user avatar
3 votes
3 answers

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 ...
Tim's user avatar
  • 4,865
3 votes
0 answers

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 ...
Manlio's user avatar
  • 369
3 votes
1 answer

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{...
lo tolmencre's user avatar
3 votes
2 answers

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,...
Corristo's user avatar
  • 151
2 votes
3 answers

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 ...
M a m a D's user avatar
  • 1,519