Theses for Computation and Recursion on Concrete and Abstract Structures

Solomon Feferman ()
Additional contact information
Solomon Feferman: Stanford University, Department of Mathematics

A chapter in Turing’s Revolution, 2015, pp 105-126 from Springer

Abstract: 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.

Keywords: Church's Thesis; Church-Turing Thesis; Computation; Algorithm; Recursion; Concrete structures; Abstract structures (search for similar items in EconPapers)
Date: 2015
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-319-22156-4_4

Ordering information: This item can be ordered from
http://www.springer.com/9783319221564

DOI: 10.1007/978-3-319-22156-4_4

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().