Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2015 | Book

Conceptual Confluence in 1936: Post and Turing Read chapter Read first chapter

Turing’s Revolution

The Impact of His Ideas about Computability

Editors: Giovanni Sommaruga, Thomas Strahm

Publisher: Springer International Publishing

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

This book provides an overview of the confluence of ideas in Turing’s era and work and examines the impact of his work on mathematical logic and theoretical computer science. It combines contributions by well-known scientists on the history and philosophy of computability theory as well as on generalised Turing computability. By looking at the roots and at the philosophical and technical influence of Turing’s work, it is possible to gather new perspectives and new research topics which might be considered as a continuation of Turing’s working ideas well into the 21st century.

Table of Contents

Frontmatter
Correction to: The Stored-Program Universal Computer: Did Zuse Anticipate Turing and von Neumann?
B. Jack Copeland, Giovanni Sommaruga

Turing and the History of Computability Theory

Frontmatter
Conceptual Confluence in 1936: Post and Turing
Abstract
In 1936, Post and Turing independently proposed two models of computation that are virtually identical. Turing refers back to these models in his (The word problem in semi-groups with cancellation. Ann. Math. 52, 491–505) and calls them “the logical computing machines introduced by Post and the author”. The virtual identity is not to be viewed as a surprising coincidence, but rather as a natural consequence of the way in which Post and Turing conceived of the steps in mechanical procedures on finite strings. To support our view of the underlying conceptual confluence, we discuss the two 1936 papers, but explore also Post’s work in the 1920s and Turing’s paper (Solvable and unsolvable problems. Sci. News 31, 7–23). In addition, we consider their overlapping mathematical work on the word-problem for semigroups (with cancellation) in Post’s (Recursive unsolvability of a problem of Thue. J. Symb. Log. 12, 1–11) and Turing’s (The word problem in semi-groups with cancellation. Ann. Math. 52, 491–505). We argue that the unity of their approach is of deep significance for the theory of computability.
Martin Davis, Wilfried Sieg
Algorithms: From Al-Khwarizmi to Turing and Beyond
Abstract
The foundational work of Alan Turing and contemporaries on computability marked a turning point in the development of mathematical sciences: It clarified in a rather absolute sense what is computable in the setting of symbolic computation, and it also opened the way to computer science where the use of algorithms and the discussion on their nature was enriched by many new facets. The present essay is an attempt to address both aspects: We review the historical development of the concept of algorithm up to Turing, emphasizing the essential role that logic played in this context, and we discuss the subsequent widening of understanding of “algorithm” and related “machines”, much in the spirit of Turing whose visions we see realized today.
Wolfgang Thomas

Open Access

The Stored-Program Universal Computer: Did Zuse Anticipate Turing and von Neumann?
Abstract
This chapter sets out the early history of the stored-program concept. The several distinct ‘onion skins’ making up the concept emerged slowly over a ten-year period, giving rise to a number of different programming paradigms. A notation is developed for describing different aspects of the stored-program concept. Theoretical contributions by Turing, Zuse, Eckert, Mauchly, and von Neumann are analysed, followed by a comparative study of the first practical implementations of stored-programming, at the Aberdeen Ballistic Research Laboratory in the US and the University Manchester in the UK. Turing’s concept of universality is also examined, and an assessment is provided of claims that various historic computers—including Babbage’s Analytical Engine, Flowers’ Colossus and Zuse’s Z3—were universal. The chapter begins with a discussion of the work of the great German pioneer of computing, Konrad Zuse.
B. Jack Copeland, Giovanni Sommaruga
PDF View full text

Generalizing Turing Computability Theory

