# Tagged Questions

140 views

### range of one increasing computation function?

We know that that the range of any recursive partial function is recursively enumerable. Also we know the fact: Set A is recursive if and only if it is range of some increasing section partial ...
40 views

### Problems On Many-one Reducible [closed]

In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. ...
32 views

### Meaning of Biinterpretability.

I'm reading this paper: http://www.math.cornell.edu/~shore/papers/pdf/hyp9.pdf and I am struggling with the meaning of Biintereptability, to quote the paper A degree structure $D$ is ...
28 views

### Diagonalization out of partial recursive functions

So generally partial recursive functions don't diagonalize. But isn't this function an exception? $\phi(x)=\lambda_{x}(x)+1$ if $\lambda_{x}(x)$ halts and $0$ else. Completely no clue... It seems ...
22 views

### Show $f(x)$ is partial recursive using the

So I want to show that the function $f(x)=0$ if $x$ is even and not defined otherwise, is partial recursive using the $\mu$ operator (bounded search function, which is partial recursive). Plan is to ...
27 views

### Prove uniqueness of recursive function

I am currently reading Cutland's Computability and would like to figure out how to solve Theorem 4.2 which states: Let $x=(x_1 \dotsc x_n)$, and suppose that $f(x)$ and $g(x,y,z)$ are functions; ...
83 views

### Ackermann function is not primitive recursive

The function of the Ackermann function is defined as $$A_{0}(y)= y+1$$ $$A_{x+1}(0)= A_{x}(1)$$ $$A_{x+1}(y +1)= A_{x}(A_{x+1}(y))$$ I want to show that the function of ackermann is primitive ...
35 views

### Figuring out the steps in a Recursive Function

I have the following recursive function: $f(0) = 7$ $f(n+1) = f(n) + 6n + 1$ for all integers $n => 0$ I know the answer is $f(n) = 3n^2 + 2n + 7$ I would like to know the steps to get to this ...
55 views

### Understanding second axiom of Primitive recursion

I read about Primitive recursion and was able to understand most of it. However I am finding it very difficult to understand the second axiom of primitive recursion. I can make out that it helps in ...
35 views

### Function composition in computability

I have been reading Cutland's computability book, which is really good! However, I have found myself thinking way too much about one little passage in the the third section of the second chapter (the ...
47 views

### A multivariate function, computable for any fixed first argument, is computable

Claim: If $f:\mathbb N^{k+1}\to\mathbb N$ is a function such that for all $x_0\in\mathbb N$, $\lambda x_1,\dots,x_k.f(x_0,x_1,\dots x_k)$ is a partial recursive function then $f$ is also partial ...
68 views

### Can we find a formula defining a recursively enumerable set?

By Post's Theorem we know that a set $A\subseteq\mathbf{N}$ is recursively enumerable iff it is definable by a $\Sigma_1$-formula, i.e. there exists a $\Sigma_1$-formula $\varphi(x)$ with $x$ free ...
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 ...
61 views

### A setting in which Rice's theorem is not true

In my class we call a set of computable functions $A$ recursive if its indexing set $I_A=\{e\in\mathbb N:\phi_e\in A \}$ is recursive, where $\phi$ is some known GĂ¶del numbering of the computable ...
94 views

### An effective enumeration of recursive sets in increasing order

Definition: We call a set recursive if its characteristic function is recursive. Claim: If the set $A\subset\mathbb N$ is recursive then $A=Range(f)$ for some recursive and increasing function. ...
151 views

### All infinite recursive sets can be enumerated by an injective function

Definition: We call a set recursive if its characteristic function is recursive. Claim: If the recursive set $A\subset\mathbb N$ is infinite then $A=Range(f)$ for some primitive recursive injective ...
64 views

### Induction on Primitive Recursive Function

