# Tagged Questions

Recursion is the process of repeating items in a self-similar way. A recursive definition (or inductive definition) in mathematical logic and computer science is used to define an object in terms of itself. A recursive definition of a function defines values of the functions for some inputs in ...

45 views

108 views

### Free Gliders for Everyone?

According to Feynman's Lecture on Computation (Problem 5.1, p. 148 ) you can extract $E=kTN\log 2$ out of two copies of a random $N$ bit random tape. From this we can conclude that it takes the same ...
30 views

29 views

### Order of growth of sequence $f_{n} = 2f_{n-1} + f_{n-2}$

I'm currently stuck with the following problem. How do I calculate the order of growth of the following sequence: $f_{n} = 2f_{n-1} + f_{n-2}$ Assuming that $f_{0} =1$ and $f_{1} = 1$ I've got ...
49 views

### The graph of Ackermman function is primitive recursive

For a relation $R ⊆ ℕ^n$, define the characteristic function $χ :ℕ^n → ℕ$ such that $χ(x_1, x_2,..., x_n)=1$, if $(x_1,...,x_n) ∈R, χ(x_1,...,x_n)=0$ otherwise. Say a relation is premitive ...
37 views

139 views

### How to define $f(x) = 2x$ as a recursive and lamba function?

How can I exhibit a recursive function and a $\lambda$-term simulating the function $f : \mathbb{N} \rightarrow \mathbb{N}$, such that $f(x) = 2x$? For $\lambda$ part, I thought to create a mult ...
23 views

97 views

### Perplexing integral

First and foremost, is it possible to get the integral you are trying to solve as the solution? I just got the same integral twice. I have also tried MATLAB but it gives the same result. Below is the ...
37 views

### A particular recursion

Given $s_0=2^r>0$ let $s_i=\frac{s_{i-1}}{2^{\log^c{r_{i-1}}}}$ where $c\geq1$ and $r_{i+1}=\log_2(s_{i+1})=r_i-(\log_2(r_{i}))^c\leq r_{i}$. What is the value of smallest $i$ at which $s_i<1$ ...
99 views

### Formula to calculate directly $1 + 2 \cdot 3 + 3 \cdot 4 \cdot 5 + 4 \cdot 5 \cdot 6 \cdot 7 + \dots + n \cdot (n+1) \cdot \dots \ (2n-1)$

Is it some formula to calculate $$1 + 2 \cdot 3 + 3 \cdot 4 \cdot 5 + 4 \cdot 5 \cdot 6 \cdot 7 + \dots + n \cdot (n+1) \cdot \dots \ (2n-1)$$ for a given $n$ without iteration? comes from : http:/...
72 views

### How do I find a recurrence relation?

Let n1, n2, . . . , n100 be a sequence of integers. Initially, n1 = 1, n2 = −1 and all the other numbers are 0. After every second, we replace the kth term of the sequence with the sum of the kth and (...
95 views

### Mathematically, how does one find the value of the Ackermann function in terms of n for a given m?

Looking at the Wikipedia page, there's the table of values for small function inputs. I understand how the values are calculated by looking at the table, and how it's easy to see that 5,13,29,61,125 ...
I found the other day that you could find some solutions to an equation in the form $$f[f(x)]=x$$As a matter of fact, I found some solutions to$$f[f(f(\cdots f(x)\cdots))]=x$$ The solution, if one ...