62 citations · 130 across the 18 of their papers we have counts for
4 papers · 2 filters
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…
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…