# Tag Info

4

Yes, at our current state of knowledge it is certainly conceivable that P=NP is independent of any given axiomatic foundation for mathematics (such as Peano Arithmetic or ZFC). It might even be "independent of the axioms, but not provably so". In contrast to some other enigmatic sentences, knowing that P=NP is independent of the axioms would not in itself ...

3

Every model of a typed lambda calculus is a cartesian closed category. Every cartesian closed category can be expressed as a typed lambda calculus (with the objects as types and arrows as terms). Thus, typed lambda calculus and cartesian closed category are essentially the same concept.

3

HINT: I’m assuming that the problem is to create context-free grammars that generate these languages. You need basically the same idea for both, so I’ll just deal with the first one. The idea is to use a non-terminal symbol to pump out $a$’s on the left and $c$’s on the right, one at a time; a production like $S\to aSc$ does this. At some point you then let ...

2

$\Sigma=\{a,b\}$ For $w\in \Sigma^*$, define $v(w)=|w|_b - |w|_a$ (the number of $b$s minus the number of $a$s). What can you say about $v(L)$? -

2

Assuming we know that the standard (diagonal) halting problem $H$ (and thus its complement $\overline{H}$) is undecidable: Given the index $\langle M \rangle$, let $M^\prime$ be the machine which ignores its input and runs $M$ on input $\langle M \rangle$. Then $f$ given by $f(\langle M \rangle) = \langle M^\prime\rangle$ is computable, one-to-one, and ...

2

