11 votes
Accepted

To what extent is my interpretation of computable numbers correct?

This is exactly the incorrect interpretation of "computable", resulting of trying to replace the precise definition with (possibly misplaced) intuition. $\pi$ or any other irrational number also has ...
Ariel's user avatar
  • 13.4k
8 votes
Accepted

Elimination rule for the equality type aka J axiom

A complete understanding of what J was actually saying and why has only come fairly recently. This blog post discusses it. While thinking in terms of homotopy and ...
Derek Elkins left SE's user avatar
6 votes

How to tell if a language is recognizable, co-recognizable or decidable?

L is recognizable A language $L$ is recognizable if and only if there exists a verifier for $L$, where a verifier is a Turing machine that halts on all inputs and for all $w \in \Sigma^*$, $w \in L \...
roctothorpe's user avatar
  • 1,158
5 votes

Why don't integer multiplication algorithms use lookup tables?

If you want to use lookup tables, and you have 4GB of memory, you'll only be able to use a lookup table with about $2^{32}$ entries or fewer, so you'll only be able to handle multiplication of numbers ...
D.W.'s user avatar
  • 159k
4 votes
Accepted

Why don't integer multiplication algorithms use lookup tables?

Some integer multiplication algorithms do use lookup tables. The IBM 1620 Model I "CADET" lacked a conventional ALU: addition and subtraction used a 100 digit table; multiplication used a ...
David Cary's user avatar
4 votes

Seeking an "intuitive" proof

Since the $y_i$ are non-negative, you can think of $y_1,\ldots,y_n$ as specifying a probability distribution. One way to sample from this distribution is via the partition $$ [0,1) = [0,y_1) \cup [y_1,...
Yuval Filmus's user avatar
3 votes

Bellman-Ford algorithm intuition

I can give you the intuition behind Bellman-Ford. It is beautiful! I'm going to do it in an indirect way. I want to share a warm-up puzzle that might seem unrelated, but stay with me. Suppose we ...
D.W.'s user avatar
  • 159k
3 votes

To what extent is my interpretation of computable numbers correct?

First off, I'm not sure what the intuition you're proposing is, so I'll make some general remarks. In the comic, the problem given to the robot was ill-posed; the interpretation of the request is not ...
Raphael's user avatar
  • 72.4k
3 votes
Accepted

Of monotone formulas and same ones satisfying certain properties

Spira's result uses the technique of formula balancing. For simplicity, I describe the non-monotone case, the monotone case being similar. Let $\phi$ be a formula of size $n$. We can think of $\phi$ ...
Yuval Filmus's user avatar
3 votes

How to tell if a language is recognizable, co-recognizable or decidable?

Main ideas Being recognizable means you can build an automatic process (we'll get back to that later) that takes a word as a parameter such that If the automatic process ends, it returns either YES ...
wazdra's user avatar
  • 362
2 votes

Algorithmic intuition for logarithmic complexity

The intuition is how many times you can halve a number, say n, before it is reduced to 1 is O(lg n). For visualizing, try drawing it as a binary tree and count the number of levels by solving this ...
user1234's user avatar
2 votes
Accepted

What is the simplest/smallest subset an OOP language like C#/JavaScript that is Turing-complete?

It takes very little to obtain Turing completeness. For example the While programming language and Counter Machines are Turing complete and are easily recognized as a subset (up to syntax) of all ...
kne's user avatar
  • 2,254
2 votes
Accepted

Intuition behind straight-line programs

A straight-line program is one with no branches, no loops, no conditional statements, no comparisons -- just a sequence of basic operations. A straight-line program for a finite group $G$ is a ...
D.W.'s user avatar
  • 159k
1 vote
Accepted

Eulerian Path and Circuit Algorithm - How does it work?

The algorithm you linked is (or is closely related to) Hierholzer's algorithm. While Fleury's algorithm stops to make sure no one is left out of the path (the "making decisions" part that ...
Vaekor's user avatar
  • 209
1 vote

To what extent is my interpretation of computable numbers correct?

I think there are too many kinds of sort-of uncomputability involved here: Uncomputable because ill-defined. "The smallest rational larger than 1.0" would be an example. Uncomputable because of ...
toolforger's user avatar
1 vote

Google's Deep Dreamer

Simply put, you: Pick a layer Forward propagate to that layer Set the gradient at that layer to the activation at that layer. Backpropagate to update the image The general idea is that you want that ...
Christabella Irwanto's user avatar
1 vote

Google's Deep Dreamer

So far nothing's been said about technical details of DeepDream. I'll fill the blank. The procedure is the following: pick some layer from the network (usually a convolutional layer), pass the ...
Maxim's user avatar
  • 640
1 vote

Why is $L= \{ 0^n 1^n | n \geq 1 \}$ not regular language?

Simple rule: Regular expressions can't count. That said, sometimes you are given languages that look like they need counting, but it turns out they actually don't. An example is that language over (0, ...
gnasher729's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible