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

61 views

29 views

### recursion and inductive proof

Just so no one thinks I am trying to get one over on anyone, this is a homework question. I have solved all the other problems, but I don't know where to begin with this one. I am not asking for an ...
30 views

32 views

40 views

### A question about many-one reducibility of two sets

We want to show that $\big\{x:W_{x}$ is finite }$=Fin \leq _m Cof=\big\{x : W_{x}$ is cofinite}. But I really have not any idea. Would be grateful for your help.
40 views

### I need a common term for a recursive sequence

Some days ago, I made a question here about a common term for recursive sequence. I gained very good solutions. Thanks again. Today, I was thinking of a general case which is given below. Assume $p$ ...
282 views

159 views

### A new type of Arithmetic-Harmonic mean for $n$ numbers

Let's introduce the following iterative procedure. Take two numbers $x_0$ and $y_0$. $$a_0=\frac{x_0+y_0}{2}~~~~~~~~~~~b_0=\frac{2x_0y_0}{x_0+y_0}$$ x_1=\frac{x_0+a_0+b_0}{3}~~~~~~~~~~~y_1=\frac{...
19 views

### the set of extendable p.c. functions is not N

Show that the set $Ext:= \big\{x\in N : \varphi_{x}$ is extendable to a total recursive function $\big\}$ is not equal to the set of non negative integers $N$. Would be grateful for your help.
23 views

### Modeling the maximum number of moves in Tower of Hanoi problem

What would be the recursive algorithm for solving the Tower of Hanoi problem (with n disks and 3 pegs) in maximal number of moves (i.e. going through all possible disks/pegs combinations).
38 views

36 views

### A Question about Computable Functions

Barry Copper states following in his Computability theory book which I have a question about them. Exe.4.5.1: Show that if $\varphi_e(x) \downarrow$ is a computable relation, then so is ...
141 views

### Proof of x-intersection of the Mandelbrot Set?

I'm trying to prove that the Mandelbrot set intersects the X-axis on the interval [-2,.25]. I understand and have proven that the Mandelbrot set lies in a radius of 2. Mostly, I'm wondering how to ...
77 views

### factoring cubic polynomial equation using Cramer's rule.

1) I have question about factoring cubic polynomials. In my note it says "Any polynomial equation with positive powers whose coefficients add to 0 will have a root of 1. Another, if sum of the ...
23 views

### How to solve a nonlinear recursion relation?

Given the following recursion relation $$E^{(n)}=(E^{(n-1)}-\alpha_1)\,e^{-\alpha_2\,(\alpha_3E^{(n-1)}+b)}$$ where $\alpha_i$'s and $b$ are some constants. I am trying ...
37 views

### Recurrence to find P(n). P(n) is the number of ways to decorate a strip of size n with tiles.

There are three kind of tile. One is of size 1. Second is of size 2 of green color. Third is of size 2 with blue color. These are the values I found but I can not figure out the formula. P1 1 p2 3 p3 ...
There is a theorem in computability theory which states: B.Cooper: If $A\subseteq N$ is computable, then $A$ is also computably enumerable. In the proof of this theorem -which is an ...