To prove that $$Y = \{w\mid \text{w=t_1\mathtt{\#}t_2\mathtt{\#}\cdots\mathtt{\#}t_k for k \ge 0, each t_i \in \mathtt{1}^*, and t_i \ne t_j whenever i \ne j}\}$$ for $\Sigma = \{\mathtt{1}, \mathtt{\#}\}$ there are two main approaches: Via intersection with regular language: As you have mentioned, if $Y$ is context free then intersection with a ...

2

The pumping lemma should work. Let $w = a^m \in L$ with $m$ greater than the pumping constant (this will happen when $m = 2^n+273$ for some $n$, so just choose large enough $n$). Then if $L$ were regular, there is some $k$ such that for all $c\in \mathbb{N}$, all of $a^{m+ck} \in L$. Now show that for any $k>0$ and $m$, not all numbers of the form ...

2

Just notice that if $$c_i \le \frac{f_i}{g_i} \le C_i$$ then ($n=2$ is the number of functions you are considering) $$\frac{\max f_i}{\max g_j} \le \frac{\sum f_i}{\max g_j} = \sum_i \frac{f_i}{\max_j g_j} \le \sum \frac {f_i}{g_i}\le \sum C_i$$ and $$\frac{\sum f_i}{\max g_j} = \sum_i \frac{f_i}{\max_j g_j} = \sum_i \min_j \frac{f_i}{g_j} \ge ... 2 No, you cannot, at least under the definition of big-\Omega used in computer science. For example: f(n) = n^2 if n is of the form \displaystyle 2^{4^k} and f(n) = f(n-1) otherwise; g(n) = n. Then f(n) is as large as n^2 infinitely often, so f(n) is not O(g(n)). Also, f(n) is smaller than 2\sqrt{n} infinitely often (for instance, ... 2 Suppose that we have Turing machines M_1 and M_2 that compute the number-theoretic functions f_1 and f_2, respectively. Then we can construct the Turing machine M_2 \circ M_1 that computes the number-theoretic function f_2 \circ f_1, assuming appropriate restrictions on the domain and range of f_1 and f_2. This is done by first computing ... 2 There are several views of HoTT. The homotopic interpretation of p:Id_X(a,b) (or as the book writes, of p:a=b) is that p is a path in space X with endpoints a and b. We do have concatenation of paths, constructing by path induction, so it indeed gives a category-like structure per se. But! In general, associativity holds only up to the next ... 2 In fact your formula \displaystyle p = \frac{1}{n-1}\sum_{t=1}^n a_{ti} does give the probability that fish i will be eaten, given that fish i is one of the pair of fish that meet. The other probability, \displaystyle p = \frac{2}{n(n-1)}\sum_{t=1}^n a_{ti} is the probability that fish i will be eaten, without any prior knowledge about which fish ... 1 let G= (V,T,P,S), where P are: S\to S(E)|E E\to (S)E|0|1|ϵ Now consider a string w ϵ L(G) w ϵ (0)(0)()1 Construct Left Derivation S\to E\to (S)E\to (0)E\to (0)(S)E\to (0)(0)E\to (0)(0)(S)E\to (0)(0)(ϵ)E\to (0)(0)()E\to (0)(0)()1. Construct Right Derivation S\to E\to (S)E\to (S)(S)E\to (S)(S)(S)E\to (S)(S)(S)1\to (S)(S)(ϵ)1\to ... 1 This notion, which sounds somewhat like an oxymoron, is not very commonly used in mathematics, but it is in programming. The "strict" just means it is the irreflexive form "<" of the comparison rather than the reflexive "\leq". The "weak" means that the absence of both a<b and b<a do not imply that a=b. However as explained here, the ... 1 The problem statement is not clear, but I assume A≺B, So D=B-A is an infinite regular language. Now as shown here, D can be written as D=L_1\cup L_2, where L_1 and L_2 are infinite regular languages and L_1 \cap L_2=\varnothing. Consider C=A \cup L_1. 1 A Bloom filter is... an array of n bits with k random hash functions, f_i: S \to \{ 1, \dots , n\} with i = 1, \dots, \ell no too many "collisions" |f^{-1}(k)| < M for 1 \leq k \leq n. We then add elements of S_0 \subseteq S by "flipping" each of the k-hash values for our inputes. So  T = f_1(S_0) \cup \dots \cup f_n(S_0) . ... 1 The question is not well-posed, as it doesn't specify how a "positive" is determined. You are trying to say, based on just the first n/2 bits, whether a particular item has been added to the Bloom filter. When you check the bit positions given by the l hash functions, some of them will lie in the first half, and (unless you have been improbably lucky and ... 1 Write$${(n+a)^b \over n^b} = \left(1+{a\over n}\right)^b$$Then let n \to \infty and conclude! And of course, see here if you don't know the big theta notation. It's more or less the same as big O (that is, upper bound) with additional lower bound of the same order. 1 First note that q may be assumed to be primitive, because if q=r^k then q^{\omega}=r^{\omega}. Now if pq is primitive we're done by resetting p as pq. Let x be the first symbol of q. Then one can peel that off from q and get q^{\omega}=x(q')^{\omega} where q' is a cyclic permutation of q. For example$$(abc)(abc)(abc)\cdots ...

1

Your "updating" formula is correct. You do not need to know every value to know the average, all you need is the sum of scores and the number of scores. Your formula is effectively "recovering" the previous sum, adding in the new result, and re-averaging with one higher number of scores. A more compact version might be: $\bar x_{n} = \frac{\bar ... 1 One of the best references I know on order theory is the third chapter of Richard Stanley's Enumerative Combinatorics, Volume I. A manuscript of this is available by the author here. The topics aren't computer science oriented though, and cover lattices, Mobius functions, and some other interesting topics. It requires a fair bit of mathematical maturity, ... 1 The language$c^*ac^*bc^*$is *FO*$[<]$-definable but is not *FO*$[Succ, Pred, \min, \max]$-definable. More details in the paper The expressive power of existential first order sentences of Büchi's sequential calculus. 1 There are various ways to convert formulas to CNF avoiding the exponential growth of your example. Wikipedia's Conversion_into_CNF shows how to do that. A good reference is the Handbook of Satisfiability, Chapter 2, CNF Encodings. 1 A tight bound means that you need to find a function$f$such that$f$is both an asymptotically upper and lower bound for the running time of your algorithm. In big O notation this is usually denoted$\Theta$. When considering the asymptotical running time of an algorithm, you usually work in a model that specifies some operations you can use and the cost ... 1 I think your solution is incomplete, how do you know that$w_1$is in$L(G)$. Consider$w=aaabbb$,then$w1=aabbb$which clearly is not in the language. I will put my answer below, if you want to think more on it you can stop here. Now on, by the property I mean :"every prefix of$w$has at least as much$a$s as$b$s". The proof must consist of two ... 1 In general, strings of the form$a^nb^n$for$n > 0$are derived from productions of the form$A \rightarrow aAb$. So a context-free grammar generating the language$a^nb^n$for$n \geq 0$will have produtions$A \rightarrow \lambda$and$A \rightarrow aAb$. The second production will generate the leading and trailing$a$'s and$b$'s, while the ... 1 The answer depends on whether you are interested in cyclic or linear auto-correlation. If you have a sequence$s(i)$on length$L$, so$i=0,1,\ldots,L_1$, then its cyclic auto-correlations are $$\Theta(s,\tau)=\sum_{i=0}^{L-1}s(i)\overline{s(i+\tau)},$$ where the addition$i+\tau$is done modulo$L$. The cyclic auto-correlation comes to the fore, when you ... 1 The short answer is that adding two numbers by the "elementary school" algorithm has linear complexity. That is, given binary representations F and H of respective lengths$s$and$t$, the number of steps needed is$O(s+t)\$. This should be intuitively clear. After arranging the longer number over the shorter one, starting at the right hand side and ...

Only top voted, non community-wiki answers of a minimum length are eligible