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 computing this particular set comes from the indexing of theorems. No matter what indexing method our turing machine uses to index the theorems of peano arithmetic we could always construct a theorem that doesn’t appear on the list our turing machine is to test. Just as cantor was able to show with the real #s. As a result, no turing machine can know even one member of such a set. I suppose that one would encounter the same problems in trying to use a turing machine to predict the next member in arbitrary patterns of natural numbers. Suppose a real god were feeding our turing machine the set considered above. The turing machine would never be able to reliably predict the next member arbitrarily far off into the future. The other article treats concepts like one’s daughter or a countries soldier and their decisions as sets of binary numbers as well. Suppose however that such sets were the same as the set of truth values for the theorems of peano arithmetic considered above. Now that would be much more interesting than artificial intelligence based on solomonoff’s induction.
Another part of the difficulty in computing this particular set comes from the indexing of theorems. No matter what indexing method our turing machine uses to index the theorems of peano arithmetic we could always construct a theorem that doesn’t appear on the list our turing machine is to test. Just as cantor was able to show with the real #s.
I don’t think that is correct. Cantor’s ability to find real numbers that do not show up anywhere in any particular indexing scheme in which the integers are used to index the reals is dependent on the fact that the exact representation of many real numbers requires a string of digits of infinite length. This is not true of theorems in Peano arithmetic; although there are an infinite number of theorems in Peano arithmetic, each theorem can be represented with a string of symbols of finite length. So, there are countably many theorems and therefore we can index them using the integers.
I find it difficult to know what this is saying, but here are some true statements to set beside it.
The set of sentences of Peano arithmetic is recursive, the set of proofs of theorems is recursive, the set of theorems (provable sentences) is recursively enumerable, and the set of sentences that are not theorems is not recursively enumerable.
A utm (universal Turing machine) is not the thing you are talking about under that name. It is a Turing machine that can emulate any Turing machine by being given a specification of it.
I find it difficult to know what this is saying, but here is a true statement to set beside it: The set of theorems of Peano arithmetic is recursively enumerable, but the complement of that set is not. Also, a utm (universal Turing machine) is not the thing you are talking about under that name; it is a Turing machine that can emulate any Turing machine by being given a specification of it.
This is all rather confused. Here is a true statement to set beside it: The set of theorems of Peano arithmetic is recursively enumerable, but the complement of that set is not.
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 computing this particular set comes from the indexing of theorems. No matter what indexing method our turing machine uses to index the theorems of peano arithmetic we could always construct a theorem that doesn’t appear on the list our turing machine is to test. Just as cantor was able to show with the real #s. As a result, no turing machine can know even one member of such a set. I suppose that one would encounter the same problems in trying to use a turing machine to predict the next member in arbitrary patterns of natural numbers. Suppose a real god were feeding our turing machine the set considered above. The turing machine would never be able to reliably predict the next member arbitrarily far off into the future. The other article treats concepts like one’s daughter or a countries soldier and their decisions as sets of binary numbers as well. Suppose however that such sets were the same as the set of truth values for the theorems of peano arithmetic considered above. Now that would be much more interesting than artificial intelligence based on solomonoff’s induction.
I don’t think that is correct. Cantor’s ability to find real numbers that do not show up anywhere in any particular indexing scheme in which the integers are used to index the reals is dependent on the fact that the exact representation of many real numbers requires a string of digits of infinite length. This is not true of theorems in Peano arithmetic; although there are an infinite number of theorems in Peano arithmetic, each theorem can be represented with a string of symbols of finite length. So, there are countably many theorems and therefore we can index them using the integers.
I find it difficult to know what this is saying, but here are some true statements to set beside it.
The set of sentences of Peano arithmetic is recursive, the set of proofs of theorems is recursive, the set of theorems (provable sentences) is recursively enumerable, and the set of sentences that are not theorems is not recursively enumerable.
A utm (universal Turing machine) is not the thing you are talking about under that name. It is a Turing machine that can emulate any Turing machine by being given a specification of it.
I find it difficult to know what this is saying, but here is a true statement to set beside it: The set of theorems of Peano arithmetic is recursively enumerable, but the complement of that set is not. Also, a utm (universal Turing machine) is not the thing you are talking about under that name; it is a Turing machine that can emulate any Turing machine by being given a specification of it.
This is all rather confused. Here is a true statement to set beside it: The set of theorems of Peano arithmetic is recursively enumerable, but the complement of that set is not.