Skip Navigation


The Computer Journal Advance Access originally published online on August 11, 2005
The Computer Journal 2005 48(6):642-645; doi:10.1093/comjnl/bxh124
This Article
Right arrow Full Text
Right arrow Full Text (PDF)
Right arrow Figure 2 - colour version
Right arrow All Versions of this Article:
48/6/642    most recent
bxh124v1
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Levin, L. A.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author 2005. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Aperiodic Tilings: Breaking Translational Symmetry

Leonid A. Levin

Boston University, Department of Computer Science, 111 Cummington Street, Boston, MA 02215, USA

Classical results on aperiodic tilings are rather complicated and not widely understood. In the present article, an alternative approach to these results is discussed in the hope of providing additional intuition, not apparent in classical works.

This annual University of London lecture celebrates the life and work of Andrei Nikolaevich Kolmogorov, one of the greatest mathematical and scientific minds of the last century. The lecture addresses current issues arising from the impact of Kolmogorov's work in the fields of mathematical and computer sciences.

Each Kolmogorov Lecture is given by one of the leading figures in their field, who is presented with a medal in recognition of their own contribution to science. The speaker at the Second Annual Kolmogorov Lecture, held on February 24, 2004, was Professor Leonid Levin of Boston University. He presented a lecture entitled ‘Randomness and Non-determinism’:

In the decades since fundamental questions like P = ?NP have been raised, we have not come much closer to answering them. Yet, we did learn one obscure but essential hint: a strange pattern of relationships between non-determinism and randomness—another major deviation from deterministic computations.

I will give illustrations of these ideas: some simple, some powerful and ingenious to which many authors contributed. One example, foreshadowed by Andrei Kolmogorov, is the fundamental relationship between computer-generated randomness and hard non-deterministic problems (one-way functions). A converse example is a Monte Carlo method for instant verification of proofs of any theorems or computations—a quite general nondeterministic task.


Professor Levin awarded the Kolmogorov Medal (From left) Professor Norman Gowar, Professor Leonid Levin and Professor Alex Gammerman.

Professor Levin, one of the world's foremost researchers in the field of Kolmogorov Complexity, works in the field of mathematical probability and the theory of computation, particularly with respect to randomness and complexity in computing. First introduced to Kolmogorov at the age of 15 during a school visit, he was later taught by Kolmogorov at Moscow University and was advised by him for his doctoral thesis.

Randomness was a major topic of the Kolmogorov Lecture as well as a great passion of Kolmogorov himself. One of the remarkable effects of randomness is breaking the symmetries inherent in many natural and artificial phenomena. The following article supplements the Lecture with a look at some other (non-deterministic) mechanisms of symmetry breaking.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.