A Basis for a Mathematical Theory of Computation
This paper is a corrected version of the paper of the same title given at the Western Joint Computer Conference, May 1961. A tenth section discussing the relations between mathematical logic and computation has been added. Programs that learn to modify their own behaviors require a way of representi...
| Main Author: | |
|---|---|
| Language: | en_US |
| Published: |
2004
|
| Online Access: | http://hdl.handle.net/1721.1/6099 |
| _version_ | 1826199903126159360 |
|---|---|
| author | McCarthy, John |
| author_facet | McCarthy, John |
| author_sort | McCarthy, John |
| collection | MIT |
| description | This paper is a corrected version of the paper of the same title given at the Western Joint Computer Conference, May 1961. A tenth section discussing the relations between mathematical logic and computation has been added. Programs that learn to modify their own behaviors require a way of representing algorithms so that interesting properties and interesting transformations of algorithms are simply represented. Theories of computability have been based on Turing machines, recursive factions of integers and computer programs. Each of these has artificialities which make it difficult to manipulate algorithms or to prove things about them. The present paper presents a formalism based on conditional forms and recursive functions whereby the functions computable in terms of certain base functions can be simply expressed. We also describe some of the formal properties of conditional forms and a method called recursion induction for proving facts about algorithms. A final section in the relations between computation and mathematical logic is included. |
| first_indexed | 2024-09-23T11:27:58Z |
| id | mit-1721.1/6099 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:27:58Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | mit-1721.1/60992019-04-12T08:29:05Z A Basis for a Mathematical Theory of Computation McCarthy, John This paper is a corrected version of the paper of the same title given at the Western Joint Computer Conference, May 1961. A tenth section discussing the relations between mathematical logic and computation has been added. Programs that learn to modify their own behaviors require a way of representing algorithms so that interesting properties and interesting transformations of algorithms are simply represented. Theories of computability have been based on Turing machines, recursive factions of integers and computer programs. Each of these has artificialities which make it difficult to manipulate algorithms or to prove things about them. The present paper presents a formalism based on conditional forms and recursive functions whereby the functions computable in terms of certain base functions can be simply expressed. We also describe some of the formal properties of conditional forms and a method called recursion induction for proving facts about algorithms. A final section in the relations between computation and mathematical logic is included. 2004-10-04T14:39:12Z 2004-10-04T14:39:12Z 1962-01-01 AIM-031 http://hdl.handle.net/1721.1/6099 en_US AIM-031 9914246 bytes 7740678 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | McCarthy, John A Basis for a Mathematical Theory of Computation |
| title | A Basis for a Mathematical Theory of Computation |
| title_full | A Basis for a Mathematical Theory of Computation |
| title_fullStr | A Basis for a Mathematical Theory of Computation |
| title_full_unstemmed | A Basis for a Mathematical Theory of Computation |
| title_short | A Basis for a Mathematical Theory of Computation |
| title_sort | basis for a mathematical theory of computation |
| url | http://hdl.handle.net/1721.1/6099 |
| work_keys_str_mv | AT mccarthyjohn abasisforamathematicaltheoryofcomputation AT mccarthyjohn basisforamathematicaltheoryofcomputation |