4,216 reputation
1025
bio website
location
age
visits member for 3 years, 6 months
seen 8 mins ago

Feb
27
comment Smullyan-To-Mock-a-Mockingbird, Find egocentric bird in L
NB I've attempted to test all expressions of the form $BB$ where $|B| < 6$ by beta-expanding repeatedly (using a priority queue by size of expression) and checking for each expression $XY$ so reached whether both $X$ and $Y$ had previously been encountered. The program failed with a stack overflow when looking for beta-expansions in a 1001-$L$ expression. $(N_3 N_3)(N_3 N_3)$, on the other hand, succeeds at the first opportunity with a 24-$L$ expression. So certainly there's no smaller solution which behaves as nicely as $(N_3 N_3)(N_3 N_3)$.
Feb
24
comment Smullyan-To-Mock-a-Mockingbird, Find egocentric bird in L
@Snowball, the problem there is that checking whether two combinator expressions are equivalent is undecidable in the general case, and the behaviour of $L L (L L) = L (L L (L L)) = \lambda x. L L (L L) (x x)$ seems to rule out testing extensionality for small cases, looking for a counterexample, as a strategy.
Feb
23
comment Is it possible to build a circle with quadratic Bézier curves?
@JasonS, I took a screenshot of the linked PDF.
Feb
21
comment Check if a point is on a plane? (Minimize the use of multiplications and divisions)
Why do you think that multiplication is the source of your errors? I'm not an expert in numerical analysis, but one of the first things I learnt is that subtraction is one of the biggest sources of error. Your choice of which vertex to call $v_0$ might have a big effect.
Feb
18
comment Game Theory Question - Matching Coins
Does the dotted line notation in en.wikipedia.org/wiki/Information_set_(game_theory) look familiar from your notes?
Feb
13
comment Little O Bound, Combinatorics
You're asking us to read your mind. What's the property $S_k$?
Feb
11
comment i^i^i^i^… Is there a pattern?
@nayrb, since $(a^b)^c = a^{(bc)}$, the convention is that $a^{b^c} = a^{(b^c)}$.
Feb
11
comment Logic behind the ID checksum?
@Prakhar, it's one of the first things I do when trying to understand a mystery sequence of numbers. It's a good way of identifying polynomials (if you repeat the operation $n$ times then an order-$n$ polynomial will give a constant vector).
Feb
11
comment Logic behind the ID checksum?
@Prakhar, "take first differences" means taking each adjacent pair and subtracting one from the other. So $1 - 2 \equiv 10, 6 - 1 \equiv 5, 3 - 6 \equiv 8, \ldots$.
Feb
9
comment Combinatorics - falling ball through a labyrinth
And for $m \times n$ labyrinths it's $\binom{m+n}{m}$, being a simple manifestation of staircase walks.
Feb
4
comment Proving that a language is not context-free
I suggest using the pumping lemma to derive a contradiction. That's the way pumping lemmas are typically used to prove that languages don't fall into the relevant class.
Feb
4
comment Which are the most effective modern intuitive definitions of a vector?
@twirlobite, "direction" is a very ineffective intuition. It makes sense in Cartesian products over fields of characteristic zero, but what would it mean in vector spaces over fields of finite characteristic?
Feb
3
comment Difference between breadth first search and iterative deepening depth first search
I think this question is better suited for the computer science stack. The difference is a memory/time tradeoff. ID-DFS will visit many nodes more than once, but it needs memory proportional to the current depth rather than to the size of the wavefront.
Jan
25
comment Find three $10\times10$ orthogonal Latin squares.
What's the link to Latin squares?
Jan
25
comment Proof of a Known Claim About Languages
@xavierm02, $a \notin \{ab\} \implies a \in \overline{\{ab\}} \implies a \in (\overline{\{ab\}})^*$
Jan
25
comment Proof of a Known Claim About Languages
@xavierm02, $a \in (\overline{ab})^*$.
Jan
24
comment Consider the smallest number in each of the $n\choose r$ subsets (of size $r$) of $S=\{1,2,\ldots,n\}$…
This might be clearer if you parameterise $\mu$.
Jan
16
comment enumerating in pseudo random order
I think that your amended explanation corresponds to a series of permutation compositions such that if we view the counter $x$ as having digits base 4 of $abcd$ then $$f(x) = (2301)^a A (2301)^b B (2301)^c C (2301)^d D$$ and that you want to ensure that all possible permutations are generated in an order which passes some kind of pseudorandomness test. Does this seem about right?
Jan
15
comment enumerating in pseudo random order
You seem to be trying to find $n^n$ distinct permutations of $n$ items, which is impossible for $n > 1$. Have I misunderstood something?
Jan
15
comment Can 18 consecutive integers be separated into two groups,such that their product is equal?
Although note that Erdős doesn't actually prove it for products of fewer than 100 consecutive numbers: he just refers to a paper by Seimatsu Narumi, Tôhoku Math. Journal, 11 (1917), 128-142 which apparently proves cases up to 202 consecutive numbers by special arguments.