Properties Complementary to Program Self-Reference

• Autorzy: Case J. , Moelius III S. E.
• Języki publikacji: EN

Abstrakty

EN

In computability theory, program self-reference is formalized by the not-necessarilyconstructive form of Kleene’s Recursion Theorem (krt). In a programming system in which krt holds, for any preassigned, algorithmic task, there exists a program that, in a sense, creates a copy of itself, and then performs that task using the self-copy. Interpreted in this way, such self-copying programs have usable self-knowledge. Herein, properties complementary to krt are considered. Of particular interest are those properties involving the implementation of control structures. One main result is that no property involving the implementation of denotational control structures is complementary to krt. This is in contrast to a result of Royer, which showed that implementation of if-then-else - a denotational control structure - is complementary to the constructive form of Kleene's Recursion Theorem. Examples of non-denotational control structures whose implementation is complementary to krt are then given. Some such control structures so nearly resemble denotational control structures that they might be called quasi-denotational

Słowa kluczowe

EN

program self-reference

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 111, nr 3
• Strony: 281--311
• Opis fizyczny: Bibliogr. 34 poz.

Twórcy

autor

Case J.

autor

Moelius III S. E.

• IDA Center for Computing Sciences, 17100 Science Drive, Bowie, MD 20715-4300,

Bibliografia

• [1] Adami, C.: What Do Robots Dream Of?, Science, 314(5802), 2006, 1093-1094.
• [2] Amtoft, T., Nikolajsen, T., Träff, J. L., Jones, N.: Experiments with Implementations of Two Theoretical Constructions, Logic at Botik '89: Symposium on Logical Foundations of Computer Science, 363, Springer, 1989.
• [3] Blum, M.: A Machine Independent Theory of the Complexity of Recursive Functions, Journal of the ACM, 14(2), 1967, 322-336.
• [4] Blum, M.: On the size of machines, Information and Control, 11(3), 1967, 257-265.
• [5] Bonfante, G., Kaczmarek, M., Marion, J.-Y.: A Classification of Viruses through Recursion Theorems, Proceedings of Computation and Logic in the Real World - Third Conference of Computability in Europe (CiE'07), 4497, Springer, 2007.
• [6] Bongard, J., Zykov, V., Lipson, H.: Resilient Machines Through Continuous Self-Modeling, Science, 314(5802), 2006, 1118-1121.
• [7] Case, J.: Periodicity in generations of automata, Mathematical Systems Theory, 8(1), 1974, 15-32.
• [8] Case, J.: Infinitary Self-Reference in Learning Theory, Journal of Experimental and Theoretical Artificial Intelligence, 6(1), 1994, 3-16.
• [9] Case, J., Jain, S., Suraj,M.: Control Structures in Hypothesis Spaces: The Influence on Learning, Theoretical Computer Science, 270(1-2), 2002, 287-308.
• [10] Case, J., Moelius, S.: Properties Complementary to Program Self-reference, Proceedings of the 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS'07), 4708, Springer, 2007.
• [11] Case, J., Moelius, S.: Characterizing Programming Systems Allowing Program Self-Reference, Theory of Computing Systems, 45(4), 2009, 756-772.
• [12] Case, J., Moelius, S.: Independence Results for n-Ary Recursion Theorems, Proceedings of 17th International Symposium on Fundamentals of Computation Theory (FCT'09), 5699, Springer, 2009.
• [13] Case, J., Moelius, S.: Program Self-reference in Constructive Scott Subdomains, Proceedings of Mathematical Theory and Computational Practice - Fifth Conference of Computability in Europe (CiE'09), 5635, Springer, 2009.
• [14] Conduit, R.: To Sleep, Perchance to Dream, Science, 315(5816), 2007, 1219-1220, A letter, including responses from C. Adami and H. Lipson, et al.
• [15] Friedman, H.: [FOM] 305: Proofs of Godel's Second. Communication to the Foundations of Mathematics electronic mailing list, December 21, 2006.
• [16] Jain, S., Nessel, J.: Some Independence Results for Control Structures in Complete Numberings, Journal of Symbolic Logic, 66(1), 2001, 357-382.
• [17] Jones, N.: Computer Implementation and Applications of Kleene's S-m-n and Recursion Theorems, Logic From Computer Science, Mathematical Science Research Institute Publications, Springer, 1992.
• [18] Kleene, S. C.: On notation for ordinal numbers, Journal of Symbolic Logic, 3(4), 1938, 150-155.
• [19] Machtey,M.,Winklmann, K., Young, P.: Simple G¨odel Numberings, Isomorphisms, and Programming Properties, SIAM Journal on Computing, 7(1), 1978, 39-60.
• [20] Machtey, M., Young, P.: An Introduction to the General Theory of Algorithms, North Holland, 1978.
• [21] Manna, Z.: Mathematical Theory of Computation, McGraw-Hill, 1974, Reprinted, Dover, 2003.
• [22] Manna, Z., Ness, S., Vuillemin, J.: Inductivemethods for proving properties of programs, Proceedings of the ACM Conference on Proving Assertions about Programs, 1972.
• [23] Moschovakis, Y. N.: Kleene's amazing second recursion theorem, Bulletin of Symbolic Logic, 16(2), 2010, 189-239.
• [24] Plotkin, G.: LCF considered as a programming language, Theoretical Computer Science, 5(3), 1977, 223-255.
• [25] Riccardi, G.: The Independence of Control Structures in Abstract Programming Systems, Ph.D. Thesis, SUNY Buffalo, 1980.
• [26] Riccardi, G.: The Independence of Control Structures in Abstract Programming Systems, Journal of Computer and System Sciences, 22(2), 1981, 107-143.
• [27] Rogers, H.: G¨odel Numberings of Partial Recursive Functions, Journal of Symbolic Logic, 23(3), 1958, 331-341.
• [28] Rogers, H.: Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967, Reprinted, MIT Press, 1987.
• [29] Royer, J.: A Connotational Theory of Program Structure, vol. 273 of Lecture Notes in Computer Science, Springer, 1987.
• [30] Royer, J., Case, J.: Subrecursive Programming Systems: Complexity and Succinctness, Progress in Theoretical Computer Science, Birkhäuser Boston, 1994.
• [31] Schmidhuber, J.: Prototype Resilient, Self-Modeling Robots, Science, 316(5825), 2007, 688, A letter, including responses from H. Lipson, et al.
• [32] Schmidhuber, J.: Resilient, Self-Modeling Robots, 2007, http://www.idsia.ch/~juergen/resilientmachines.html .
• [33] Smullyan, R.: Theory of Formal Systems, vol. 47 of Annals of Mathematics Studies, Princeton University Press, 1961.
• [34] Winskel, G.: The Formal Semantics of Programming Languages: An Introduction, Foundations of Computing Series, MIT Press, 1993.