# Tagged Questions

79 views

### Fixed point combinator and functions with no fixed point

In lambda calculus the fixed point combinator is defined as: It is very easy to see how $Yg =g(Yg)$ for any $g$ by using $\beta$-reduction. At the same time I wonder what is the meaning of ...
59 views

### Formulating a recursive definition

Let Σ(k) = 1 + 3 + 5 + ... + (2k+1) be the sum of all odd natural numbers from 1 up to and including (2k+1). Formulate a recursive definition for Σ including both the base case Σ(0) = 1 and a (k+1)th ...
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. ...
34 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 ...
143 views

### Precisely, what is a primitive recursive definition?

If I understand correctly, the language of primitive recursive arithmetic has a distinguished function symbol $S$, together with a function symbol for each primitive recursive definition (hereafter ...
89 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 ...
25 views

### proof using a recursive definition

I am doing a 2-part question. Thus far, I have finished the first part, requiring me to make a recursive definition of a set "S" of all binary strings, starting with a 1. I have: Base: 1 Recursion: ...
30 views

### Recursively defined sequences

So, this question has been giving me a little bit of trouble. It's supposed to be just a few lines, and I know that I don't need to write out the base case, recursive step, and restriction. I ...
43 views

### Discrete Math Recursive Functions for Strings

Recursive Functions for Strings Construct a recursive definition for the following string function over the alphabet {x,y}: f(x) returns the string where every x is replaced by xy and every y is ...
70 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 ...
31 views

### Defining substitution by structural recursion

For a term u, let $u{x\atop t}$ be the expression obtained from $u$ by replacing the variable $x$ by the term $t$. Define $u{x\atop t}$ by recursion on $u$. Not really sure how to start this one. ...
70 views

### Primitive Recursion Functions (Programs)

The set $F_{n}$ of primitive recursive function symbols of arty $n$ can be defined inductively as \begin{array}[lr] & Z, \text{Succ} \in F_{1} & \\ \pi_{j}^{n} \in F_{n} \quad \text{for each} ...
65 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 ...
71 views

### Recursion, multiplication and exponential

The set $F_{n}$ of primitive recursive function symbols of arty $n$ can be defined inductively as \begin{array}[lr] & Z, \text{Succ} \in F_{1} & \\ \pi_{j}^{n} \in F_{n} \quad \text{for each} ...
182 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?
104 views

### undecidability of the structure $(\omega,+,2^n)$

Is the structure $(\omega,+,2^n)$ undecidable? There is no easy way to define multiplication using a formula.
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 ...
376 views

### Primitive recursive functions and characteristic functions. Methods of proof- examples. Illumination.

I am puzzling over a sentence in an example in a textbook, showing that a function $f$, defined by cases, is primitive recursive. Let $E$ be the set of even natural numbers. The function $f$ defined ...