Semantics-to-Syntax Analyses of Algorithms

Yuri Gurevich ()
Additional contact information
Yuri Gurevich: Microsoft Research

A chapter in Turing’s Revolution, 2015, pp 187-206 from Springer

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

Keywords: Abstract state machines; Algorithms; Analysis of algorithms; Church’s thesis; Computability; Concept of algorithms; Definition of algorithms; Human computers; Semantics-to-syntax analysis; Sequential algorithm; Turing’s thesis (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_7

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

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

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 ().