62 citations · 63 across the 4 of their papers we have counts for
9 papers · 1 filter
Meaningful Information
Paul Vitanyi
The information in an individual finite object (like a binary string) is commonly measured by its Kolmogorov complexity. One can divide that information into two parts: the informa…
Kolmogorov Random Graphs and the Incompressibility Method
Harry Buhrman, Ming Li, John Tromp +1
We investigate topological, combinatorial, statistical, and enumeration properties of finite graphs with high Kolmogorov complexity (almost all graphs) using the novel incompressib…
Tolstoy's Mathematics in "War and Peace"
Paul Vitanyi
The nineteenth century Russian author Leo Tolstoy based his egalitarian views on sociology and history on mathematical and probabilistic views, and he also proposed a mathematical…
A New Approach to Formal Language Theory by Kolmogorov Complexity
Ming Li, Paul Vitanyi
We present a new approach to formal language theory using Kolmogorov complexity. The main results presented here are an alternative for pumping lemma(s), a new characterization for…
Two heads are better than two tapes
Tao Jiang, Joel Seiferas, Paul Vitanyi
We show that a Turing machine with two single-head one-dimensional tapes cannot recognize the set {x2x'| x \in {0,1}^* and x' is a prefix of x} in real time, although it can do so…
Counting is Easy
Joel Seiferas, Paul Vitanyi
For any fixed , a remarkably simple single-tape Turing machine can simulate independent counters in real time. Informally, a counter is a storage unit that maintains a singl…