The set $F_{n}$ of primitive recursive function symbols of arity $n$ can be defined inductively as: \begin{align} & Z, \text{Succ} \in F_{1} & \\ &\pi_{j}^{n} \in F_{n} \quad \text{for ...
40 views

### Two indexes $c$ and $b$, such that $Dom(\varphi_a)=\{b\}$ and $Dom(\varphi_b)=\{c\}$

Problem: Assume $\{\varphi_i\}_{i=1}^\infty$ is an effective enumeration of the computable functions. Find two indexes $c$ and $b$, such that $Dom(\varphi_c)=\{b\}$ and $Dom(\varphi_b)=\{c\}$. ...
63 views

### Concatenation, reversal and sum are primitive recursive

Let $\mathbb N^*$ be the language of finite words with alphabet $\mathbb N$. Assume $k:\mathbb N^*\to\mathbb N$ is an effective coding. That is $k$ is a bijection whose length and member functions are ...
86 views

### An effective coding of $\mathbb N^*$

Problem: Assume $\Pi:\mathbb N^2\to\mathbb N\setminus\{0\}$ is a primitive recursive coding of the pairs of numbers, that is also a bijection and $(\forall (x,y)\in\mathbb N^2)(\Pi(x,y)>max(x,y))$. ...
80 views

### Is definition by cases a primitive recursive function?

Primitive recursive functions can simulate every single step of a Turing machine. In order to prove this, one has to see that a function defined by state table is primitive recursive. Simply ...
51 views

### Course-by-values recursion

I have many questions in my textbook of the kind: Assume $g$ is primitive recursive and assume $f(0)=c_0,\dots,f(n-1)=c_{n-1}$ $f(x+n)=g(<f(x),\dots,f(x+n-1)>)$ Prove that $f$ is primitive ...
48 views

128 views

### Termination of a Fast Exponentiation problem

Here's the problem I am stuck on. There exists a fast exponentiation program like the following: Given inputs a in the set of all Real numbers, b in the set of Natural numbers, initialize ...
62 views

### Ackermann function and primitive recursiveness

If we define $b_n(m) := a(n,m)$ for all $n$ and $m \in \mathbb{N}$. For which $n$ is the function $b_n$ primitive recursive and for which $n$ it is not a primitive recursive function? Can anyone ...
57 views

### Prove $g$ is PR. $g(n) = f(n) \text{ if n} \notin A$. $f$ is PR. $g$ is total. $A$ is a finite set.

Show that if f:N $\rightarrow$ N is primitive recursive, A $\subseteq$ N is a finite set, and g is a total function agreeing with f at every point not in A, then g is primitive recursive. My ...
177 views

### Simultaneous recursion

I have no idea how to even start proving the following theorem: If $f_0, f_1: \mathbb{N}^r \rightarrow \mathbb{N}$ and $g_0, g_1: \mathbb{N}^{r+3} \rightarrow \mathbb{N}$ are primitive recursive, ...
63 views

### Acceptable numbering of partial computable functions required to be one variable?

Soare in a yet unpublished textbook (I happened to be in a class taught by one of his former graduate students where we were field-testing a rough draft of his new textbook) Computability Theory and ...
78 views

### Prove that $\{(x,y): W_x\text{ and }W_y\text{ are recursively separable}\}$ is $\Sigma_3$-complete

Prove that $\{(x,y): W_x\text{ and }W_y\text{ are recursively separable}\}$ is $\Sigma_3$-complete This is a question from Soare's Recursively Enumerable Sets and Degrees. I have little idea how ...
137 views

### How do we know that every halting Turing Machine can be expressed as a recursive function?

I've hear many times that a major result in Recursion Theory is the equivalence of Turing and Godel's models: the functions implementable on a Turing machine are precisely the functions that can be ...
180 views

### Primitive recursive function which isn't $\Delta_0$

What is the simplest/cutest example (and/or example with the most student-friendly proof that it is an example) of a primitive recursive function which isn't representable by a $\Delta_0$ wff?
120 views

### completeness and creative

I'm trying to show that any complete $\Sigma_1^0$ set is creative. The definition of creative I understand is: if there is a total recurvise function f s.t. f(e) is an element of A iff f(e) is an ...
95 views

### Are the brackets in formal box notation of recursive functions omittable?

So we know all recursive functions can be expressed as a finite sequence of symbols for the basic functions and processes composition, primitive recursion, and minimization. What I'm wondering is if ...
What is the recursive relation for $$H(m)=2^{(m^2)}$$ using successor function recursive relation for multiplication: $$mult(x,0)=0; mult(x,S(y))=add(x,mult(x,y))$$ recursive relation for addition: ...