Skip to main content
SpringerLink
Log in
SpringerLink
Log in

Computability and Models

Perspectives East and West

  • Book
  • © 2003

Overview

Authors:
  1. S. Barry Cooper

    1. University of Leeds, Leeds, UK

    View author publications

    You can also search for this author in PubMed   Google Scholar

  2. Sergey S. Goncharov

    1. Novosibirsk State University, Novosibirsk, Russia

    View author publications

    You can also search for this author in PubMed   Google Scholar

  • Variety of articles, exploring models, and computability in a modern and classic sense
  • Contributors are internationally known experts in their fields
  • East meets west to discuss recursive model theory

Part of the book series: University Series in Mathematics (USMA)

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 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book USD 109.99
Price excludes VAT (USA)
  • Durable hardcover 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 (15 chapters)

  1. Front Matter

    Pages i-xix
    Download chapter PDF

  2. Truth-Table Complete Computably Enumerable Sets

    • Marat M. Arslanov
    Pages 1-10

  3. Completeness and Universality of Arithmetical Numberings

    • Serikzhan Badaev, Sergey Goncharov, Andrea Sorbi
    Pages 11-44

  4. Algebraic Properties of Rogers Semilattices of Arithmetical Numberings

    • Serikzhan Badaev, Sergey Goncharov, Sergey Podzorov, Andrea Sorbi
    Pages 45-77

  5. Isomorphism Types and Theories of Rogers Semilattices of Arithmetical Numberings

    • Serikzhan Badaev, Sergey Goncharov, Andrea Sorbi
    Pages 79-91

  6. Computability over Topological Structures

    • Vasco Brattka
    Pages 93-136

  7. Incomputability in Nature

    • S. Barry Cooper, Piergiorgio Odifreddi
    Pages 137-160

  8. Gems in the Field of Bounded Queries

    • William Gasarch
    Pages 161-195

  9. Finite End Intervals in Definable Quotients of ε

    • Eberhard Herrmann
    Pages 197-214

  10. A Tour of Robust Learning

    • Sanjay Jain, Frank Stephan
    Pages 215-247

  11. On Primitive Recursive Permutations

    • Iskander Kalimullin
    Pages 249-258

  12. On Self-Embeddings of Computable Linear Orders

    • Steffen Lempp, Andrei S. Morozov, Charles F. D. McCoy, D. Reed Solomon
    Pages 259-265

  13. Definable Relations on the Computably Enumerable Degrees

    • Angsheng Li
    Pages 267-288

  14. Quasi-Degrees of Recursively Enumerable Sets

    • Roland Sh. Omanadze
    Pages 289-319

  15. Positive Structures

    • Victor Selivanov
    Pages 321-350

  16. Local Properties of the Non-Total Enumeration Degrees

    • Boris Solon
    Pages 351-370

  17. Back Matter

    Pages 371-375
    Download chapter PDF
Back to top

Keywords

About this book

Science involves descriptions of the world we live in. It also depends on nature exhibiting what we can best describe as a high aLgorithmic content. The theme running through this collection of papers is that of the interaction between descriptions, in the form of formal theories, and the algorithmic content of what is described, namely of the modeLs of those theories. This appears most explicitly here in a number of valuable, and substantial, contributions to what has until recently been known as 'recursive model theory' - an area in which researchers from the former Soviet Union (in particular Novosibirsk) have been pre-eminent. There are also articles concerned with the computability of aspects of familiar mathematical structures, and - a return to the sort of basic underlying questions considered by Alan Turing in the early days of the subject - an article giving a new perspective on computability in the real world. And, of course, there are also articles concerned with the classical theory of computability, including the first widely available survey of work on quasi-reducibility. The contributors, all internationally recognised experts in their fields, have been associated with the three-year INTAS-RFBR Research Project "Com­ putability and Models" (Project No. 972-139), and most have participated in one or more of the various international workshops (in Novosibirsk, Heidelberg and Almaty) and otherresearch activities of the network.

Authors and Affiliations

  • University of Leeds, Leeds, UK

    S. Barry Cooper

  • Novosibirsk State University, Novosibirsk, Russia

    Sergey S. Goncharov

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation