# Tagged Questions

19 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 ...
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)$$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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: ...
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!!!
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 ...
286 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 ...
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 ...