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 …
Author: ignougroup
[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]: What is semantic closure?
Problem Detail: In the context of database theory, what does semantic closure mean (linguistically speaking, i.e. not the mathematical definition) If X is the set of attributes of $F$, then the semantic closure $F^+$ of $F$ is defined as follows: $F^+={$ Read More …
[Solved]: Standard notation for the language of the universal Turing machine?
Problem Detail: The universal Turing machine $U_{TM}$ is a TM that takes in as input an encoding of a TM and a string, then runs the TM on the string and does whatever the simulated TM does. The language of the Read More …
[Solved]: Why is a program with only atomics in SC-DRF but not in HRF-direct?
Problem Detail: In the paper “Heterogeneous-Race-Free Memory Models” [1], the authors state that a program consisting only of atomic is race free in SC-DRF but it is not in HRF-direct. I am not able to understand why this is. Can anyone 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 …
