Questions tagged [mu-recursion]

The tag has no usage guidance.

11 questions
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,...]$...
• 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 ...
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 ...
• 239
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 ...
0 votes
1 answer
118 views

• 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 ...
• 1,519