debray@sbcs.UUCP (Saumya Debray) (02/15/84)
Charlie Crummer <crummer@AEROSPACE>: > Since one of the annoying things about undecidable propositions > is that it cannot be decided whether or not they are decidable ... Huh? If a problem "is undecidable", the *by definition* it has been *decided* that it is undecidable. In other words, it has been proved that a decision procedure for the problem cannot exist. An interesting aside on Charlie's comment on the [un]provability of the Goldbach Conjecture is that while it is not known whether the conjecture is provable or not, it can easily be shown that it is impossible to prove the conjecture unprovable: for, assume that we have a proof of unprovability. Then, a Turing Machine looking for a counterexample to the conjecture would run forever (if it ever halted, we would have a counterexample and thereby have proved the conjecture false, contrary to our hypothesis of unprovability). But this would mean that the conjecture held true for every integer, i.e. that the conjecture was true, again contradicting our hypothesis. -- Saumya Debray Dept. of Computer Science SUNY at Stony Brook uucp: {floyd, cbosgd, ihnp4, mcvax, cmcl2}!philabs \ !allegra > !sbcs!debray {teklabs, hp-pcd, metheus}!ogcvax / CSNet: debray@suny-sbcs@CSNet-Relay