Computability theory: structure or algorithms

doi:10.1017/9781316755983.010

Computability theory: structure or algorithms

from PART II - LOGIC AND COMPUTATION

Published online by Cambridge University Press: 31 March 2017

Edited by

Richard Sommer and

Wilfried Sieg: Affiliation:
Carnegie Mellon University, Pennsylvania
Richard Sommer: Affiliation:
Stanford University, California
Carolyn Talcott: Affiliation:
Stanford University, California

Book contents

Get access

Summary

In the paper Turing's “oracle”: From absolute to relative computability - and back S.Feferman discusses some major trends in recent work on degrees of unsolvability, theories of recursive functionals and generalized recursion theory and notes how “marching in under the banner of degree theory, these strands were to some extent woven together by the recursion theorists, but the trend has been to pull the subject of effective computability even farther away from questions of actual computation.” (Feferman [1992a])

Feferman had expressed similar concerns in a paper from 1977 Inductive schemata and recursively continuous functionals (Feferman [1977]), and both he and Y. Moschovakis have since pursued a program of how to use “abstract recursion theory as a foundation for a theory of algorithms” (to quote the title of a paper by Moschovakis from 1984). Some key references in the development of this program are Feferman [1991], [1992b], [1996], and Moschovakis [1984], [1989], [1997]. We particularily recommend Feferman [1992b] A new approach to abstract data types, I, Informal development, for a clear conceptual presentation of the issues involved.

I had commented on these issues in the introductory part of the book General Recursion Theory, (Fenstad [1980]). The Oslo group had in the 1970's been active in many parts of generalized recursion theory, such as computation in higher types, inductive definability, continuous functionals, set recursion and other relationships between set theory and recursion theory. We attempted a unified analysis through the axiomatic notion of a computation theory. Our logic group shared the common “world view” of the recursion theory community. We were “inwards bound”, concentrating above all on structure and generality.

It would, however, be wrong to claim that recursion theory in the late 1970'swas all structure and that it paid no attention to questions of algorithmic content. But it was true that our brand of generalized recursion theory was an activity almost exclusively pursued by the logic community. We were running the risk, and this may even be the subtext of Feferman's remarks in 1992, that the inward bound travel toward ever more intricate structural concerns would lead to an academic profession largely irrelevant to computational praxis.

Type: Chapter
Information: Reflections on the Foundations of Mathematics
Essays in Honor of Solomon Feferman
, pp. 182 - 207

DOI: https://doi.org/10.1017/9781316755983.010 [Opens in a new window]

Publisher: Cambridge University Press

Print publication year: 2002

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

V., Brattka, 1999, Recursive and computable operations over topological structures, Ph.D. Thesis, FernUniversität Hagen.

L., Blum, F., Cucker, M., Shub and S., Smale, 1998, Complexity and real computations, Springer-Verlag, New York

J., Dahl, B., Myrhaug and K., Nygaard, 1970, Common Base Language, Norsk Regnesentral, Oslo.

F. R., Drake and S., S.Wainer, 1980, Recursion Theory: its generalizations and applications, Cambridge University Press, Cambridge.

E., Engeler, 1968, Formal languages: Automata and structures, Markham PublicationsCompany.

M. H., Escardo, 1996, PCF extended with real numbers, Theoretical Computer Science, 162 (1).Google Scholar

M. H., Escardo, 1997, PCF extended with real numbers: a domain-theoretic approach to higher-order exact real number computation, Ph.D. Thesis, University of London, Imperial College.

S., Feferman, 1977, Inductive schemata and recursively continuous functionals, in Gandy and Hyland 1977.

S., Feferman, 1991,A new approach to abstract data types,II. Computations on ADTs as ordinary computations, in Computer Science Logic, Lecture Notes in Computer science, 626, Springer-Verlag.

S., Feferman, 1992a, Turing's oracle: From absolute computability - and back, in The Space of Mathematics (ed. J., Echeverria et al), Walter de Gruyter, Berlin.

