This type of discussion is why the terms "recursive" v. "recursively enumerable" (RE) were defined. A set S which is _recursive_ can have its elements and non-elements determined in a finite number of steps; i.e., a finite number of steps will conclude whether x in S or not (x in S). A recursively enumerable set can be enumerated, but given an x, there is no finite procedure to determine conclusively if x in S or not. The best you can do is to list all of the elements using your enumeration procedure, and hope that x shows up in the list. But since there is no way to list all of the non-elements of S, you can never conclude that not (x in S) in a finite amount of time. Most standard theories start with axioms & then make deductions willy-nilly to produce a stream of true statements. But if the theory is suitably powerful, then there will be statements that never show up in the stream. Unfortunately, listing all of the false statements (which appear as "not S"" in the stream) won't help, because there will be statements that won't show up in either stream -- either the "true" stream or the "false" stream. These statements that don't appear in the stream _ever_ are "undecidable". At 08:07 PM 11/9/2014, Michael Kleber wrote:
Given a single Turing machine T, is there a decider D which takes the description of T as its input, and returns "true" if T halts and "false" if T does not? Well certainly there is: either the constant machine D_t that always returns "true", or else the constant machine D_f which always returns "false", does the job. There's no algorithm to decide which of these is actually the right D for the given T, but one of them definitely is.
On Sun, Nov 9, 2014 at 10:31 PM, Warren D Smith <warren.wds@gmail.com> wrote:
I do not see the basis for APG's claim for for any particular turing machine T, it is decidable whether it halts. Au contraire, it is decidable IF it halts, but if it does not halt, then why is it decidable?
Similarly, particular propositions like the RH are decidable if false, but might be undecidable if true.
So I do not see APG's claim that only CLASSES of propositions undecidable.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)