Is it possible to define an unique operation $\varphi$, which transforms a computable function into a non computable function?

Question

Suppose, a non-computable function $f:\mathbb{N}\longrightarrow \left\{0,1\right\}$ is given.

We have $f(n)=a_n$, where $\left\{a_n\right\}_{n\in\mathbb{N}}$

Is it possible to define an unique operation $\varphi$, which transforms a computable function into a non-computable function? Such that, if the computable function given is different, the result of this operation must certainly give us different result. So this operation I'm talking about is unique.

For example,

$\left\{0,1,0,1,0,1\cdots\right\}\overset\varphi{\longrightarrow} \left\{a_1,a_2,a_3,\cdots\right\}$

Is it possible to define such a operation?

Answer 1

(Per The_Sympathizer, you don't want to talk about unique functions but rather injective functions - saying that a function is unique is saying that no other function with the relevant properties exists, which isn't what's meant here.)

---

Computability isn't relevant to this question at all.

Since the set of computable sequences is countable and the set of noncomputable sequences is uncountable, the answer is yes: countable sets are smaller than uncountable ones, and anytime I have a countable set $X$ and an uncountable set $Y$ there is an injection from $X$ to $Y$. Note that this doesn't have anything to do with computability theory. Given your other questions re: cardinality, this purely set-theoretic phenomenon is something you should make sure you understand, especially since bringing in computability theory only makes the situation more complicated than it actually is.

• Incidentally, this actually requires a very small amount of the axiom of choice - it's not provable in ZF alone. But that's not worth paying attention to at first; focus on the ZFC-picture for now.

---

That said, if we care specifically about computability theory for whatever reason in this context, a significantly stronger result is true:

The set of functions from $\mathbb{N}$ to $\{0,1\}$ has a natural topology, and with this topology is called Cantor space (and is homeomorphic to the Cantor set with the usual topology, hence the name); I'll refer to this space as "$\mathcal{C}$."

There is then a function $\varphi$ (actually, there are many such functions) from $\mathcal{C}$ to $\mathcal{C}$ such that:

• $\varphi$ is continuous (in fact, "reducible" in an appropriate sense to the Halting Problem) and

• if $f\not=g$ then $\varphi(f)\not\le_T\varphi(g)$. (Note that this trivially implies that nothing in the range of $\varphi$ is computable; it can also be strengthened in various ways, but let's ignore that for now.)

The former condition says that $\varphi$ isn't too weird. The latter condition says that $\varphi$ is injective in a very strong sense: not only to we get that $\varphi(f)$ and $\varphi(g)$ are distinct, in some sense they aren't even related to each other, computationally speaking.

This is not a trivial result, but it isn't too hard. The key component is that we can "diagonalize," in a broad sense, against Turing reductions:

Given any finite binary sequences $\sigma,\tau$ and any natural number $e$, there are extensions $\hat{\sigma}\preccurlyeq\sigma,\hat{\tau}\preccurlyeq\tau$ such that if $f, g$ are infinite binary sequences extending $\hat{\sigma},\hat{\tau}$ respectively then $\Phi_e^f\not=g$; moreover, we can find such extensions computably relative to the Halting Problem.

This is the simplest example of a finite extension argument; by "iterating and splitting" we build a perfect (= no dead ends, every node has a splitting extension) tree of finite binary sequences such that any two paths through the tree have incomparable Turing degrees. The map $\varphi$ then takes a given infinite binary sequence $f$ and uses it to build a path $p_f$ through this tree - the $n$th bit of $f$ determines which way $p_f$ goes at the $n$th split in the tree.

(I also mentioned this in my answer to an earlier question of yours.)

Answer 2

What it seems you're asking about is actually an "injective" function, not a "unique" one - one that does not confuse more than one possible input into the same output value.

In that case, sure, just add the non-computable sequence to the computable one. The resulting sum must be non-computable because the algorithm that computes the computable function can reverse the process via subtraction.

Answer 3

Partition the set of functions $f:\mathbb{N}\to\{0,1\}$ into three parts: (i) the countable set of computable functions, $A$; (ii) any countable subset of the non-computable functions, $B$; (iii) the rest, $C$.

Now let $\phi$ be any map which swaps the elements of $A$ and $B$, and permutes $C$ as you will. This gives an uncountable number of possible $\phi$.