0
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
4answers
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: ...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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$ ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
-1
votes
1answer
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 ...
4
votes
4answers
303 views

Examples of partial functions outside recursive function theory?

My math background is very narrow. I've mostly read logic, recursive function theory, and set theory. In recursive function theory one studies partial functions on the set of natural numbers. Are ...
3
votes
3answers
420 views

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 ...