Frontmatter
Theses for Computation and Recursion on Concrete and Abstract Structures
Abstract
The main aim of this article is to examine proposed theses for computation and recursion on concrete and abstract structures. What is generally referred to as Church’s Thesis or the Church-Turing Thesis (abbreviated CT here) must be restricted to concrete structures whose objects are finite symbolic configurations of one sort or another. Informal and principled arguments for CT on concrete structures are reviewed. Next, it is argued that proposed generalizations of notions of computation to abstract structures must be considered instead under the general notion of algorithm. However, there is no clear general thesis in sight for that comparable to CT, though there are certain wide classes of algorithms for which plausible theses can be stated. The article concludes with a proposed thesis RT for recursion on abstract structures.
Solomon Feferman
Generalizing Computability Theory to Abstract Algebras
Abstract
We present a survey of our work over the last four decades on generalizations of computability theory to many-sorted algebras. The following topics are discussed, among others: (1) abstract v concrete models of computation for such algebras; (2) computability and continuity, and the use of many-sorted topological partial algebras, containing the reals; (3) comparisons between various equivalent and distinct models of computability; (4) generalized Church-Turing theses.
J. V. Tucker, J. I. Zucker
Discrete Transfinite Computation
Abstract
We describe various computational models based initially, but not exclusively, on that of the Turing machine, that are generalized to allow for transfinitely many computational steps. Variants of such machines are considered that have longer tapes than the standard model, or that work on ordinals rather than numbers. We outline the connections between such models and the older theories of recursion in higher types, generalized recursion theory, and recursion on ordinals such as α-recursion. We conclude that, in particular, polynomial time computation on ω-strings is well modelled by several convergent conceptions.
P. D. Welch
Semantics-to-Syntax Analyses of Algorithms
Abstract
Alan Turing pioneered semantics-to-syntax analysis of algorithms. It is a kind of analysis where you start with a large semantically defined species of algorithms, and you finish up with a syntactic artifact, typically a computation model, that characterizes the species. The task of analyzing a large species of algorithms seems daunting if not impossible. As in quicksand, one needs a rescue point, a fulcrum. In computation analysis, a fulcrum is a particular viewpoint on computation that clarifies and simplifies things to the point that analysis become possible. We review from that point of view Turing’s analysis of human-executable computation, Kolmogorov’s analysis of sequential bit-level computation, Gandy’s analysis of a species of machine computation, and our own analysis of sequential computation.
Yuri Gurevich
The Information Content of Typical Reals
Abstract
The degrees of unsolvability provide a way to study the continuum in algorithmic terms. Measure and category, on the other hand, provide notions of size for subsets of the continuum, giving rise to corresponding notions of “typicality” for real numbers. We give an overview of the order-theoretic properties of the degrees of typical reals, presenting old and recent results, and pointing to a number of open problems for future research on this topic.
George Barmpalias, Andy Lewis-Pye
Proof Theoretic Analysis by Iterated Reflection
Abstract
Progressions of iterated reflection principles can be used as a tool for the ordinal analysis of formal systems. Moreover, they provide a uniform definition of a proof-theoretic ordinal for any arithmetical complexity \(\Pi _{n}^{0}\). We discuss various notions of proof-theoretic ordinals and compare the information obtained by means of the reflection principles with the results obtained by the more usual proof-theoretic techniques. In some cases we obtain sharper results, e.g., we define proof-theoretic ordinals relevant to logical complexity \(\Pi _{1}^{0}\). We provide a more general version of the fine structure relationships for iterated reflection principles (due to Ulf Schmerl). This allows us, in a uniform manner, to analyze main fragments of arithmetic axiomatized by restricted forms of induction, including \(I\Sigma _{n}\), \(I\Sigma _{n}^{-}\), \(I\Pi _{n}^{-}\) and their combinations. We also obtain new conservation results relating the hierarchies of uniform and local reflection principles. In particular, we show that (for a sufficiently broad class of theories T) the uniform \(\Sigma _{1}\)-reflection principle for T is \(\Sigma _{2}\)-conservative over the corresponding local reflection principle. This bears some corollaries on the hierarchies of restricted induction schemata in arithmetic and provides a key tool for our generalization of Schmerl’s theorem.
L. D. Beklemishev

Philosophical Reflections

Frontmatter
Alan Turing and the Foundation of Computer Science
Abstract
The goal of this article is to explain to non-specialists what computer science is about and what is the contribution of Alan Turing to general science. To do this well-understandable for everybody, we introduce mathematics as a language describing objects and relations between objects in an exact and unambiguously interpretable way, and as a language of correct, well-verifiable reasoning. Starting with the dream of Gottfried Wilhelm Leibniz, who wanted to automatize some part of the work of mathematicians including also reasoning, we finish with Alan Turing’s exact axiomatic definition of the limits of automation of the intellectual work, i.e., with the birth date of computer science.
Juraj Hromkovič
Proving Things About the Informal
Abstract
There has been a bit of discussion, of late, as to whether Church’s thesis is subject to proof. The purpose of this article is to help clarify the issue by discussing just what it is to be a proof of something, and the relationship of the intuitive notion of proof to its more formal explications. A central item on the agenda is the epistemological role of proofs.
Stewart Shapiro
Why Turing’s Thesis Is Not a Thesis
Abstract
In 1936 Alan Turing showed that any effectively calculable function is computable by a Turing machine. Scholars at the time, such as Kurt Gödel and Alonzo Church, regarded this as a convincing demonstration of this claim, not as a mere hypothesis in need of continual reexamination and justification. In 1988 Robin Gandy said that Turing’s analysis “proves a theorem.” However, Stephen C. Kleene introduced the term “thesis” in 1943 and in his book in 1952. Since then it has been known as “Turing’s Thesis.” Here we discuss whether it is a thesis, a definition, or a theorem. This is important to determine what Turing actually accomplished.
Robert Irving Soare
Incomputability Emergent, and Higher Type Computation
Abstract
Typing of information played an historical role in bringing consistency to formulations of set theory and to the foundations of mathematics. Underlying this was the augmentation of language and logical structure with a respect for constructive principles and the corresponding infrastructure of an informational universe. This has important consequences for how we view the computational character of science, the humanities and human creativity. The aim of this article is to make more explicit the anticipations and intuitions of early pioneers such as Alan Turing in informing and making relevant the computability theoretic underpinnings of today’s understanding of this. We hope to make clearer the relationship between the typing of information—a framework basic to all of Turing’s work—and the computability theoretic character of emergent structure in the real universe. The informational terrain arising is one with comprehensive computational structure, but with theoretical boundaries to those areas accessible to effective exploration in an everyday setting.
S. Barry Cooper
Metadata
Title
Turing’s Revolution
Editors
Giovanni Sommaruga
Thomas Strahm
Copyright Year
2015
Publisher
Springer International Publishing
Electronic ISBN
978-3-319-22156-4
Print ISBN
978-3-319-22155-7
DOI
https://doi.org/10.1007/978-3-319-22156-4

Premium Partner

    Image Credits