Under which conditions does the non-computable infinite sequences have a computable subsequences?

51 Views Asked by At

Under which conditions does the non-computable infinite sequences have a computable subsequences?

And if we subtract non-computable infinite sequences which has a computable subsequence, from non-computable infinite sequences which has no computable subsequence, does cardinality change?

Is cardinality still equal to $2^{\aleph_0}$ in both cases?

Wherein said sequence or function consists of only $0$ and $1 s.$

Thank you.

1

There are 1 best solutions below

0
On

By the pidgeonhole principle, every infinite sequence has an infinite subsequence of all 0's or all 1's, both of which are computable. So all sequences have infinite computable subsequences. (The indices of these subsequences may themselves be uncomputable, however.)