# Tagged Questions

**1**

vote

**1**answer

93 views

### Total conditional complexity

By $C(|)$ denote conditional complexity.
By $CT(|)$ denote total conditional complexity.
For every n there exist two strings $x$ and $y$ of length $n$ such that $C(x|y) = O(1)$
but $CT(x|y) \ge n $.
...

**1**

vote

**1**answer

70 views

### Connection between inf-entropy rate and min-entropy

I am reading the paper "Generating random bits from an arbitrary source: fundamental limits" by Vembu and Verdu. This paper is written in the language of information theory, however, I need to ...

**8**

votes

**2**answers

349 views

### Where should I learn about Kolmogorov complexity of overlapping substrings?

I would like to know more about the relationship between the Kolmogorov complexity of a string and that of its substrings. The relation that up to an additive constant, $K(x,y) = K(x) + K(y\ |\ x, ...

**0**

votes

**1**answer

284 views

### Is there any relationship between a tree(graph theory) and semi-metric?

suppose we have a tree(undirected) with $n$ vertices.The edges are weighted(distances). Is it possible to impose a semi-metric structure on the graph using these distances and adjacency matrix?

**6**

votes

**1**answer

321 views

### compression of a Turing machine run sequence

consider a Turing machine with a set of states $s_n$ and alphabet symbols $a_n$. now consider a "run sequence" generated from a starting input in the following sense. the run sequence is defined as ...

**7**

votes

**2**answers

863 views

### Distribution of the computable numbers on the real number line

If we order all the positive computable real numbers $r_1,r_2,r_3...$ by their Kolmogorov complexity in some language $L$, then make a histogram plot of the $r_i$ on the real line, and we scale it ...

**1**

vote

**0**answers

204 views

### Geometric/Analytic techniques for constructive and asymptotic bounds in the Lee metric

Slight extension of cross posting from
http://cstheory.stackexchange.com/questions/7408/lee-metric-gilbert-varshamov-and-hamming-bounds-for-larger-relative-distance-rang (closed there)
The following ...

**2**

votes

**2**answers

187 views

### Indexing schemes of binary sequences

I am looking for "low-complexity" indexing methods to enumerate binary sequences of a given length and a given weight.
Formally, let $T_k^n = \{x_1^n \in \{0,1\}^n: \sum_{i=1}^n x_i = k\}$. How to ...

**0**

votes

**1**answer

171 views

### Building optimal rewriting rules.

Please give me some pointers where I can learn more about the following problem:
I have two alphabets A and B. A have a dictionary which contains words in A together with their translation in B (ie. ...

**13**

votes

**8**answers

2k views

### How Does Random Noise Typically Look?

How does random noise in the digital world typically look?
Suppose you have a memory of n bits, and suppose that a "random noise" hits the memory in such a way that the probability of each bit being ...