4
$\begingroup$

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!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the input. Yes indeed $S$ is the set of partial functions from $X$ to $Y$.But just "partial" and not necessarily "partially recursive". When you said that more precision is needed with the "nature of elements" in $X$, $Y$. I have already said that the sets are countable which means that I can always have a bijection from $\mathbb{N}$ to the sets. I will add the fact to the post that I assume the bijection to be computable. Then I dont think I need to specify more about the elements in $X$ and $Y$. What exactly do you mean by the "framework of CT"?. $\endgroup$
    – swarnim_narayan
    Jun 30, 2013 at 14:20
  • $\begingroup$ I mean that there is no difference between your setting of partial functions $\mathbb N\to\mathbb N$ and the functions that are considered in CT. You are simply asking what uncomputable functions look like, in the classical sense. Another example that I could have given (which is really a function and not a language like halting), is the busy beaver function. $\endgroup$
    – Denis
    Jun 30, 2013 at 14:24
1
$\begingroup$

The halting function is a classic example of an uncomputable function.

If $S$ is countable, you can put it into a one-to-one bijection with the set of all binary strings (or the set of all possible program source codes), so then you can think of the halting function as a function with $S$ as its domain.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.