S., Feferman, 1992b, A new approach to abstract data types I. Informal development, Mathematical Structures in Computer Science, 2.Google Scholar

S., Feferman, 1996, Computations on abstract data types. The extensional approach with an application to streams, Annals of Pure and Applied Logic, 81.Google Scholar

J. E., Fenstad, 1980, General Recursion Theory, Springer-Verlag, Berlin-Heidelberg- New York, 1980.

J. E., Fenstad, R.O., Gandy and G. E., Sacks, 1978, Generalized recursion theory II, North-Holland, Amsterdam.

J. E., Fenstad and P.G., Hinman, 1974, Generalized Recursion Theory, North- Holland, Amsterdam.

H., Friedman, 1971a, Axiomatic recursive function theory, in Gandy and Yates 1971.

H., Friedman, 1971b, Algorithmic procedures, generalized Turing algorithms, and elementary recursion theory, in Gandy and Yates 1971.

R.O., Gandy, 1967,General recursive functionals of finite type and hierarchies of functions, Ann.Fac. Sci. Univ. Clermont-Ferrand, 35.

R.O., Gandy, 1988, The confluence of ideas in 1936, in The Universal Turing Machine. A Half-Century Survey (ed. R., Herken), Springer-Verlag, Wien-New York.

R.O., Gandy and J. E. M., Hyland, 1977,Logic Colloquium –76, North-Holland, Amsterdam.

R.O., Gandy and C. M., E.Yates, 1971,Logic Colloquium –69, North-Holland, Amsterdam.

J. A., Goguen, J.W., Thatcher, E.G., Wagner and J., B.Wright, 1975, An initial algebra approach to the specification, correctness and implementation of abstract data types, in Current Trends in Programming Methodology: IV Data structures (ed. R., T.Yeh), Prentice Hall, London.

A., Grzegorczyk, 1955, Computable functions, Fundamenta Mathematicae, 42.Google Scholar

A., Grzegorczyk, 1957, On the definition of computable real continuous function, Fundamenta Mathematicae, 44.Google Scholar

M., Gromov, 1998, Possible trends in mathematics in the coming decades, Notices AMS, 45.Google Scholar

G.T., Herman and S.D., Isard, 1970, Computability over arbitrary fields, Journal of the London Mathmatical Society, 2.Google Scholar

S.C., Kleene, 1959, Recursive functionals and quantifiers of finite types, I, Transactions of the American Mathematical Society, 91.Google Scholar

S.C., Kleene, 1981, Origins of recursive function theory, Annals of the History of Computing, 3.Google Scholar

G., Kreisel. 1971, Some reasons for generalizing recursion theory, in Gandy and Yates, 1971.

G., Kreisel and G.E., Sacks, 1965,Metarecursive sets, The Journal of Symbolic Logic, 30.Google Scholar

D., Lacombe, 1955, Extension de la notion de fonction recursive aux fonctions d'une ou plusieurs variable reelles, C. R.Acad. Sci. Paris, 240.

J., Moldestad, 1977, Computations in Higher Types, Lecture Notes in Mathematics, 574, Springer-Verlag, Berlin-Heidelberg-New York.

J., Moldestad, V., Stoltenberg-Hansen and J.V., Tucker, 1980a, Finite algorithmic prodcedures and inductive definability,Mathematica Scandinavia, 46.Google Scholar

J., Moldestad, V., Stoltenberg-Hansen and J.V., Tucker, 1980b, Finite algorithmic procedures and computation theories,Mathematica Scandinavia, 46.Google Scholar

Y.N., Moschovakis 1969, Abstract first-order computability, I, II, Transactions of the American Mathematical Society, 138.Google Scholar

Y.N., Moschovakis, 1971, Axioms for computation theories - first draft, inGandy and Yates 1971.

