Computer Science – Logic in Computer Science
Scientific paper
2010-10-13
Lecture notes in computer science LNCS 6300 (2010) 00
Computer Science
Logic in Computer Science
37 pages
Scientific paper
We show that lambda calculus is a computation model which can step by step simulate any sequential deterministic algorithm for any computable function over integers or words or any datatype. More formally, given an algorithm above a family of computable functions (taken as primitive tools, i.e., kind of oracle functions for the algorithm), for every constant K big enough, each computation step of the algorithm can be simulated by exactly K successive reductions in a natural extension of lambda calculus with constants for functions in the above considered family. The proof is based on a fixed point technique in lambda calculus and on Gurevich sequential Thesis which allows to identify sequential deterministic algorithms with Abstract State Machines. This extends to algorithms for partial computable functions in such a way that finite computations ending with exceptions are associated to finite reductions leading to terms with a particular very simple feature.
Ferbus-Zanda Marie
Grigorieff Serge
No associations
LandOfFree
ASMs and Operational Algorithmic Completeness of Lambda Calculus does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with ASMs and Operational Algorithmic Completeness of Lambda Calculus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and ASMs and Operational Algorithmic Completeness of Lambda Calculus will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-226262