Skip to main content
SpringerLink
Log in
Book cover

Computation, Physics and Beyond

International Workshop on Theoretical Computer Science, WTCS 2012, Dedicated to Cristian S. Calude on the Occasion of His 60th Birthday, Auckland, New Zealand, February 21-24, 2012, Revised Selected and Invited Papers

  • Book
  • © 2012

Overview

Editors:
  1. Michael J. Dinneen

    1. Department of Computer Science, University of Auckland, Auckland, New Zealand

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Bakhadyr Khoussainov

    1. Department of Computer Science, University of Auckland, Auckland, New Zealand

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. André Nies

    1. Department of Computer Science, University of Auckland, Auckland, New Zealand

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • State-of-the-art research
  • Unique visibility
  • Includes invited lectures by eminent researchers in theoretical computer science

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 7160)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: WTCS 2012.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (32 chapters)

  1. Front Matter

    Download chapter PDF

  2. Life Story

    1. The Art of Reaching the Age of Sixty

      • Solomon Marcus
      Pages 1-19

    2. Calude as Father of One of the Computer Science Journals

      • Hermann Maurer
      Pages 20-30

  3. Complexity, Computability and Randomness

    1. Random Semicomputable Reals Revisited

      • Laurent Bienvenu, Alexander Shen
      Pages 31-45

    2. Constructing the Infimum of Two Projections

      • Douglas S. Bridges, Luminita S. Vîţă
      Pages 46-58

    3. Bounded Randomness

      • Paul Brodhead, Rod Downey, Keng Meng Ng
      Pages 59-70

    4. A Note on Blum Static Complexity Measures

      • Cezar Câmpeanu
      Pages 71-80

    5. A Program-Size Complexity Measure for Mathematical Problems and Conjectures

      • Michael J. Dinneen
      Pages 81-93

    6. On Degrees of Randomness and Genetic Randomness

      • Monica Dumitrescu
      Pages 94-104

    7. Hartmanis-Stearns Conjecture on Real Time and Transcendence

      • Rūsiņš Freivalds
      Pages 105-119

    8. Learning Families of Closed Sets in Matroids

      • Ziyuan Gao, Frank Stephan, Guohua Wu, Akihiro Yamamoto
      Pages 120-139

    9. Invariance and Universality of Complexity

      • Helmut Jürgensen
      Pages 140-158

    10. Demuth’s Path to Randomness

      • Antonín Kučera, André Nies
      Pages 159-173

    11. A Computability Challenge: Asymptotic Bounds for Error-Correcting Codes

      • Yuri I. Manin
      Pages 174-182

    12. Some Transfinite Generalisations of Gödel’s Incompleteness Theorem

      • Jacques Patarin
      Pages 183-193

    13. On Oscillation-Free Chaitin h-Random Sequences

      • Ludwig Staiger
      Pages 194-202

    14. Phase Transition between Unidirectionality and Bidirectionality

      • Kohtaro Tadaki
      Pages 203-223

    15. Computer Runtimes and the Length of Proofs

      • Hector Zenil
      Pages 224-240

    16. Symmetry of Information: A Closer Look

      • Marius Zimand
      Pages 241-246

  4. Physics, Philosophy and Computation

    1. How Much Information Can There Be in a Real Number?

      • Gregory Chaitin
      Pages 247-251
Back to top

Keywords

About this book

This Festschrift volume has been published in honor of Cristian Calude on the occasion of his 60th birthday and contains contributions from invited speakers and regular papers presented at the International Workshop on Theoretical Computer Science, WTCS 2012, held in Auckland, New Zealand, in February 2012.

Cristian Calude has made a significant contribution to research in computer science theory. Along with early work by Chaitin, Kučera, Kurtz, Solovay, and Terwijn his papers published in the mid-1990s jointly with Khoussainov, Hertling, and Wang laid the foundation for the development of modern theory of algorithmic randomness. His work was essential for establishing the leading role of New Zealand in this area.

The research interests of Cristian Calude are reflected in the topics covered by the 32 papers included in this book, namely: algorithmic information theory, algorithms, automata and formal languages, computing and natural sciences, computability and applications, logic and applications, philosophy of computation, physics and computation, and unconventional models of computation. They have been organized into four parts. The first part consists of papers discussing his life achievements. This is followed by papers in the three general areas of complexity, computability, and randomness; physics, philosophy (and logic), and computation; and algorithms, automata, and formal models (including unconventional computing).

Editors and Affiliations

  • Department of Computer Science, University of Auckland, Auckland, New Zealand

    Michael J. Dinneen, Bakhadyr Khoussainov, André Nies

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation