The 2024 Developer Survey results are live! See the results

# Tag Info

### Is Goedel's 1st theorem not algorithmically derivable?

Your reasoning is incorrect. It is true that your hypothetical "proof deriver" cannot derive all true statements. No proof derivation system can, and indeed, it is not even possible to express the ...
• 8,252

### Find an upper bound for $T(n)=T(\sqrt{n})+10\log\log n$

An alternative solution still using domain transformation/change of variables. $$T(n) = T(\sqrt{n}) + \log \log n$$ 1. Let $m = \log n$ We can then define a new function $S$ based on how $m$ ...
• 4,511
Accepted

Your invariant, together with the negation of the loop condition, is not strong enough to imply your postcondition. Try adding an additional conjunct to the invariant which, together with $\neg\ i<... • 2,176 4 votes Accepted ### Why is this a proof by contradiction for this algorithm? Isn't this a direct proof instead? You seem to think the structure of the proof is: suppose the algorithm is incorrect; prove that the algorithm is, in fact, correct; this contradicts 1., so the algorithm is correct. That's almost, ... 4 votes Accepted ###$\Phi_1=1$or$\Phi_1=2$for the dynamic$\text{Table-Insert}$, where$\Phi_i$is the potential function after$i$th operation, as per CLRS You have caught an instance of the infamous off-by-one error in that popular textbook whose name we shall not mention again. To repeat, it is correct that "the cost$c_1=1$,$\Phi_0=0$", &... • 39k 4 votes Accepted ### Show$\{0^𝑚1^𝑛|𝑚≠𝑛\}$is not regular Try to express in natural language what$\overline{L}$contains; that is, what words$L$doesn't contain. Most obviously, it's "words of the form$0^m0^n$, with$m = n$." However, it also ... • 359 3 votes ### how to prove that log(n!) >= c n log(n) for some c >0?$n! = n \cdot (n-1) \cdot ... \cdot 1 \ge n \cdot (n-1) \cdot ... \cdot (n/2) \ge (n/2)^{(n/2)}$so$\log(n!)≥c\cdot n\cdot\log n$for$c \ge 1/2$3 votes ### Number of possible heaps on$\{1,...,2^h-1\}$The definition you give looks like the definition of a complete tree. With the restriction that nodes are in$[\![1, 2^h-1]\!]$, then it is also a perfect tree of height$h$. Instead of looking at ... • 15.9k 3 votes ### Why is this a proof by contradiction for this algorithm? Isn't this a direct proof instead? It's a proof by contradiction that could easily be rewritten as a direct proof. To rephrase it as a direct proof, we divide it into two claims:$max$is an element of$A$.$max \geq A[j]$for all$j$... • 278k 3 votes Accepted ### Is this proof for showing that$EQ_{CFG}$is co-Turing-recognizable incorrect? In this context, lexicographic order means: First order by length. Within each length, order lexicographically. You're saying that the proof is incorrect, but in fact it is only inaccurate in that ... • 278k 3 votes Accepted ### Question about proving that Rado's function is non-computable Thanks for the clarification! I really misinterpreted your question. Okay, so we have the computable function$f$, the also computable function$F$that is based on$f$, and the Turing machine$M_F$... • 173 3 votes Accepted ### Optimizing coin splitting - Is this algorithm as fast as I think? You have made significant progress on this problem. Your final conclusion, "the overall algorithm asymptotically requires$\Omega(n^2)$steps" is likely to be correct as well. Analysis of Your ... • 39k 3 votes Accepted ### Find an upper bound for$T(n)=T(\sqrt{n})+10\log\log n$We can expand the recursion (ignoring the constant 10) as follows:$\begin{align*} T(n) &= \log \log n + \log \log n^{1/2} + \log \log n^{1/4} + \log \log n^{1/8} + \cdots \\ &= \log \log n +... • 278k 3 votes Accepted ### Proof Review: Integer Factorization is in NP You are missing something. If you are given what is supposed to be a factorisation of a number x, it's not enough to show that the product of those numbers is x. You also have to prove that all the ... • 31.1k 3 votes ### Not understanding this way of proving undecidability of the termination problem This is a very succinct way of presenting the contradiction argument, and I strongly recommend you read a textbook on the topic, or some detailed explanations. There are tons of resources that explain ... • 17.3k 3 votes ### Hierarchy of parser grammars vs Chomsky hierarchy of grammars and the comparsion of the language acceptance power of each parser grammar All of the grammars in your first figure are context-free grammars. That text seems to identify grammar with context-free grammar. • 278k 3 votes Accepted ### Disprove: if L is decidable then Prefix(L) is decidable It is correct that ifL$is decidable language$\text{Prefix}(L)$can be undecidable. The language$Lgiven in the question is a concise example of a decidable language the prefix language of which ... • 39k 3 votes Accepted ### Find a unit square containing most of the points "A window" will also mean "an axis-aligned unit square". As observed in the question, there is an optimal window such that either the bottom left corner is a given point. or the ... • 39k 3 votes Accepted ### if P = NP, does it mean that P = NP = NP-complete? No. Even assuming\mathsf{P}=\mathsf{NP}$, it is not true that all the languages therein are$\mathsf{NP}$-complete. An example of a language that is in$P$but it is not$NP$-complete (regardless of ... • 29.6k 2 votes ### Is Goedel's 1st theorem not algorithmically derivable? Our proof deriver enumerates all possible axiomatic systems But the set of possible axiomatic systems also include the inconsistent systems. On the other hand, the consistent axiomatic systems are ... • 5,400 2 votes Accepted ### Show that function is not turing-computable? This proof is correct as written, well done :) Remember this pattern, because an identical proof can be used in a wide variety of similar problems such as rational/irrational numbers and polynomials/... 2 votes ### Universal Lossless Compression? Then you can compress all$g_j ∈ S_N$, by iterating through$A$until you find$a_i|f(a_i,g_j)−m>0$. I'm not sure what the notation means (the pipe here, and also$\#A$elsewhere), but still: ... • 72.7k 2 votes ### Optimizing coin splitting - Is this algorithm as fast as I think? Your algorithm may work, but FWIW it's more conventional to build game trees where the two players' moves form alternating layers of vertices rather than combining one move from each into a single ... • 2,082 2 votes ### Show that the Language L is not regular (pumping lemma) Let me explain the easiest way to show that this language isn't context-free. It it were, then its intersection with$c(a+b+d)^*$would also be. This intersection is$cda^nb^n$. If the latter were ... • 278k 2 votes Accepted ### Minimal paths as solution of a linear program of a special network flow There is a major flaw in your question: You presented a shortest path formulation and not a special case of a network flow problem. Your objective function minimizes the cost of the path. The next 5 ... 2 votes Accepted ### How to Apply Elementary Axioms from Kleene Star to an Inequality I assume that in your definition$a \leq b$iff$a + b = b$. First, note that if$a \leq b$and$b \leq a$, then$a = a + b = b + a = b$. Therefore, in order to show that$a = b$, it is sufficient to ... 2 votes Accepted ### Number of possible heaps on$\{1,...,2^h-1\}$When$n = 2^h-1$, the heap is just a complete binary tree of height$h$. Clearly$C_0 = C_1 = 1$. For$h > 1$, we can decompose the heap as follows: The root must be 1. Each of the two children ... • 278k 2 votes ### Optimizing coin splitting - Is this algorithm as fast as I think? Aren't you just overcomplicating things? I'd use an n x n matrix, and a nested loop that finds the result in about five lines of code in O (n^2). Let b[i,j] = the amount by which you can beat your ... • 31.1k 2 votes Accepted ### how to prove that log(n!) >= c n log(n) for some c >0? ... further simplify$(n/2)\log(n/2)$-->$(n/2)\log(n^{-2})$, ... This is wrong. In fact, for$n\ge 3$,$n^{\log_3 2}\ge 2, so \begin{align} (n/2)\log(n/2)&=(n/2)(\log n-\log2)\\ &\ge (n/2)\... • 7,565 2 votes ### Prove\epsilon(S\cap T)\subseteq S \cap T$Since your definition of$\epsilon$-closure isn't really a definition, it is impossible to prove anything using it. Instead, let me use the following definition: the$\epsilon$-closure of a set$S \...
• 278k

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