Computable sequence of rationals with a noncomputable limit

  • Level: Undergrad 
  • Thread starter Hill
  • Start date
8 replies · 3K views · last reply
Hill
Messages
867
Reaction score
658
TL;DR
There is a computable sequence of rational numbers with limit whose n-th binary digit is not a computable function of n
This is a proof of the above statement in Stillwell's "Reverse Mathematics", p.77:

Printed proof from a math book: a bold statement that a computable sequence of rationals can have a noncomputable limit, followed by a proof defining rational terms r_n as a sum of powers of 2 over computable values f(i).


My question is, how do we know that the sequence ##r_1, r_2, ...## converges?
 
You should describe ##D## for us, I assume it is a subset of the natural numbers.
With that in mind:
Since ##f## is an injection on a subset of ##D##, each ##r_n \lt \sum_{i=1}^\infty 2^{-i} = 1##. Since the sequence, ##r_n## is increasing and bounded, it converges.
 
jedishrfu said:
Doesn't this come from the series being finite binary expansion? Being finite it will sum to a finite number.
I don't understand.
I understand that each ##r_n## has a finite binary expansion. I also understand that if the sequence converges, the limit is a finite number. I just don't see how we know that the sequence converges.
 
FactChecker said:
You should describe ##D## for us, I assume it is a subset of the natural numbers.
Yes, it is.

FactChecker said:
Since ##f## is an injection on a subset of ##D##, each ##r_n \lt \sum_{i=1}^\infty 2^{-i} = 1##. Since the sequence, ##r_n## is increasing and bounded, it converges.
The sequence ##r_n=\sum_{i=1}^n 2^{-i}## is increasing, but not necessarily the sequence ##r_n=\sum_{i=1}^n 2^{-f(i)}##, I think.
 
You are summing to n not to infinity. Convergence doesn't come into play.

A finite expansion will have a finite number of terms and in this case each term is ##2^{-1}## or did I misread the text.
 
jedishrfu said:
You are summing to n not to infinity. Convergence doesn't come into play.

A finite expansion will have a finite number of terms and in this case each term is ##2^-1## or did I misread the text.
The statement is about n-th binary digit of the limit. For the limit to exist, the sequence needs to converge, doesn't it?
 
Perhaps it is not important for my question, but in case it clarifies the proof, here is the description of ##D##, with explanation of the notation:

Printed textbook page on computable partial functions: defines Phi_k(n) as the output of algorithm A_k on input n, and states the set D = {k : Phi_k(k) = 0} is computably enumerable but not computable.
 
FactChecker said:
Since ##f## is an injection on a subset of ##D##, each ##r_n \lt \sum_{i=1}^\infty 2^{-i} = 1##. Since the sequence, ##r_n## is increasing and bounded, it converges.
You're right. The sequence ##r_n=\sum_{i=1}^n 2^{-f(i)}## is increasing. I was mistaken in the post #5.