Problem Detail: A lot of “famous” undecidable problems are nonetheless at least semidecidable, with their complement being undecidable. One example above all can be the halting problem and its complement. However, can anybody give me an example in which both a Read More …
Category: Uncategorized
[Solved]: Is the language $L = {a^nb^m : n = 2^m}$ context-free?
Problem Detail: Is the language $L = {a^nb^m : n = 2^m}$ context-free? Assume L is a context-free language. Then $ exists pin mathbb{Z}^{+}:forall sin Lleft | s right |geq p. s = uvxyz,left | vy right |geq 1,left | vxy Read More …
[Solved]: Could two decidable languages ever not have a mapping reduction?
Problem Detail: Is it ever the case that two decidable languages $L_1$ and $L_2$ that cannot be reduced to one another (in either or both directions)? Intuitively, I would not expect there to be, but rigorously, are there extreme examples that Read More …
[Solved]: Discrepancy between heads and tails
Problem Detail: Consider a sequence of $n$ flips of an unbiased coin. Let $H_i$ denote the absolute value of the excess of the number of heads over tails seen in the first $i$ flips. Define $H=text{max}_i H_i$. Show that $E[H_i]=Theta ( Read More …
[Solved]: How come {ww} isn’t regular when {uv | |u|=|v|} is?
Problem Detail: As we know, using the pumping lemma, we can easily prove the language $L = { w w mid w in {a,b}^* }$ is not a regular language. However, the language $L_1 = { w_1 w_2 mid |w_1| = Read More …
[Solved]: What is the Big O of T(n)?
Problem Detail: I have a homework that I should find the formula and the order of $T(n)$ given by $$T(1) = 1 qquadqquad T(n) = frac{T(n-1)}{T(n-1) + 1},. $$ I’ve established that $T(n) = frac{1}{n}$ but now I am a little Read More …
[Solved]: Collectively pay the bill problem
Problem Detail: There are $n$ people at a table. The $i$th person has to pay $p_i$ dollars. Some people don’t have the right bills to pay exactly $p_i$, so they come up with the following algorithm. First, everyone puts some of Read More …
[Solved]: Compute square root using (bit) additions and shifts as primitives
Problem Detail: Question: Given an $n$-bit natural number $N$, how to compute $lceil sqrt{N} rceil$ using only $O(n)$ (bit) additions and shifts? The tip is to use binary search. However, I could not achieve the required complexity (I got $O(n^2)$). Read More …
[Solved]: PDA recognising all strings with a $1$ in the second half
Problem Detail: My professor gave us an old exam to look over for our final exam and I am having a hard time understanding the push down automata problem he gave. In the problem it says: Let $Sigma = {0,1}$ and Read More …
[Solved]: What is a “contradiction” in constructive logic?
Problem Detail: In Practical Foundations for Programming Languages, Robert Harper says If for a proposition to be true means to have a proof of it, what does it mean for a proposition to be false? It means that we have a Read More …
