A Swiss Pocket Knife for Computability
This research is about operational- and complexity-oriented aspects of classical foundations of computability theory. The approach is to re-examine some classical theorems and constructions, but with new criteria for success that are natural from a programming language perspective. Three cornerstone...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2013-09-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1309.5128v1 |
| _version_ | 1811312714167877632 |
|---|---|
| author | Neil D. Jones |
| author_facet | Neil D. Jones |
| author_sort | Neil D. Jones |
| collection | DOAJ |
| description | This research is about operational- and complexity-oriented aspects of classical foundations of computability theory. The approach is to re-examine some classical theorems and constructions, but with new criteria for success that are natural from a programming language perspective. Three cornerstones of computability theory are the S-m-ntheorem; Turing's "universal machine''; and Kleene's second recursion theorem. In today's programming language parlance these are respectively partial evaluation, self-interpretation, and reflection. In retrospect it is fascinating that Kleene's 1938 proof is constructive; and in essence builds a self-reproducing program. Computability theory originated in the 1930s, long before the invention of computers and programs. Its emphasis was on delimiting the boundaries of computability. Some milestones include 1936 (Turing), 1938 (Kleene), 1967 (isomorphism of programming languages), 1985 (partial evaluation), 1989 (theory implementation), 1993 (efficient self-interpretation) and 2006 (term register machines). The "Swiss pocket knife'' of the title is a programming language that allows efficient computer implementation of all three computability cornerstones, emphasising the third: Kleene's second recursion theorem. We describe experiments with a tree-based computational model aiming for both fast program generation and fast execution of the generated programs. |
| first_indexed | 2024-04-13T10:41:31Z |
| format | Article |
| id | doaj.art-9396d0ac1b2c4fc4ab714e2f508ce301 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-04-13T10:41:31Z |
| publishDate | 2013-09-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-9396d0ac1b2c4fc4ab714e2f508ce3012022-12-22T02:49:55ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802013-09-01129Festschrift for Dave Schmidt11710.4204/EPTCS.129.1A Swiss Pocket Knife for ComputabilityNeil D. JonesThis research is about operational- and complexity-oriented aspects of classical foundations of computability theory. The approach is to re-examine some classical theorems and constructions, but with new criteria for success that are natural from a programming language perspective. Three cornerstones of computability theory are the S-m-ntheorem; Turing's "universal machine''; and Kleene's second recursion theorem. In today's programming language parlance these are respectively partial evaluation, self-interpretation, and reflection. In retrospect it is fascinating that Kleene's 1938 proof is constructive; and in essence builds a self-reproducing program. Computability theory originated in the 1930s, long before the invention of computers and programs. Its emphasis was on delimiting the boundaries of computability. Some milestones include 1936 (Turing), 1938 (Kleene), 1967 (isomorphism of programming languages), 1985 (partial evaluation), 1989 (theory implementation), 1993 (efficient self-interpretation) and 2006 (term register machines). The "Swiss pocket knife'' of the title is a programming language that allows efficient computer implementation of all three computability cornerstones, emphasising the third: Kleene's second recursion theorem. We describe experiments with a tree-based computational model aiming for both fast program generation and fast execution of the generated programs.http://arxiv.org/pdf/1309.5128v1 |
| spellingShingle | Neil D. Jones A Swiss Pocket Knife for Computability Electronic Proceedings in Theoretical Computer Science |
| title | A Swiss Pocket Knife for Computability |
| title_full | A Swiss Pocket Knife for Computability |
| title_fullStr | A Swiss Pocket Knife for Computability |
| title_full_unstemmed | A Swiss Pocket Knife for Computability |
| title_short | A Swiss Pocket Knife for Computability |
| title_sort | swiss pocket knife for computability |
| url | http://arxiv.org/pdf/1309.5128v1 |
| work_keys_str_mv | AT neildjones aswisspocketknifeforcomputability AT neildjones swisspocketknifeforcomputability |