New answers tagged

0

You could do it by making the second parameter of your function function like the index of the summation, and recursively increment this parameter as long as $0 \leq i < n$. $$f(n, i) = \begin{cases} 1 & \text{if } n =0\\ f(i, 0)\cdot f(n-i-1,0) + f(n, i+1) & \text{if } 0 \leq i < n\\ 0 & \text{otherwise}\\ \end{cases}$$ Then $...


4

Once you have proved that $|x-2^y|=0$ is a decidable predicate, the function $$\log_2(x) \equiv \mu y(|x-2^y| = 0)$$ should match the description of the function given and proves that it is recursive. Edit: To show that $|x-2^y|=0$ is decidable, show that $\overline{\text{sg}}(|x-2^y|)$ is recursive, which requires you to show that $|x-z|$, $2^y$, and $1 - \...


3

You are unsure how to answer the question. When you are unsure: I method that does usually not work is trying to think about the problem very hard and waiting for inspiration. It doesn't come. A method that works quite well is using pen and paper and trying it out. And you'll find that f (2, 64) calls f (64, 1) which doesn't make any further calls. Now ...


1

Without going into the details, you are looking for something that's known as a Gray code. Any cyclic Gray code that has the all zero bitstring at the opposite part of the cycle as the all one bitstring gives a minimal expected solution time assuming an uniform random input.


2

Here is a general algorithm. The maximum number of flips needed is $2^{n-1}-1$. Input: coin 0, coin 1, coin 2, ..., coin $n-1$ Procedure: $\quad$ If all coins face the same side, return. $\quad$ For $i$ from 1 to $2^{n-1}-1$ inclusive: $\quad\quad$ If $i$ is divisible by $2^k$ but not $2^{k+1}$: $\quad\quad\quad$ Flip coin $k$ $\quad\quad\quad$ If ...


Top 50 recent answers are included