# Tagged Questions

56 views

### Function Combination on Computer Science

I read some material on Computational Function, every one could describe the result of following combination? suppose $g_1(x)=3x$, $g_2(x)=4x$, $f(x,y)=x+y$, how we compute combination of $f$ with ...
104 views

### $\textbf{Q}$ fails to prove some correct $\forall$-rudimentary sentence

Show that the existence of a semirecursive set that is not recursive implies that any consistent, axiomatizable extension of Q fails to prove some correct $\forall$-rudimentary sentence. I ...
75 views

### Examples of partial functions in which the domain is not known?

I was reading this, it mentions about a kind of function in which the exact domain is not known. The only example given is this one - and I'm not really sure I understood it. I got curious about it: ...
107 views

### Prove that div(x,y) is primitive recursive (integer division

Prove that div(x,y) is primitive recursive (integer division). I tried thinking about it, I just don't know how to write it formally. it is kinda obvious that I should subtract y from x several times ...
55 views

### Structure of partial recursive function over recursively enumerable guard

I read that the function $$f(n) = \left\{ \begin{array}{l l} g(n) & \quad \text{if n \in A}\\ \text{undefined} & \quad \text{otherwise} \end{array} \right.$$ is recursive if ...
50 views

### Prove that [x/y] is a primitive recursive function

Prove that [x/y] is a primitive recursive function using this theorem: If $g(x_1,...,x_n)$ is primitive recursive, then $f(x_1,...,x_n)=\sum^{x_n}_{i=0}g(x_1,...,x_{n-1},i)$ is also a primitive ...
80 views

### computability and uncomputability

1) Suppose $f$ is an increasing function from $\mathbb N \to \mathbb N$ $(i.e., if x\ge y, then \space f(x) \ge f(y)).$ Is there necessarily a program which computes $f$? 2) Suppose $f$ is a ...
34 views

### Expressing total functions in a single equation

Suppose $f(x),g(x)$ are total functions. Give a single equation $h$ in terms of $f$ and $g$ using $+,.,$ truncated substitution and the functions $sg$, $\bar{sg}$ $h(x)= x$ if $f(x)=0$ and $g(x)=0$ ...
101 views

### Recursively enumerable properties

In my textbook are three interesting properties listed (which I would like to prove) (1) A is recursively enumerable iff A is the domain of a partial computable function (2) A is recursievly ...
178 views

### Representing Recursion and Primitive Recursion diagrammatically

I'm interested in how Recursion, and Primitive Recursion, could be represented diagrammatically. It occurred to me that this would be a good way of seeing the difference. Also, I'm interested in how ...
56 views

### Proof that an inverse of a possibly noncomputable function is possibly not decidable

I'm stuck with the following homework: Given an fixed function $f:\mathbb{N}\to\mathbb{N}$. $f$ is an arbitrary (possibly not computable, possibly partial) function. Show that the set $\{f(42)\}$ is ...
173 views

### How to show if a function is partial recursive?

I have seen and understood the most definitions but i just could not understand how to show if a function is mu-partial recursive or not. I used search engines, but all I find are just more lectures ...
### Growth rate of primitive and $\mu$-recursive functions
Functions that are not primitive recursive but $\mu$-recursive are said to grow too fast to be primitive recursive. Are there functions $f$ and $F$ such that a function is primitive recursive ...