Computer Science Weekly Newsletter

Computer Science newsletter

Top new questions this week:

Is there a more intuitive proof of the halting problem's undecidability than diagonalization?

I understand the proof of the undecidability of the halting problem (given for example in Papadimitriou's textbook), based on diagonalization. While the proof is convincing (I understand each step of ...

computability proof-techniques undecidability halting-problem intuition  
asked by user118967 18 votes
answered by Luke Mathieson 13 votes

In what sense is the Mandelbrot set "computable"?

The Mandelbrot set is a beautiful creature in Mathematics. There are a lot of beautiful images of this set created with high precision, so obviously this set is "computable" in some sense. However, ...

computability  
asked by Earth Engine 12 votes
answered by Yuval Filmus 11 votes

Regularity of unary languages with word lengths the sum of two resp. three squares

I think about unary languages $L_k$, where $L_k$ is set of all words which length is the sum of $k$ squares. Formally: $$L_k=\{a^n\mid n=\sum_{i=1}^k {n_i}^2,\;\;n_i\in\mathbb{N_0}\;(1\le i\le k)\} $$ ...

formal-languages regular-languages  
asked by Danny 8 votes
answered by Yuval Filmus 8 votes

Is there a continuous hash?

Questions: Can there be a (cryptographically secure) hash that preserves the information topology of $\{0,1\}^{*}$? Can we add an efficiently computable closeness predicate which given $h_k(x)$ and ...

complexity-theory cryptography hash string-metrics topology  
asked by Kaveh 6 votes
answered by D.W. 4 votes

Why is binary search called binary search?

I heard several possible explanations, so I would like some trustable reference. Update 05.19: I'm interested in the question because one of mine students wrote in his thesis that the name comes from ...

terminology reference-request history  
asked by domotorp 5 votes
answered by D.W. 1 vote

TM recognizing $0^n1^n$ requires Ω(log n) space

I am trying to prove that any deterministic 1-tape Turing Machine which recognizes the language $L = \lbrace{0^n1^n | n \geq 0 \rbrace}$ requires $\Omega(\text{log }n)$ space. I believe this can be ...

complexity-theory context-free space-complexity lower-bounds crossing-sequence  
asked by rookie 5 votes
answered by Shaull 2 votes

Question on NP $\cap$ coNP

I'm struggling with a past paper question and would appreciate any hints: Suppose $L_1, L_2 \in $ NP $ \cap $ coNP and $L_1 \oplus L_2 = \{ x : x $ is in exactly one of $L_1 $ or $ L_2 \} $. Then ...

complexity-theory closure-properties complexity-classes np  
asked by Richard 5 votes
answered by Yuval Filmus 5 votes

Greatest hits from previous weeks:

Why, really, is the Halting Problem important?

I don't understand why the Halting Problem is so often used to dismiss the possibility of determining whether a program halts. The Wikipedia article correctly explains that a deterministic machine ...

computability halting-problem  
asked by Brent 71 votes
answered by jmite 124 votes

How to prove that a language is not context-free?

We learned about the class of context-free languages $\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is ...

formal-languages context-free proof-techniques reference-question  
asked by Raphael 44 votes
answered by jmad 38 votes

Can you answer these?

Why is exact nearest neighbor search hard in high dimensional spaces?

I started research on nearest neighbor search in IR a couple of weeks ago. I am still very new to this field, but what I discovered so far from literature is: 1) For the exact nearest neighbor ...

search-algorithms search-trees hash nearest-neighbour  
asked by Jonas Köhler 1 vote

NPDA, guessing capability and stack as an exclusive resource

Context Free languages is exactly the class of languages recognized by Nondeterministic Push Down Automata (NPDA). We can view a nondeterministic transition as a guess; for example if $L = \{x x^R ...

reference-request automata pushdown-automata computation-models  
asked by Vor 1 vote

sets of axioms for LADR automated theorem provers

I am pretty new to ATP, but I'm really enjoying playing around with prover9. I have found a nice set of axioms for basic information-theoretic proofs here, I was wondering if there are some ...

reference-request automated-theorem-proving  
asked by Ziofil 1 vote
Subscribe to more Stack Exchange newsletters


Unsubscribe from this newsletter or change your email preferences by visiting your subscriptions page on stackexchange.com.

Questions? Comments? Let us know on our feedback site. If you no longer want to receive mail from Stack Exchange, unsubscribe from all stackexchange.com emails.

Stack Exchange, Inc. 110 William St, 28th Floor, NY NY 10038 <3