Computability is Nonsense?
Start with a Godel-numbering of Turing machines whose outputs are real numbers and which can be described with a finite amount of information. In an ideal world, build a Turing-complete programming language, and take a Godel-numbering of programs which take as input a natural number (n) and return as output the first n digits of a real number (let's say between 0 and 1 for simplicity).
Define the set of computable numbers as the set of real numbers which are approximated by this process. There are clearly a countable number of computable numbers since each can be described by a computer program of finite length which can be collapsed into binary as a number, so they're in correspondence with a subset of the natural numbers.
So then, write out the decimal expansions of these numbers in a block, and build Cantor's diagonal element, which has a value at each decimal place not equal to the corresponding computable number's value at that decimal place. Then this diagonal element is necessarily not in the list. However, I have just described an algorithm for computing as many of the first n digits of its decimal expansion, and the programming language we used is assumed to be turing complete. This is a contradiction.
Right?
So what went wrong?
EDIT: The issue that arises is the halting problem; we want "computable" to mean "known to halt." When the diagonal element here encounters itself, it needs to know what to do or else computing it doesn't halt. If it is equal to itself it's on the list, if it's not then it doesn't halt and isn't computable.
Define the set of computable numbers as the set of real numbers which are approximated by this process. There are clearly a countable number of computable numbers since each can be described by a computer program of finite length which can be collapsed into binary as a number, so they're in correspondence with a subset of the natural numbers.
So then, write out the decimal expansions of these numbers in a block, and build Cantor's diagonal element, which has a value at each decimal place not equal to the corresponding computable number's value at that decimal place. Then this diagonal element is necessarily not in the list. However, I have just described an algorithm for computing as many of the first n digits of its decimal expansion, and the programming language we used is assumed to be turing complete. This is a contradiction.
Right?
So what went wrong?
- Is my definition of computable bad? I don't think that's really possible, since I'm just choosing a subset of the real numbers, which fail this test because they are uncountable.
- Is it unclear what is meant by computable? Well I'm not actually asking about set membership; the proof is (not very effectively) constructive--given a real world system it would be possible to put computational bounds on everything and build this system. What would happen?
- Is the set of computable numbers as I've defined it not actually countable? I.e., is there no way to write a single Turing-complete programming language that can be converted to machine code for a given system? That strains credulity for me.
- Is Cantor's diagonal construction not turing-computable? This also strains credulity since it requires only very basic logic. Of course if you are something like a large-number-atheist and don't believe that 10^^^^10 exists then you're safe, since the point at which the diagonal element shows up in the list could just be so big that the index doesn't exist in real life.
EDIT: The issue that arises is the halting problem; we want "computable" to mean "known to halt." When the diagonal element here encounters itself, it needs to know what to do or else computing it doesn't halt. If it is equal to itself it's on the list, if it's not then it doesn't halt and isn't computable.