4,942 reputation
1932
bio website mpi-sws.org
location Kaiserslautern, Germany
age 32
visits member for 2 years, 1 month
seen 15 hours ago

PhD student at MPI-SWS.


Mar
23
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?
Mar
17
comment Program with no intermediary states
Oh, wait. You may need higher-order functions; see the answer.
Mar
17
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?
Mar
17
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.
Mar
17
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.
Mar
8
comment What is the meaning of $M \models \varphi$?
That is the right interpretation.
Feb
28
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.
Feb
28
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$?
Feb
20
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?
Feb
9
comment Buchberger's criterion to show Grobner basis for linear forms
Yes, that's the idea here.
Feb
9
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$?
Feb
9
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?
Feb
9
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<k$. So, first reduce with $A$ as long as possible. Can you then prove that the remainder is divisible by $B$?
Dec
7
comment Why $\langle I, J\rangle =R$ for distinct prime ideals $I$, $J$ of a principal ideal domain $R$?
You need the extra side condition $I,J \neq 0$!
Dec
6
comment find the extremal of a function
I'm sorry, but I find this answer completely incomprehensible.
Nov
27
comment Show that the field $L = \mathbb F_3[X]/\langle X^5 - X + 1\rangle$ consists of $243$ elements and that $[X][f] = [1]$ for some $[f] \in L$.
Some hints: First of all, it helps to consider $L$ as an $\mathbb F_3$-vectorspace, and note that $243 = 3^5$. Now, if $K$ is a finite field with $k$ elements, an $n$-dimemsional $K$-vectorspace has $k^n$ elements... To show that $L$ is a field, you should be able to use the following well-known theorem: Let $R$ be a ring and $I$ a maximal ideal. Then $R/I$ is a field.
Nov
25
comment interpret a sum geometrically
That question doesn't address the geometric interpretation, though...
Nov
18
comment Limit: $\lim_{n\to \infty} \frac{n^5}{3^n}$
You could try induction to show that from some $n$ on, $n^5/3^n \le c/a^n$ for suitable $a,c \ge 1$.
Nov
15
comment DPLL Algorithm $ \rightarrow $ Resolution proof $ \rightarrow $ Craig Interpolation
As I wrote, this must be given. It cannot be derived.\
Nov
12
comment how can exponential of two terms be expressed as sum of the two terms?
Are you looking for a finite sum (then this will work in special cases only), or is a powerseries acceptable?