I don't know anything about it. Therefore, I may have used the wrong words in the question.
We know that there are uncountable many non-computable infinite sequences which is consist of elements $\left\{0,1\right\}$ and there are countable many computable infinite sequences which is consist of elements $\left\{0,1\right\}.$
Here is my question:
Is it possible to define such a set that contains countable infinite computable and countable infinite non-computable infinite sequences which is consist of elements $\left\{0,1\right\}$ ?
I mean, the set I'm talking about it is a set that contains both countable many computable and countable many non-computable infinite sequences.
However, the number of both non-computable and computable functions/sequences must be infinite. Is it possible to define such a set?
How do I create such a set and notation?
Thank you very much.
Best Answer
Let me start by making a couple observations:
As soon as you have an uncountable set of things, you can also get a countable set of the same type of thing by just throwing out a bunch of stuff. So in one sense your question is trivial. On the other hand, things get more interesting when we demand concreteness: are there "reasonably-definable" examples of the sets you're asking about?
Also, note that this really boils down to finding an appropriate set of noncomputable sequences; after that, we can just take the union of that set with the set of computable sequences. So let's forget entirely about the computable-sequences part of your question.
The following is the same idea as Hagen von Eitzen's comment (which I think you misunderstood by taking "finitely many" to mean "fixed finitely many); the key point is the fact that two sequences which differ on only finitely many bits are either both computable or both non-computable.
Fix your favorite non-computable binary sequence $\alpha$, and for each $i\in\mathbb{N}$ let $\alpha_i$ be the binary sequence which differs from $\alpha$ at and only at the $i$th bit. Then the set $$\{\alpha_i: i\in\mathbb{N}\}$$ is countably infinite and consists entirely of non-computable sequences.
Now you might object that the $\alpha_i$s are all "morally equivalent." There is in fact a precise sense in which they're equivalent, given by Turing reducibility.
We can indeed, by iterating the Halting Problem! The set $$\{\emptyset^{(n)}:\mathbb{N}\}$$ is perfectly concrete, and no two elements have the same Turing degree. And it's clearly countable.
You might still object on the grounds that these iterated jumps aren't "maximally different," they still have some relationship to each other. And here things get a bit interesting.
It's not hard to show that for any finite family of c.e. sets, none of which are Turing equivalent to either $\emptyset$ (= computable) or $\emptyset'$ (= complete), there is a c.e. set which is Turing incomparable to each of them. This means that we can build an infinite antichain with respect to Turing reducibility of c.e. sets via a "greedy algorithm:" recursively let $e_i$ be the least natural number such that $W_{e_i}$ is Turing incomparable with each $W_{e_j}$ for $j<i$ (fine, with the further stipulation that $W_{e_0}$ must be neither computable nor complete). This is perfectly definable.
(Another argument consists of the following. We can define a perfect (= no dead ends, every node has a split above it) binary tree $T$ such that any two paths through $T$ have incomparable Turing degree. Now any infinite binary sequence $f$ yields a path $p_f$ through $T$, by using the $n$th bit of the sequence to determine which way to go at the $n$th split, and so now we just take any countable set $F$ of infinite paths whatsoever and look at $\{p_f: f\in F\}$. Despite looking much more abstract, this argument is much simpler than the argument above.)
However, it's still not natural. And here's where things get really interesting:
Sure, we can whip up lots of incomparability in the Turing degrees - there are even concrete examples of uncountable Turing antichains - but the degrees in these antichains are always fairly ad hoc. Indeed, there is a body of results and conjectures pointing towards the general thesis that this cannot happen. This goes well beyond this question, but it is a problem worth mentioning: that for all the weird behavior the Turing degrees provably have, the natural examples of Turing degrees are actually quite well-behaved in many senses.
Here's a concrete example of that. All solutions to Post's problem - that is, all constructions of c.e. sets which are neither computable nor complete - rely at some point on a choice of numbering of computable partial functions. Change that numbering and you change the set produced - indeed, you change its degree. So one might reasonably ask whether this is a necessary feature. It's not clear how to phrase this precisely, but a "relativized" version of the question is quite easy to pose precisely: is there an $e$ such that for all Turing-equivalent $X, Y$ we have $$X\equiv_TY<_T W_e^X\equiv_TW_e^Y<_TX'\equiv_TY'?$$ This seems like a plausible dream result at first, but Downey and Shore showed that it doesn't exist.