Posts
Comments
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.