Convergent Computability

Computer Science Level 3

Let ⟨ a n ⟩ \left \langle a_n \right \rangle be a convergent sequence in R \mathbb{R} . Furthermore, let ⟨ a n ⟩ → a \left \langle a_n \right \rangle \to a .

True or False: If a i a_i is computable for every i ∈ N i \in \mathbb{N} , then a a is also computable.

  • A number x ∈ R x \in \mathbb{R} is computable , iff there exists a procedure (with a finite description) that, for each b ∈ N b \in \mathbb{N} , eventually decides the b b th most significant bit of x x .
Inspired from Quora
True False

Agnishom Chattopadhyay by Agnishom Chattopadhyay , 22, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Sándor Daróczi
Jun 8, 2017

Consider the sequence a n a_n = 1 - 1 n \frac{1}{n} + b n b_n where b n b_n = 0 if n < k or b n b_n = 1 if n ≥ k n \geq k for an integer k. Clearly the sequence converges to 2 as n approaches infinity. Observe that if k moves on the number line from 0 to infinity the limit doesn't change, so k can be chosen arbitrarily in the interval. Let P = { i j i_j | 0 < j ≤ n j \leq n } and let a i a_i , i ∈ P i \in P the collection of elements Bob has already computed to some significant bit. Setting k > max{ i j i_j } the limit obviously doesn't change, while Bob has no information to decide whether a = 1 or a = 2. Thus ultimately we can conclude that a is not computable.

2 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...