Reputation
5,390
Top tag
Next privilege 10,000 Rep.
Access moderator tools
Badges
1 11 37
Newest
 Good Answer
Impact
~138k people reached

Mar
31
comment Push Down Automata
What have you tried so far? Also, do you know how to construct a PDA for $a^nb^n$? If you have one for $a^nb^n$ and one for $a^nc^n$, what can you do with that?
Feb
22
comment When is matrix multiplication commutative?
Here's an example why this condition is not neccesary: Take any non-diagonalizable matrix $A$. It will always commute with the unit matrix $1$, but $A$ and $1$ are clearly not simultaneously diagonalizable.
Feb
12
comment When is matrix multiplication commutative?
It's not neccesary, AFAICT. I can't think of a counter-example right know, though.
Jan
22
comment $f(x) \in R[X]$ irreducible $\Rightarrow (f(x))$ ideal?
Just to make sure: Do you mean by $(f)$ the ideal generated by $f$?
Jan
11
comment Powers of $2\times 2$ matrices, such that $A^n = I$
Do you know about rotation matrices?
Sep
13
comment What is a polynomially bounded function?
Your argument would be correct if, say, $2^x-1$ was actually a polynomial. But by definition, a polynomial is of the form $a_n x^n + a^{n-1} x^{n-1} + \cdots + a_0$ for some parameters $a_0, \ldots, a_n$, and $2^x-1$ is not of this form.
Jul
6
comment Help with function proof
Indeed, my bad. Ignore my previous comment.
Jul
6
comment Help with function proof
@CameronWilliams: If you prefer, write $\mathbb{N}_0$. My natural numbers start at 0.
Jul
6
comment Help with function proof
To everybody trying to show a proof: Please make sure that what you want to prove is actually correct. In particular, consider $A = B = \mathbb{N}$, $f(x) = 0$, $Y = 2\mathbb{N}$ (the set of even numbers).
Jul
6
comment Who named “Quotient groups”?
Skimming the paper, Hölder uses the term "Faktorgruppe" (factor group), and refers to an expression "factor of composition" that he attributes to Jordan.
May
31
comment How to extend an existing orthogonal set of vectors?
Would guessing a linearly independent vector and then taking the orthogonal part work? You can make a vector orthogonal to a given set of vectors using methods similar to Gram-Schmidt...
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?