Tagged Questions
2
votes
1answer
73 views
Application Church-Turing thesis
I would like to give examples of problems which are solvable with an algorithm, for example the function $f$ which maps the tuple $(n,m)$ to the greatest common divisor. This map is recursive. I would ...
0
votes
1answer
36 views
Identifying a pattern in an array
Is there a way to identifying a pattern and/or recursive function for an array?
If yes, how can I do this. Could anyone please help me with some information and/or resource for this?
Any help is ...
1
vote
2answers
82 views
Recursive relation using successor function
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: ...
1
vote
1answer
50 views
Recursive functions, successor function
How to show that the power function $\displaystyle A=2^{m^2}$ is primitive recursive based on successor function?
Thanks much in advance!!!
0
votes
0answers
85 views
Master Theorem $T(n)=4T(n/8)+n^(3/8)$
My try was :
$$f(n)= n^3/5=n^{0.6} g(n) = n^{\log_8}(4) =n^{0.667}$$ so $f(n)<g(n)$
So $f(n) = \Omega(n^{\log_8}(n) + \epsilon)$ but with regularity condition
$4f(n/8) \le cn^{3/5}$ ,for $c$ ...
3
votes
1answer
41 views
Is every context free language equivalent to one whose grammar has only one non-terminal symbol?
A context free language is generated by a context free grammar, which can be expressed in the Backus-Naur form e.g. I believe that if we only allow one nonterminal symbol in the grammar, the resulting ...
2
votes
2answers
104 views
How to define divisibility recursively?
Let $d(x,y)=1$ if $x$ is divisible by $y$, and $=0$ otherwise.
How can I define $d(x,y)$ in terms of just the basic primitive recursive functions (zero, successor, identity, projection) and the ...
2
votes
1answer
260 views
Finding General Expression from recursion
I am trying to find a general expression from a recursion.
Here it goes:
$(x+i)P_i = (i+1)P_{i+1} + \frac{x}{2} P_{i-1}$
$i$ goes from $0$ to $S$.
How can I calculate a generic $P_i$ in terms of ...
3
votes
0answers
98 views
Recursion closed form [closed]
Is there a theorem stating that all recursive problems cannot have a closed form? Or the other way around, stating that all recursive problems can have a closed form.
