8
votes
2answers
346 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, ...
1
vote
1answer
512 views

Collatz conjecture— finite state machine transducer construction, origination?

wikipedia has an entry on the Collatz conjecture with a section on As an abstract machine that computes in base two. this apparently describes a construction of a FSM transducer computing sequential ...
0
votes
1answer
190 views

hypergraph cartesian join operation (over same vertex set)

consider two hypergraphs $H_1 = (V, \mathscr{E}_1), H_2 = (V, \mathscr{E}_2)$ over the same vertex set $V$. am interested in what could be called a "cartesian join" operation building a new hypergraph ...
5
votes
1answer
386 views

Arrangement of integers 1..k^2 in k*k grid to minimize energy function

Question arises from considering cache oblivious algorithms. What is the optimal way arrange the numbers $1$ to $k^2$ in a grid, to minimize to average difference between any two neighbouring ...
6
votes
1answer
319 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 ...
9
votes
1answer
2k views

All-pairs shortest paths in trees?

This is a reference request, since I'm sure what follows isn't new, but I can't seem to find it. Suppose that we have a finite tree $T$ with non-negative weights on the edges. Naively, computing the ...
4
votes
1answer
242 views

Turing Machine which generates order on the set of its states

This question is related to this one Do Turing Machines generates any nontrivial lattice on the set o symbols or states? The Turing machine (TM) is an abstract model for effective implementation of ...
1
vote
1answer
211 views

Do Turing Machines generates any nontrivial lattice on the set o symbols or states?

Second question, probably better: Turing Machine which generates order on the set of its states I would like to ask ( if it is not terribly obviously wrong): Do Turing Machine generates ...
0
votes
0answers
378 views

Applications of the property of Kendall-Mann numbers

I am looking for an application of the Kendall-Mann sequence (KM) which uses the property $M(n+1)/M(n) = n - 1/2 + O(1/n)$ ($n \to \infty$) in science ( computer science ( sorting), physics, biology ...
27
votes
17answers
6k views

Computer Science for Mathematicians

This is a big-list community question, so I'm sorry in advance if it is deemed too soft but I haven't seen anything similar yet. I've seen computer scienctists post questions looking to learn things ...
5
votes
1answer
381 views

What is the pathwidth of the 3D-grid (mesh or lattice) with sidelength k?

This question is now also on http://cstheory.stackexchange.com/questions/4081/what-is-the-pathwidth-of-the-3d-grid-mesh-or-lattice-with-sidelength-k, where a discussion started, and one reference ...
0
votes
3answers
293 views

boolean functions and averaging / counting

Hey guys, I have a slightly imprecise question. I would like say something about a whole set of binary strings evaluated by a binary function by just looking at some type of average. The easiest ...
3
votes
0answers
303 views

Inversion density: Have you seen this concept?

Let n > 1 be an integer. Let A be an array, indexed from 1 to n, of n values A(i) coming from the finite set {0,1}. (More generally, the values can come from any totally ordered set, but I only need ...
31
votes
9answers
3k views

What is the shortest program for which halting is unknown?

In short, my question is: What is the shortest computer program for which it is not known whether or not the program halts? Of course, this depends on the description language; I also have the ...
11
votes
3answers
740 views

Alive dynamical system

Intuitively, one can say that a dynamical system is alive if one can build a universal Turing machine inside. So, Conway's Game of Life is alive and shift space should be dead. I fail to make this ...