[PDF][PDF] On the simplicity and speed of programs for computing infinite sets of natural numbers
GJ Chaitin - Journal of the ACM (JACM), 1969 - dl.acm.org
GJ Chaitin
Journal of the ACM (JACM), 1969•dl.acm.orgIn view of Remark 7, the following theorem is merely a corollary to Theorem 5. rI~ IEOREM 6.
Consider a simple-program computer I. For any connecting function% the~ exists a natural
number cv which has the following property: For any V-connected set S and any infinite
computable subset R of S, II, z (S)< IIz (R)+ cv. In fact, we can take 11 ev= 2c~= 2 max (zcz~,
z~ cz).
Consider a simple-program computer I. For any connecting function% the~ exists a natural
number cv which has the following property: For any V-connected set S and any infinite
computable subset R of S, II, z (S)< IIz (R)+ cv. In fact, we can take 11 ev= 2c~= 2 max (zcz~,
z~ cz).
In view of Remark 7, the following theorem is merely a corollary to Theorem 5. rI~ IEOREM 6. Consider a simple-program computer I. For any connecting function% the~ exists a natural number cv which has the following property: For any V-connected set S and any infinite computable subset R of S, II, z (S)< IIz (R)+ cv. In fact, we can take 11 ev= 2c~= 2 max (zcz~, z~ cz).
ACM Digital Library