Computer Science And Recursion Theory

ABSTRACT

One of the basic concerns of classical mathematical logic has been a rigorous definition of “mathematical proof". A proof may be discovered by luck, genius or accident. But once discovered it is mechanically checkable. Thus the most general type of mechanically checkable procedure provides a definition of the most general kind of proof. An investigation of “mechanical checkability" leads naturally to the notion of “computable process". Recursion theory is that branch of mathematical logic which studies computability theory. From its very inception recursion theory has been so closely associated with theoretical computer science that it is sometimes difficult to tell where one begins and the other ends. Both appear to have a common origin in the 1930's and 1940's - when the fundamental results of Turing, Post, Herbrand-Gödel, Kleene and Church on computability were obtained [52,53,35,36,19,25,26,11,12,13]. Although the work of each of these authors is based on a different intuition as to the nature of computability, they all share a common feature. In each, the approach is discrete and atomic. No attempt was made to use machines with continuously varying parameters - e.g. analog computers - as a basis for understanding computability. The author finds this regrettable and is trying to remedy the situation [39]. At all events, all of these discrete, atomic definitions have been proved to be equivalent. It is now widely accepted that the concept “computable function of natural numbers" is correctly identified with “partial recursive function". Lack of space forces us to be selective rather than exhaustive. We discuss briefly five areas of interest to the computer scientist. The purpose of this paper is to explore the interaction of recursion theory with computer science in these areas. We consider, not only similarities between the two fields, but also points of difference. We discuss how recursion theory supplied computer science with specific mathematical definitions and techniques. We also consider how the computer scientist shaped (and is still shaping) this recursion-theoretic material to his own needs. The five areas are not mutually exclusive: there are numerous connections between them. In the interest of clarity and brevity, reference is made only to those works which are easily understandable to the beginner. No attempt is made to make the bibliography complete or up-to-date.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 2: Ax, J. The elementary theory of finite fields. Ann. of Math., 88, 239-271 (1968).
• 3: Ax, J. and Kochen, S. Diophantine problems over local fields I. Am. J. Math., 87, 605-630 (1965)
• 4: Ax, J. and Kochen, S. Diophantine problems over local fields II. Am. J. Math., 87, 631-648 (1965).
• 5: Ax, J. and Kochen, S. Diophantine problems over local fields III, Ann. Math., 83, 437-456 (1966).
• 6: Baker, T., Gill, J. and Solovay, R. Relativizations of the P@@@@NP question. SIAM J. comput. 4, 431-441 (1975).
• 7: Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, Journal of the ACM (JACM), v.14 n.2, p.322-336, April 1967 [doi>10.1145/321386.321395]
• 8: Boone, W.W. The word problem. Ann. of Math. (2) 70, 207-265 (1959).
• 9: Chandra, A.K. and Stockmeyer, L.J. Alternation. Proc. 17th annual symposium on foundations of computer science. 98-108 (1976).
• 10: Chang, C.C. and Keisler, H.J. Model Theory. Studies in Logic 73, North-Holland Pub. Co. (1973).
• 11: Church, A. A set of postulates for the foundation of logic. Ann. Math. 2nd series 33, 346-366 (1932); 34, 839-864 (1933).
• 12: Church, A. An unsolvable problem of elementary number theory. Amer. J. Math. 58, 345-363 (1936).
• 13: Church, A. A note on the Entscheidungs-problem. J.S.L. 1, 40-41, 101-102 (1936).
• 14: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 15: Calvin C. Elgot , Abraham Robinson, Random-Access Stored-Program Machines, an Approach to Programming Languages, Journal of the ACM (JACM), v.11 n.4, p.365-399, Oct. 1964 [doi>10.1145/321239.321240]
• 16: Fischer, M.J. and Rabin, M.O. Superexponential complexity of Presburger arithmetic. SIAM-AMS Proceedings 7, Amer. Math. Society 27-41 (1974).
• 17: Garey, M.R. and Johnson, D.S. Computers and Intractability. to be published by W.H. Freeman and Co.
• 18: Gödel, K. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatsh. für Math. und Phys. 38, 173-198 (1931).
• 19: Gödel, K. On undecidable propositions of formal mathematical systems. The Undecidable (ed. by M. Davis) Raven Press, 41-71 (1965).
• 20: Grzegorczyk, A. On the definitions of computable real continuous functions. Fund. Math. 44, 61-71 (1957).
• 21: J. Hartmanis , J. E. Hopcroft, An Overview of the Theory of Computational Complexity, Journal of the ACM (JACM), v.18 n.3, p.444-475, July 1971 [doi>10.1145/321650.321661]
• 22: John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
• 23: Horowitz, E. and Sahni, S. Algorithms: Design and Analysis. to be published by Computer Science Press, Inc.
• 24: Karp, R.M. Reducibility among combinatorial problems. Complexity of Computer Computations, R.E. Miller and J.W. Thatcher eds., Plenum Press, 85-104 (1972).
• 25: Kleene, S.C. A theory of positive integers in formal logic. Amer. J. Math. 57, 153-173, 219-244 (1935).
• 26: Kleene, S.C. &lgr;-definability and recursiveness. Duke Math. J. 2, 340-353 (1936).
• 27: Kleene, S.C. Introduction to metamathematics. D. van Nostrand Co., Inc. (1952).
• 28: Kleene, S.C. Representation of events in nerve nets and finite automata. Automata Studies, (ed. by C.E. Shannon and J. McCarthy) Annals of Math. Studies. #34, 3-41 (1956).
• 29: Kozen, D. On parallelism in Turing Machines. Proc 17th annual Symposium on Foundations of Computer Science, 89-97 (1976).
• 30: Kreisel, G. A notion of mechanistic theory. Synthese 29, 11-26 (1974).
• 31: Markov, A.A. On the impossibility of certain algorithms in the theory of associative systems (Russian). Dokl. Akad. Nauk. SSSR 55, 587-590 (Eng. tr. Comptes rendus de l'Academie des Sciences de l'URSS, n.s. 55, 583-586) (1947).
• 32: Matijacevič, Y. Enumerable sets are Diophantine. Dokl. Akad. Nauk. SSSR 191, 279-282, (Eng. tr. Soviet Math. Doklady 11, 354-358) (1970).
• 33: Meyer, A.R. The inherent computational complexity of theories of ordered sets. Proc. Int'l Congress of Mathematicians (Vancouver) 2, 477-482 (1974).
• 34: Novikov, P.S. On the algorithmic unsolvability of the word problem in group theory (Russian). Trudy Mat. Inst. im Steklov #44 (1955).
• 35: Post, E.L. Finite combinatory processes-formulation I. J.S.L. 1, 103-105 (1936).
• 36: Post, E.L. Formal reductions of the general combinatorial decision problem. Amer. J. Math. 65, 197-215 (1943).
• 37: Post, E.L. Recursively enumerable sets of positive integers and their decision problems. Bull. Amer. Math. Soc. 50, 284-316 (1944).
• 38: Post, E.L. Recursive unsolvability of a problem of Thue. J.S.L. 12, 1-11 (1947).
• 39: pour-El, M.B. Abstract computability and its relation to the general-purpose analog computer. TAMS 199, 1-28 (1974).
• 40: Pour-El, M.B. and Richards, I. - presented at the AMS special session on recursion theory, Houston, April 1978. Notices AMS 25, #755-E15, A-386 (1978).
• 41: Presburger, M. Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen in welchem die Addition als einzige Operation hervortritt, C.R. 1er Congr. des Mathématiciens des Payes Slaves (Warsaw) 92-101, 395 (1930).
• 42: Rabin, M.O. Decidability of second order theories and automata on infinite trees. TAMS 141, 1-35 (1969).
• 43: Rabin, M.O. and Scott, D. Finite automata and their decision problems. IBM Journal of Research and Development 3, 114-125 (1959).
• 44: Rice, H.G. Recursive real numbers. Proc. Amer. Math. Soc. 5, 784-791 (1954).
• 45: Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
• 46: Sacks, G.E. Degrees of unsolvability. Annals of Math. Studies #55 (1963).
• 47: J. C. Shepherdson , H. E. Sturgis, Computability of Recursive Functions, Journal of the ACM (JACM), v.10 n.2, p.217-255, April 1963 [doi>10.1145/321160.321170]
• 48: Szmielew, W. Elementary properties of abelian groups. Fund. Math. 41, 203-271 (1955).
• 49: Tarski, A. Arithmetical classes and types of Boolean algebras (preliminary report) Bull. Am. Math. Soc. 55, 64, 1192 (1949).
• 50: Tarski, A. A decision method for elementary algebra and geometry (2nd ed.). University of California Press (1951).
• 51: Tarski, A., Mostowski, A., and Robinson, R.M. Undecidable theories. North-Holland Pub. Co. (1953).
• 52: Turing, A.M. On computable numbers with an application to the Entschiedungsproblem Proc. London Math. Soc., ser. 2, 42, 230-265 (1936-7). A correction, ibid. 43, 544-546 (1937).
• 53: Turing, A.M. Computability and &lgr;-definability. J.S.L. 2, 153-163 (1937).

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.3 COMPUTERS AND EDUCATION
      K.3.2 Computer and Information Science Education
          Subjects: Computer science education

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Recursive function theory

General Terms:
Human Factors, Theory