0
votes
1answer
17 views

What's time complexity of algorithm for “Word Break”?

Word Break(Dynamic Programming) Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible ...
2
votes
1answer
33 views

Primitive-recursive functions and polynomial equations

I am looking for examples of primitive-recursive functions $f:\mathbb{N}\rightarrow\mathbb{N}$ that can not be written as a pair of polynomials, i.e. $$f(n) = m \Leftrightarrow P(n,m) = Q(n,m)$$ ...
1
vote
0answers
47 views

“Building blocks” for computable functions

In an (otherwise very enlightening) answer to another question of mine the question came up What functions are allowed as building blocks for computable functions? I was astonished that there ...
0
votes
1answer
99 views

Show that $gcd(x,y)$ and $z = lcm(x,y)$ is primitive recursive

For the $gcd(x,y)$ we note: $gcd(x,0) = x$ $gcd(x,succ(y)) = gcd(succ(y),mod(x,succ(y)))$ $succ(x)$ and $mod(x,y)$ are both primitive recursive, so $gcd(x,y)$ must be as well. $z = lcm(x,y)$ if ...
0
votes
2answers
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 ...
2
votes
1answer
98 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
56 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
164 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
76 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!!!
4
votes
1answer
68 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
285 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
374 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
101 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.