# Tagged Questions

**8**

votes

**2**answers

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

**1**answer

513 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

**1**answer

191 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

**1**answer

387 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

**1**answer

320 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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**17**answers

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

**1**answer

385 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

**3**answers

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

**0**answers

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 ...

**32**

votes

**9**answers

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

**3**answers

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 ...