Hot answers tagged

11

Yes. The Information Age is based on the Gödel number. A program in the programming language Python, for instance, is stored internally in the computer as a base-128 integer, via the ASCII which encodes characters as integers. If you wish to execute the program, you provide it to the computer as a Gödel number, expressed in base 128 (by typing in certain ...


3

The basic idea of Gödel numbers is to establish a mapping between logical statements and natural numbers. This allows to apply reasoning on natural numbers, and those results can be translated back into reasoning on logical statements. Related mappings are: the mapping between Turing machines, one embodiment of computable functions, and natural numbers. ...


2

when it says "....concave function of $p(x)$", does that mean function of the probability of one particular realization of $X$? No. A concave function has the property $f(\frac{a+b}{2}) \ge \frac{f(a)+f(b)}{2}$ [*] In the case of the mutual information, the variables ($a,b$ above) are the probabilities densities themselves. So that would translate as ...


2

I don't think that intution can help much here. It's true that the number of sortings fits in 29 bits ($12 ! < 2^{29}$), so it's in principle possible to identify a permutation by making at most 29 yes-no questions. But a comparison algorithm imposes a huge restriction: instead of chossing among all the arbitrary yes-no questions ($2^{11}=2048$ questions)...


2

The key idea of Gödel numbering is that logical syntax can be treated as data. Applications of this concept pervade modern computing.


1

This has indeed been done before. Given a probability distribution $p$ with $n$ distinct outcomes $x_i$, the quantity $$-\sum_{i=1}^n \frac{p(x_i) \log(x_i)}{\log(n)}$$ is sometimes called as the efficiency, or the normalized entropy. Wikipedia has a short paragraph on this, but other than that I haven't found any good references. Some searches on google ...


1

First of all, I would use log base 2 instead of natural log because it's easier to talk about its meaning as the number of yes/no questions on average to guess the value. Given 20 choices, the maximum entropy distribution has entropy of 4.322 bits. While your distribution has 3.607 bits, which is 83% of the maximum possible value. Of course you can ...


1

One way is the nuclear norm, which is the sum of singular values. It's often used in low rank matrix completion, such as in "Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization" by B. Recht et al.


1

It might be simpler than that, but without knowing exactly what pictures you have in your head, I can't be 100% sure. I think it is a question of remembering that concatenation is essentially multiplication by $x^n$. You take $$R(x) = M(x)\cdot x^n\mod G(x)$$ You say that you "append" $R(x)$ to $M(x)$, which is to say that you calculate $$RM(x) = (M(x)\...


1

I believe your doubt is not really related to CRC but with cyclic codes (on which CRC are based), more specifically with the construction of systematic cyclic codes. This is explained in any textboox. Here's a summary. A binary $(n,k)$ cyclic code has $2^k$ codewords, they correspond to a binary polynomial $c(X)$ of degree less than $n$. A particular code ...


1

For the first question: Entropy can be viewed as the expected value of the random variable that is the logarithm of the probabilities (alphabet size $M$): $$H_b = -\sum_{i=0}^{M}\log_b(p_i)p_i = -E[\log_b(p_i)]$$ For logarithm with base 2, this is the average number of bits required per symbol $(H_2)$. For some other number system, change the base of ...


1

The significance of having convex sets comes from statistical mechanics. This is mentioned at least in two places in Cover & Thomas's book (2nd edition); the first paragraph in Ch. 12 and Example 12.2.5. However, convexity of $\mathcal{P}$ does not play any role for the existence of I-projection. Since $D(\cdot\|\cdot)$ is lower semi-continuous, the ...


1

Question 1: Is the logarithm on base 2 or base 10? As entropy is in bits, it should be in base 2. However, the Lyapunov Exponent (LE) for Tent Map = 0.69 approx (please correct me if wrong). If this relationship applies to all maps, then log2(2) and log10(2) would give entirely different result. The Lyapunov exponent is commonly defined using the ...


1

The following answer of mine might probably not be able to provide a rigorous justification for why the solutions to the two optimization problems are different, but Campbell provides interesting differential geometric viewpoints to the same, which I present below: If we consider the initial value problem \begin{align} \frac{d}{du}x_{i}(u)&=\left(l_{i}-\...



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