## 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

### 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

### 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

### 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

### 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

### 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

### 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

## 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

### 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

### 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