the number of programs we can write is countable; the number of functions we can write over interesting domains (like natural numbers or integers) is not countable
You should edit and rewrite "the number of functions we can write over interesting domains" as "the number of functions that exist over interesting domains" - it tripped me up.
So we have managed to show, in a fairly simple way, that there have to exist undecidable problems.
I don't think that this is correct. I had to check Wikipedia on decidability:
There are two distinct senses of the word "undecidable" in mathematics and computer science. The first of these is the proof-theoretic sense used in relation to Gödel's theorems, that of a statement being neither provable nor refutable in a specified deductive system. The second sense, which will not be discussed here, is used in relation to computability theory and applies not to statements but to decision problems, which are countably infinite sets of questions each requiring a yes or no answer. Such a problem is said to be undecidable if there is no computable function that correctly answers every question in the problem set.
I don't believe that you're talking about the first meaning, from formal logic. As for the second meaning, it does not apply either, since your "problem set" is not countably infinite.
Right, good observations. I'm being more than a little loose with some of my terminology.
"Undecidable" problems are usually defined in terms of "languages". That is, a language is a set of string, and the problem is to decide whether some particular string is in this set. For certain sets, this is not computable, so they are called undecidable.
However, this is isomorphic to just running any sort of program, so I just took "undecidable" to mean any function from strings to strings that you can't answer with a Turing machine. However, I definitely agree that I could have been far more clear! It seems you can't just read my mind, and I'm not sure if I can really blame you for it.
the number of programs we can write is countable; the number of functions we can write over interesting domains (like natural numbers or integers) is not countable
You should edit and rewrite "the number of functions we can write over interesting domains" as "the number of functions that exist over interesting domains" - it tripped me up.
So we have managed to show, in a fairly simple way, that there have to exist undecidable problems.
I don't think that this is correct. I had to check Wikipedia on decidability:
There are two distinct senses of the word "undecidable" in mathematics and computer science. The first of these is the proof-theoretic sense used in relation to Gödel's theorems, that of a statement being neither provable nor refutable in a specified deductive system. The second sense, which will not be discussed here, is used in relation to computability theory and applies not to statements but to decision problems, which are countably infinite sets of questions each requiring a yes or no answer. Such a problem is said to be undecidable if there is no computable function that correctly answers every question in the problem set.
I don't believe that you're talking about the first meaning, from formal logic. As for the second meaning, it does not apply either, since your "problem set" is not countably infinite.