[Solved]: Finding an Uncomputable Function

Problem Detail: 

Let there be 2 sets $X$ and $Y$, both are countable (assume the bijection from $\mathbb{N}$ to the respective sets is computable) and infinite. Let $S$ be the set of all possible functions (NOT necessarily computable, i dont care about computability at this point) from $A$ to $Y$ for all $A \subset X$ (Remember that $A$ is not fixed here and it varies to cover all subsets of $X$. Note that $X$ and $Y$ are fixed in this question).I understand that $S$ is uncountable (as the number of subsets of $X$ will be uncountable) and hence all functions in it cannot be computable because there are countable number of computable functions. My question is that if there are indeed uncomputable functions in $S$, can somebody please give me an example of one such function or example of a subset of $S$ which contains only uncomputable functions ?

Thankyou!

Asked By : swarnim_narayan

Answered By : Denis

Your definition is a complicated way to say that $S$ is the set of partial functions $X\to Y$ (the sets $A$ you choose are the domains of the partial functions).

Now, if you want to talk about computability, you have to be more precise on $X$ and $Y$: every element of $X$ and $Y$ have to be finitely described, so that they can be manipulated by algorithms.

We can for instance consider that $X=Y=\mathbb{N}$. Since they are countable and infinite, we just have to apply some bijections to get this.

Now, the framework you define is exactly the one of computability theory, you can define turing machines etc, and find out what the uncomputable are. Go here for more details.

For instance the halting function (which is in fact a function $\mathbb N\to \{0,1\}$) is uncomputable. As for an example of subset of $S$ which contains only uncomputable functions, it is true as soon as the domain of the function is not a recursively enumerable set. For instance there is no recursive function $NH\to \mathbb N$, where $NH$ is the set of indices of Turing machines that do not halt on input $0$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12985