Back to search

Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, c2009

A new program for combinatory reduction and abstraction

Abstract

dc:description.abstract

Even though lambda calculus (λ-calculus) and combinatory logic (CL) appear to be equivalent, they are not. As yet we do not have a reduction in CL which corresponds to β-reduction in λ-calculus. There are three proposals but they all have few problems one of which is the lack of a complete characterization of CL-terms corresponding to λ-terms in β-normal form. Finding such a characterization for any of the three proposals appears to require a lot of examples which are tedious and time consuming to develop by hand. For this reason, a computer program to do reductions and abstractions of CL-terms would be useful. This thesis is about an attempt to write such a program. The program that we have does not yet work for the three proposals but it works for βη-strong reduction. Coding this program turned out to be much harder than anticipated. Dr. Robin Cockett developed a semantic translation which helped in coding the program but his semantic translation needs to be extended to all three proposals to obtain the program originally desired and that needs a lot of research.

Degree

thesis:*
Level thesis:degree_level
Masters
Grantor dc:publisher
Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, c2009
Year dc:date.issued
2009

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Deshpande, Sushant
  • University of Lethbridge. Faculty of Arts and Science
Advisor dc:contributor.supervisor
  • Seldin, Jonathan

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Identifier
hdl:10133/1296

Chain of custody

source
Harvested from
University of Lethbridge
Base URL
opus.uleth.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Deshpande, Sushant; University of Lethbridge. Faculty of Arts and Science. A new program for combinatory reduction and abstraction. Masters thesis, Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, c2009, 2009. https://hdl.handle.net/10133/1296