# Tag Info

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 ...
• 13.4k

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 \... • 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 ... • 162k 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 ... • 916 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,... • 278k 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 ... • 162k 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 ... • 72.6k 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$... • 278k 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 ... • 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 ... • 61 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 ... • 2,253 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 ... • 162k 1 vote ### Intuition for Using Greedy Approach in Container with Most Water Problem There is in general no way to know in advance whether a greedy algorithm will work, other than trying it. My experience is that a typical approach is to try the obvious greedy algorithms first, and ... • 162k 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 ... • 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 ... • 111 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 ... 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 ... • 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, ...
• 30.6k

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