Many sets of natural numbers are not computable in the sense that there is no recursive algorithm which generates their members sequentially. One such set would be the set of truth values of all theorems of peano arithmetic. A utm tests a given proposition encoded as a natural number in binary and prints one if the theorem is universally true, zero otherwise. If the answer is yes our turing machine will eventually discover this and print one. If the answer is no however, our machine will continue to test our theorem using the natural numbers forever, never reaching the decision that the answer is indeed no. Another part of the difficulty in... (read more)
Many sets of natural numbers are not computable in the sense that there is no recursive algorithm which generates their members sequentially. One such set would be the set of truth values of all theorems of peano arithmetic. A utm tests a given proposition encoded as a natural number in binary and prints one if the theorem is universally true, zero otherwise. If the answer is yes our turing machine will eventually discover this and print one. If the answer is no however, our machine will continue to test our theorem using the natural numbers forever, never reaching the decision that the answer is indeed no. Another part of the difficulty in... (read more)