Y.N., Moschovakis, 1984, Abstract recursion as a foundation for the theory of algorithms, Computation and Proof Theory, Lecture Notes inMathematics, 1104, Springer-Verlag, Berlin-Heidelberg-New York.

Y.N., Moschovakis, 1989, The formal language of recursion, The Journal of Symbolic Logic, 54.

Y.N., Moschovakis, 1997, The logic of functional recursion, in Logic and Scientific Methods (ed M. L., Dalla Chiara et al), Kluwer Academic Publishers, Dordrecht.

D., Normann, 1978, Set recursion, in Fenstad, Gandy and Sacks 1978.

R.A., Platek, 1966, Foundation of recursion theory, Ph.D. Thesis, Stanford University.

G., Plotkin, 1977, LCF considered as a programming language, Theoretical Computer Science, 5 (1).Google Scholar

M., B. Pour-El and J.C., Caldwell, 1975, On a simple definition of computable function of a real variable with applications to functions of a complex variable, Zeitschr. f. math. Logik und Grundl. der Mathematik, 21.Google Scholar

M., B. Pour-El and J. I., Richards, 1989, Computability in Analysis and Physics, Springer-Verlag, New York-Heidelberg.

G.E., Sacks, 1990, HigherRecursion Theory, Springer-Verlag, Berlin-Heidelberg- New York.

J.C., Shepherdson, 1975,Computations over abstract structures: serial and parallel procedures and Friedman's effective definitional schemes, Logic Colloquium ' 73, North-Holland, Amsterdam.

J.C., Shepherdson. 1976, On the definition of a computable function of a real variable, Zeitschr. f. math. Logik und Grundl. der Mathematik, 22.Google Scholar

J.C., Shepherdson, 1988, Mechanisms for computing over arbitrary structures, in The UniversalTuring Machine. AHalf-Century Survey (ed. R., Haken), Springer- Verlag,Wien-New York.

J.C., Shepherdson and H. E., Sturgis, 1963, Computability of recursive functions, J. Ass. for Computing Machinery, 10.Google Scholar

S., Smale, 1998, Mathematical problems for the next century, TheMathematical Intelligencer, 20.Google Scholar

R.I., Soare, 1996, Computability and recursion, The Bulletin of Symbolic Logic, 2.Google Scholar

K.J., Stewart, 1999, Concrete and abstract model of computation over metric algebras, Ph.D. Thesis, University of Wales, Swansea.

V., Stoltenberg-Hansen and J.V., Tucker, 1999, Concrete models for computation for topological algebras, Theoretical Computer Science, 219.Google Scholar

H.R., Strong, 1968, Algebraically generalized recursive function theory, IBM J.Res. Devel., 12.Google Scholar

J.V., Tucker, 1980,Computing in algebraic systems, in Drake and Wainer 1980.

J. V., Tucker and J. I., Zucker, 1998, Computable functions and semicomputable sets on many-sorted algebras, in Handbook of Logic in Computer science, vol 5.

J.V., Tucker and J. I., Zucker, 1999, Computation by While programs on topological partial algebras, Theoretical Computer Science, 219.Google Scholar

J.V., Tucker and J. I., Zucker, in preparation, Abstract versus concrete models of computation on metric partial algebras.

J., Van Leeuwen (ed), 1990, Handbook of Theoretical Computer Science, Vol A, Algorithms and Complexity, Elsevier, Amsterdam.

J., Van Leeuwen (ed), 1990, Handbook of Theoretical Computer Science, Vol B, Formal Models and Semantics, Elsevier, Amsterdam.

E.G., Wagner, 1969, Uniform reflexive structures, Trans.AMS, 144.Google Scholar

M., Wirsing, 1990, Algebraic specification, in J.Van Leeuwen 1990.Google Scholar

Book contents

Computability theory: structure or algorithms

Summary

Access options

References

Save book to Kindle

Save book to Dropbox

Save book to Google Drive