debray@sbcs.UUCP (Saumya Debray) (02/16/84)
Yesterday I posted an article replying to sri-unix!crummer@AEROSPACE, who
had said that undecidability was undecidable. I'm afraid I misread his
article; undecidability is, in general, obviously undecidable, and I agree
with Charlie. Sorry about that.
--
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-Relayfulk@sunybcs.UUCP (Mark Fulk) (02/22/84)
The problem with the "undecidability of undecidability" is not that undecidable problems must have been proved so; it is perfectly possible for a problem to be undecidable and for us to never know about it. Goldbach's conjecture is decidable; either it is true of the natural numbers or it is not. If it is, the program that answers "yes" to any question decides the question "Is Goldbach's conjecture true"; similarly another program suffices if Goldbach's conjecture is false. Goldbach's conjecture may, however, be unprovable in a particular axiomatization of the natural numbers; there is always a larger axiomatization which implies it or its negative. If Goldbach's conjecture is false, of course, its falsity is provable from the axioms of Peano arithmetic. This is true of any proposition of the form (for all x)[decidable property of x]. Being the sum of two primes is of course a decidable proposition, since the primes are constrained to be less than the given number. The following predicates are undecidable: "Is x provable in Peano arithmetic" "Is x a decidable predicate on the natural numbers". Note that propositions (which are always either true or false) are always decidable; although perhaps not provable in given axiom systems. It is predicates (which have a parameter) which can be undecidable in the sense that there may not be a program to determine from x, if R(x) is true. -- Mark Fulk ARPA and CSNET: fulk.buffalo@rand-relay UUCP: ...!seismo!rochester!rocksvax!sunybcs!fulk U.S. Mail: Department of Computer Science 226 Bell Hall SUNY at Buffalo Buffalo, NY 14260 (716) 636-3197