[an error occurred while processing this directive] An error occured whilst processing this directive

Notions of Computability for General Datatypes

Funding Body: EPSRC

Grant value 158,403 pounds

The Edinburgh Team

GRANT HOLDERS:: Prof Mike Fourman, Prof Gordon Plotkin
OTHER PARTICIPANTS:: Dr John Longley

Objectives

Investigate new notions of computability for a wide variety of datatypes, higher-order types, and abstract types.
Prototype a programming language based on these new notions of computability.
Test the scope and usefulness of these notions by focusing on specific application areas.

Summary

Church's thesis fails at higher types, in the sense that there are competing, incompatible notions of higher-type computability. The proposed research will investigate classes of computable functions for a range of datatypes, including finite types over the natural numbers, recursive types, abstract types and object classes. It will also consider the more general question of what constitutes an "effective datatype". In addition to a theoretical analysis, we will investigate the practical applicability of notions of computability. We will do this mainly by via prototype implementations of simple programming languages based on these notions. This will allow us to investigate issues of computational feasibility and efficiency. An error occured whilst processing this directive