A Note on Computability

When I studied the non-computable numbers in college, I remember thinking that existing proofs were pointlessly longwinded, since you could show quite plainly, that because the reals are uncountable, and the number of programs that can be run on a UTM is countable, there are more numbers than there are programs, which proves the existence of non-computable numbers. That is, there aren’t enough programs to calculate all of the reals, and so it must be the case that some real numbers aren’t associated with programs, and are therefore non-computable.

But it just dawned on me, that you could have this result, even without resorting to the fact the reals are uncountable, since it could simply be the case that the set of all inputs to a UTM maps to some countable, proper subset of a countable subset of the reals. Expressed formally, let S \subset R, and assume that S is countable. That is, S is a countable subset of the reals, and because it’s countable, it’s a proper subset (i.e., obviously, S does not contain all of the reals). It could be simply be the case that the set of all inputs to a UTM, A, maps to only a subset of S. That is, even though S is countable, it could could still be the case that A maps to only a subset of S, and not the entire set.

Here’s a concrete example: Let K be the set of all non-computable numbers, which you can easily show is uncountable. Now let S be a countable subset of K. It follows that there is no mapping at all from A to S, since by definition, for each x \in S, there is no program that calculates x.

So aside from this little result, I suppose the point is, that even if all of the reals don’t exist, you could still be stuck with non-computable numbers.

Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s