3 ms·
I recently learned that the computable numbers are subcountable but not enumerable. Proof sketch: Turing Machines are enumerable by lexiographically sorting th
by calebh 3y ago
I recently learned that the computable numbers are subcountable but not enumerable.
Proof sketch:
Turing Machines are enumerable by lexiographically sorting them. The Turing Machines that compute computable numbers are a subset of them. Therefore the set of computable numbers is subcountable.
Now assume that the set of computable numbers is enumerable by some Turing Machine M. Then I can construct a new computable number who's ith digit is a swap from the ith number's ith digit given by M (ie a diagonialization). This contradiction shows that the set of computable numbers is not enumerable.
Another way of looking at this is that determining if some Turing Machine computes a computable number requires deciding the halting problem, which cannot be done. TMs computing computable numbers are required to terminate given an input precision.