Re: Comparing Proofs of Rosser's 1936 Theorem

On 4 Mar 2006 17:08:38 -0800, "Charlie-Boo" <shymathguy@xxxxxxxxx>
wrote:


David C. Ullrich wrote:
On 3 Mar 2006 06:42:50 -0800, "Charlie-Boo" <shymathguy@xxxxxxxxx>
wrote:


David C. Ullrich wrote:
On 19 Feb 2006 15:15:30 -0800, "Charlie-Boo" <chvol@xxxxxxx> wrote:

What is the relationship between the following two proofs of Rosser's
1936 theorem?

1. [Turing 1937] We can list the provable sentences, and by negating
each list the refutable sentences. If the system is both complete and
consistent then any given sentence will be provable or refutable but
not both, and thus will be seen in either but not both lists, and we
can tell if the given sentence is provable, which amounts to solving
the halting problem where halt yes means provable and halt no means
refutable, so halt means decidable.

2. [C-B 2005] If the system is both complete and consistent, then the
refutable sentences coincide with the unprovable sentences, but the
former is an r.e. set whereas the latter is not.

They're essentially the same proof.

The first is written out in much more detail, perhaps
because the concepts mentioned in the second were less
well-known in 1937 or perhaps just because it happens
to be written out in more detail. And of course there
are various _other_ ways the details could be filled
in in the second.

But the two are essentially the
same - the one basic idea appears in both proofs,
in different words.

Really? Well, you really beat me on that one, David. I thought they
were different. So, what is the basic idea that appears in both? I
want to learn where I went wrong and correct my mistake.

I thought # 2 was shorter, simpler, doesn't involve knowing the proof
that the Halting Problem is unsolvable, and is easier to understand.
What is the "one basic idea" that you are referring to that you
discovered appears in both proofs?

The basic idea in your quote(?) of Turing is given by what
you wrote.

You wrote, "They're essentially the same proof. . . . The one basic
idea appears in both proofs, in different words." But where does
Turing's argument appear within mine? What is the "basic" idea
that you were referring to? Or is it all just a lie to try to deny me
credit for my discovery?

It's obviously not true to say there're the same proof. My proof
is much shorter and simpler than Turing's. He describes the
construction of a decision procedure for theorems, and then relies on
the proof of the unsolvability of the Halting Problem. My proof, on
the other hand, does not involve writing a decision procedure nor does
it rely on the unsolvability of the Halting Problem. Instead, I merely
rely on known facts concerning the provable and refutable sentences.

Precisely. Your _version_ of the proof looks simpler because
it uses these known facts instead of explaining why those
same facts are true.

I find my proof easier to understand than Turing's because it
doesn't use a decision procedure and only relies on simple
comparisons of sets with known properties.

How can you say they are the same?

Read my lips: they are essentially the same proof.

See, that was very easy.

Honestly, are you just trying to
deny me credit for coming up with a proof - in fact, one simpler (and
thus arguably better) than Turing's? You are only making an
assertion that flies in the face of the facts - a blatant lie - in
a desperate attempt to deny the obvious fact that my proof is not only
different, it is much simpler in the principles that it uses and the
overall complexity of the proof is simpler.

Puhlease.

The difference is that when a person reads my proof he is apt to find
it easier to understand than the Turing proof.

That may well be. It doesn't follow that they're not essentially
the same argument.

Thus it is a better
proof in that regard.

But to take two different proofs such as these, and the reader can see
they are different and that one is simpler and easier to understand,
and then say, "No, you might think there's a difference, but there
really isn't." is a real joke. It is a lie that is a desperate
attempt to deny someone credit for a mathematical discovery.

A "desperate" attempt? Right. A "mathematical discovery"? Right.
If you _really_ think that "your proof" is not simply obvious
that's very sad.

You should try to publish it, then get back to us concerning
the desperate attempts of the editors and referees to deny
you credit for this discovery.

Btw, make certain not to include an appendix on how ~(x e x)
is not a wff, or how truth has nothing to do with models,
etc. The editor/referee might find that, um, distracting.

************************

David C. Ullrich
.

Relevant Pages

  • Re: OT: election predictions
    ... and striking out wildly at everyone around you. ... "I Riverman do regularly make up shit and state it as ... like David and lots of Libs who thought that skewing the numbers to ... I believe that there are things called facts. ...
    (rec.outdoors.fishing.fly)
  • Re: Tricks to impress Windows users
    ... Like with the pdf thing, let's just recap the facts (at least as I ... emails / jokes with / without attachments with all the mail headers ... Remember who jumped in with the abuse first David. ...
    (uk.comp.sys.mac)
  • Re: Comparing Proofs of Rossers 1936 Theorem
    ... David C. Ullrich wrote: ... not both, and thus will be seen in either but not both lists, and we ... refutable sentences coincide with the unprovable sentences, ... Well, you really beat me on that one, David. ...
    (sci.logic)
  • Re: Muslim censorship at the UN
    ... Nations Commission on Human rights was a valuable article by David ... impugn the source of the facts. ... Do you think that Islam is well served by these tactics? ... seem to win) by whatever means, or so Muslims seem to think. ...
    (soc.religion.islam)
  • Re: What is the evidence for Phoenician involvement with tin fromBritain?
    ... David B. wrote in message ... ... and the facts it links (Phoenician trade and Irish ... before the Irish voyages occurred). ... Assuming that Inger is not indulging in a 7-year hoax, ...
    (sci.archaeology)