user avatar
user avatar
user avatar
John L.
  • Member for 3 years, 11 months
  • Last seen this week
  • Canada
177 votes
13 answers
60k views

Why, really, is the Halting Problem so important?

  • 2,477
92 votes
7 answers
22k views

Why are some programming languages "faster" or "slower" than others?

  • 1,352
74 votes
1 answer
14k views

Language theoretic comparison of LL and LR grammars

  • 70.9k
73 votes
3 answers
48k views

Express boolean logic operations in zero-one integer linear programming (ILP)

  • 141k
52 votes
8 answers
112k views

How to prove a language is regular?

  • 869
52 votes
6 answers
11k views

Keeping a String Secret in (Open) Source Code

  • 657
50 votes
4 answers
6k views

What exactly is the semantic difference between set and type?

  • 3,474
49 votes
1 answer
21k views

Show that { xy ∣ |x| = |y|, x ≠ y } is context-free

49 votes
4 answers
5k views

What is the meaning of $O(m+n)$?

  • 1,472
48 votes
10 answers
11k views

O(·) is not a function, so how can a function be equal to it?

  • 591
45 votes
2 answers
8k views

Perplexed by Rice's theorem

45 votes
2 answers
20k views

How to show that a function is not computable?

  • 2,111
43 votes
4 answers
17k views

What are common techniques for reducing problems to each other?

  • 70.9k
41 votes
6 answers
6k views

How does a computer work?

  • 519
35 votes
6 answers
8k views

Do lossless compression algorithms reduce entropy?

  • 453
32 votes
2 answers
21k views

Show how to do FFT by hand

  • 483
32 votes
7 answers
9k views

What are the simplest examples of programs that we do not know whether they terminate?

  • 4,017
30 votes
2 answers
5k views

Is Lambda Calculus purely syntactic?

  • 431
30 votes
7 answers
6k views

Are algorithms (and efficiency in general) getting less important?

30 votes
2 answers
12k views

Optimization version of decision problems

30 votes
4 answers
28k views

Is Morse Code binary, ternary or quinary?

29 votes
2 answers
2k views

Longest Repeated (Scattered) Subsequence in a String

  • 393
29 votes
1 answer
1k views

Asymptotics of the number of words in a regular language of given length

28 votes
2 answers
41k views

How to prove that a language is context-free?

  • 141k
28 votes
3 answers
39k views

When is the minimum spanning tree for a graph not unique

  • 467
26 votes
3 answers
2k views

Is the language of pairs of words of equal length whose hamming distance is 2 or greater context-free?

  • 737
24 votes
5 answers
5k views

What is the formal, rigorous definition of a programming language?

23 votes
3 answers
2k views

Why are NP-complete problems so different in terms of their approximation?

  • 505
21 votes
2 answers
13k views

Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?

  • 1,091
21 votes
3 answers
6k views

Why is this code uniquely decodable?

1
2 3 4 5
7