Properties complementary to program self-reference

被引:0
作者
Case, John [1 ]
Moelius, Samuel E., III [1 ]
机构
[1] Univ Delaware, Dept Comp & Informat Sci, 103 Smith Hall, Newark, DE 19716 USA
来源
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2007, PROCEEDINGS | 2007年 / 4708卷
关键词
computability theory; programming language semantics; self-reference;
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
In computability theory, program self-reference is formalized by the not-necessarily-constructive 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 on the self-copy. 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.
引用
收藏
页码:253 / +
页数:3
相关论文
共 27 条
[1]   Computer science - What do robots dream of? [J].
Adami, Christoph .
SCIENCE, 2006, 314 (5802) :1093-1094
[2]  
AMTOFT T, 1989, LECTURE NOTES COMPUT, V363, P119
[3]  
[Anonymous], 2014, COMPUTER SCI LIB THE
[4]   ON SIZE OF MACHINES [J].
BLUM, M .
INFORMATION AND CONTROL, 1967, 11 (03) :257-&
[5]   A MACHINE-INDEPENDENT THEORY OF COMPLEXITY OF RECURSIVE FUNCTIONS [J].
BLUM, M .
JOURNAL OF THE ACM, 1967, 14 (02) :322-&
[6]  
BONFANTE G, 2007, LNCS, V4497
[7]   Resilient machines through continuous self-modeling [J].
Bongard, Josh ;
Zykov, Victor ;
Lipson, Hod .
SCIENCE, 2006, 314 (5802) :1118-1121
[8]   Control structures in hypothesis spaces: the influence on learning [J].
Case, J ;
Jain, S ;
Suraj, M .
THEORETICAL COMPUTER SCIENCE, 2002, 270 (1-2) :287-308
[9]   INFINITARY SELF-REFERENCE IN LEARNING-THEORY [J].
CASE, J .
JOURNAL OF EXPERIMENTAL & THEORETICAL ARTIFICIAL INTELLIGENCE, 1994, 6 (01) :3-16
[10]  
Case J., 1974, Mathematical Systems Theory, V8, P15, DOI 10.1007/BF01761704