What a treat! Get Apress Access for just $149 Subscribe now >>

New Computational Paradigms

Changing Conceptions of What is Computable

Editors: Cooper, S. Barry, Löwe, Benedikt, Sorbi, Andrea (Eds.)

  • Explores new developments in the theory and practice of computation from a mathematical and predominantly logical perspective
  • Covers topics ranging from classical computability to complexity, biocomputing and quantum computing
  • Written not only for specialists, but also with a broader audience in mind
  • Contributors are all prominent scholars and worldwide known specialists
see more benefits

Buy this book

eBook $149.00
price for USA (gross)
  • ISBN 978-0-387-68546-5
  • Digitally watermarked, DRM-free
  • Included format: PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Hardcover $199.00
price for USA
valid through November 5, 2017
  • ISBN 978-0-387-36033-1
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Softcover $199.00
price for USA
valid through November 5, 2017
  • ISBN 978-1-4419-2263-2
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
About this book

In recent years, classical computability has expanded beyond its original scope to address issues related to computability and complexity in algebra, analysis, and physics. The deep interconnection between "computation" and "proof" has originated much of the most significant work in constructive mathematics and mathematical logic of the last 70 years. Moreover, the increasingly compelling necessity to deal with computability in the real world (such as computing on continuous data, biological computing, and physical models) has brought focus to new paradigms of computation that are based on biological and physical models. These models address questions of efficiency in a radically new way and even threaten to move the so-called Turing barrier, i.e. the line between the decidable and the un-decidable.

This book examines new developments in the theory and practice of computation from a mathematical perspective, with topics ranging from classical computability to complexity, from biocomputing to quantum computing. The book opens with an introduction by Andrew Hodges, the Turing biographer, who analyzes the pioneering work that anticipated recent developments concerning computation’s allegedly new paradigms. The remaining material covers traditional topics in computability theory such as relative computability, theory of numberings, and domain theory, in addition to topics on the relationships between proof theory, computability, and complexity theory. New paradigms of computation arising from biology and quantum physics are also discussed, as well as the computability of the real numbers and its related issues.

This book is suitable for researchers and graduate students in mathematics, philosophy, and computer science with a special interest in logic and foundational issues. Most useful to graduate students are the survey papers on computable analysis and biological computing. Logicians and theoretical physicists will also benefit from this book.

Reviews

From the reviews:

“It is addressed to researcher and graduate students … . All contributions to the book have been rigorously refereed, and the standards with respect to layout, references … are high. … This is a piece of excellent pedagogical work. The paper is hereby recommended. … I personally find very readable and informative. … I enjoyed reading these papers, and I assume they are all right when we take them for what they are … .”­­­ (Lars Kristiansen, Studia Logica, Vol. 97, 2011)

Table of contents (8 chapters)

  • Computation Paradigms in Light of Hilbert's Tenth Problem

    Yuri Matiyasevich

    Pages 59-85

  • Elementary Algorithms and Their Implementations

    Yiannis N. Moschovakis, Vasilis Paschalis

    Pages 87-118

  • Church Without Dogma: Axioms for Computability

    Wilfried Sieg

    Pages 139-152

  • Effective Fractal Dimension in Algorithmic Information Theory

    Elvira Mayordomo

    Pages 259-285

  • Metamathematical Properties of Intuitionistic Set Theories with Choice Principles

    Michael Rathjen

    Pages 287-312

Buy this book

eBook $149.00
price for USA (gross)
  • ISBN 978-0-387-68546-5
  • Digitally watermarked, DRM-free
  • Included format: PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Hardcover $199.00
price for USA
valid through November 5, 2017
  • ISBN 978-0-387-36033-1
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Softcover $199.00
price for USA
valid through November 5, 2017
  • ISBN 978-1-4419-2263-2
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.

Services for this book

Loading...

Bibliographic Information

Bibliographic Information
Book Title
New Computational Paradigms
Book Subtitle
Changing Conceptions of What is Computable
Editors
  • S. Barry Cooper
  • Benedikt Löwe
  • Andrea Sorbi
Copyright
2008
Publisher
Springer-Verlag New York
Copyright Holder
Springer-Verlag New York
eBook ISBN
978-0-387-68546-5
DOI
10.1007/978-0-387-68546-5
Hardcover ISBN
978-0-387-36033-1
Softcover ISBN
978-1-4419-2263-2
Edition Number
1
Number of Pages
XIV, 560
Topics