Questions tagged [mu-recursion]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
2 answers
108 views

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
189 views

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
165 views

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
298 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 ...
mouton5000's user avatar
0 votes
1 answer
118 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} \...
Karo's user avatar
  • 478
0 votes
1 answer
82 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 ...
David Hamide's user avatar
3 votes
3 answers
886 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 ...
Tim's user avatar
  • 4,865
3 votes
0 answers
85 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 ...
Manlio's user avatar
  • 369
3 votes
1 answer
316 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{...
lo tolmencre's user avatar
3 votes
2 answers
240 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,...
Corristo's user avatar
  • 151
2 votes
3 answers
455 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 ...
M a m a D's user avatar
  • 1,519