-3
votes
1answer
85 views

“logical distance” link algorithmic complexity to statistical information [closed]

Someone mentioned what I think was referred to as 'logical distance'. My hard drive crashed and I dont have the link anymore. I do recall that I ran across it on this site, in response to linking ...
3
votes
1answer
317 views

Complexity of convex polytope volume calculation ? (Volume of Voronoi cell) (Error probability)

Assume I have polytope in R^k given by N (k<< N) linear inequalities (A_i x < b_i). I guess complexity of its volume calculate is higher than linear in "N", am I right ? (Is the complexity ...
6
votes
1answer
313 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
2answers
833 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 ...
11
votes
6answers
1k views

Compressing Graphs (Kolmogorov complexity of graphs)

What is known about compressing graphs? Here, with "compressing", I mean something like "putting a graph into a zip program"; or with a more technical expression, what is know about the Kolmogorov ...
5
votes
1answer
793 views

Is pattern recognition NP-complete?

Hello, is the problem of pattern recognition (for a given sequence of n numbers, find the shortest Turing machine with an alphabet of 42 elements that will output these n numbers in, say, 5*n^3 time) ...
2
votes
2answers
182 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 ...
10
votes
4answers
1k views

reversible Turing machines

Hello, Let T be a Turing machine such that 1) it operates on the alphabet {0,1}, 2) its set of states is A 3) the language it accepts is $L$ . Does there exists a Turing machine S which also ...