Johannes Kloos
Reputation
Top tag
Next privilege 10,000 Rep.
Access moderator tools
 Mar25 reviewed Approve About the definition of fixed-point combinators Mar23 comment Why is this Goldbach's Conjecture Proof Wrong? As a first comment, I don't understand what your proof of Lemma 2 shows. In particular, how is "L cannot be a prime" a contradiction? Mar17 answered Program with no intermediary states Mar17 comment Program with no intermediary states Oh, wait. You may need higher-order functions; see the answer. Mar17 comment Program with no intermediary states As long as you can give effective semantics to your model/programming language, yes. Does this answer your question? Mar17 comment Program with no intermediary states To be more concrete, suppose you have big-step semantics for an imperative programming language without function calls. Then for each statement, we get a (computable) function mapping a variable context to a variable context. Chain all these functions, and you have a representation of your program as a sequence of function applications. Mar17 comment Program with no intermediary states What is your computation model? If you allow any model and provide denotational semantics, the answer is "trivially, yes": Just take the function induced by the denotational semantics. Edit: This also works with other formal semantics, e.g., small-step operational semantics or natural semantics. Mar13 reviewed Approve Showing a Problem Is Undecidable Mar13 awarded Proofreader Mar13 reviewed Approve General versions of (Second part of) Fundamental Theorem of Calculus Mar8 comment What is the meaning of $M \models \varphi$? That is the right interpretation. Mar8 answered What is the meaning of $M \models \varphi$? Mar5 awarded Yearling Feb28 comment Given S is non-empty and sup(S)=inf(S), prove that the set S has only one element. @MPW: I know, but I wanted to point out a gap in the proof. Feb28 comment Given S is non-empty and sup(S)=inf(S), prove that the set S has only one element. A minor thing: What if $S = \varnothing$? Feb20 comment Knuth-Bendix completion algorithm: word problem I'm not quite sure what you mean be "see certain structures". Are you asking how Knuth-Bendix is implemented, or do you want to know how to find the complete set of normal forms? Feb9 comment Buchberger's criterion to show Grobner basis for linear forms Yes, that's the idea here. Feb9 comment Buchberger's criterion to show Grobner basis for linear forms Right, scratch the "strictly". If its support is contained, you can reduce by $g$, yielding $E$ (and if you do it right, you can reduce in such a way the the leading coefficient of $D$ is reduced to zero), thereby getting a polynomial that is smaller according to the monomial ordering. By properties of the reduction, $E \in L$ again, so you can repeat the process. Because of well-foundedness, this can only happen finitely many times. What would the normal form look like, when it's in $L$? Feb9 comment Buchberger's criterion to show Grobner basis for linear forms Didn't you want to show this for $k \neq l$? Anyway, if $k = l$, you have found a critical pair. Since $L$ is an ideal, certainly $D := x_l A -x_k B \in L$. By definition of $S$, there's some $g \in S$ whose support is strictly contained in that of $D$. What can you deduce from this? Feb9 comment Buchberger's criterion to show Grobner basis for linear forms Note that A and B are elements of $S$, and they have different leading coefficients. Let's assume that \$l