Re: Provability

On Fri, 26 Oct 2007 20:28:50 -0400, quasi <quasi@xxxxxxxx> wrote:

On Fri, 26 Oct 2007 00:19:14 GMT, Michael Press <rubrum@xxxxxxxxxxx>
wrote:

In article
<m7v0i3dpaksfbt8nssfpuh524piltchqua@xxxxxxx>,
David C. Ullrich <ullrich@xxxxxxxxxxxxxxxx> wrote:

On Wed, 24 Oct 2007 17:57:05 GMT, Michael Press <rubrum@xxxxxxxxxxx>
wrote:

In article
<ibiuh39cpcljngark7juncm853rda374im@xxxxxxx>,
David C. Ullrich <ullrich@xxxxxxxxxxxxxxxx> wrote:

On Tue, 23 Oct 2007 23:01:05 GMT, Michael Press <rubrum@xxxxxxxxxxx>
wrote:

In article
<rbisrael.20071023142716$7fa6@xxxxxxxxxxxxxxxx>,
Robert Israel <israel@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx>
wrote:

Victor Porton <porton@xxxxxxxx> writes:

For famous hypothesis such as Millennium Prize problems (or to be yet
more specific for P=NP problem)...

... how we can (or cannot) be sure that the hypotheses or its negation
is provable.

We can't. In some cases we can do half of this: e.g. if the Riemann
hypothesis or Goldbach's conjecture happens to be false, then its
negation is provable. But if it is true, there is no guarantee that
there is a proof of that.

There are statements which are unprovable nor true nor false in ZFC.

For a specific example can we be sure that either P=NP or P!=NP is
provable?

No. This is even worse than the Riemann hypothesis in that regard:
thus if P=NP there is a polynomial-time algorithm for solving an NP-complete
problem, but there might not be a proof that this algorithm works.

The notion of algorithm shares an important characteristic
with the notion of theorem. A computational method is not
an algorithm until we have accepted a proof of its efficacy.

Not according to the definition of "algorithm" I know.

Both of the following routines are algorithms. One of them
is an algorithm which gives the right answer to the
question "Is RH true?":

def SayYes:
return "yes"

def SayNo:
return "no"

I don't know which one gives the right answer, but
that doesn't change the fact that they are both
algorithms and one of them works.

Neither of those procedures and associated assertions is
an algorithm, because you have not offered an accepted
proof.

That's ridiculous.

Then we have nothing more to discuss.

I mostly agree with Michael Press on this issue.

You're entitled to your opinion. It's wrong.

I admit that I know very little about the theory of computation, and
yet, I think I know an algorithm when I see one.

Here's my (informal) concept ...

A procedure does not qualify as "an algorithm" unless there is a
specification of

(1) What problem the algorithm is intended to solve.

(2) The acceptable and/or required inputs.

(3) The possible outputs.

(4) How the algorithm works.

(5) A proof that it correctly solves the intended problem.

And I imagine that you'd also say that something does not
qualify as an irrational number unless there is a proof
that it is irrational?

If you would not say that, why not?

If you _would_ say that: You might note that it follows that
there are only countably many irrational numbers. It also
follows that zeta(3) was not irrational 100 years ago,
but is now irrational.

As far as I can see, anyone who actually implements, designs, or
writes textbooks about algorithms takes all of the above aspects quite
seriously, _especially_ aspect (1), and would regard a procedure with
no specified goal as useless nonsense, not an algorithm.

Of course they do! Just as when someone publishes an assertion
that a given number is irrational they include a proof of this
fact. That has nothing to do with the _definition_ of "irrational
number".

quasi


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

David C. Ullrich
.

Relevant Pages

  • Re: Is P(x,y) Recursively Enumerable if P(N,x) is for every N?
    ... David C. Ullrich wrote: ... The obvious approach to defining an algorithm to enumerate ...
    (sci.logic)
  • Re: OT Camera Raw 5.2 and Photoshop CS4, not CS3
    ... little out-of-date wrt programming techniques but I'd say ... David, back in my Apple][days and even during my early PC DOS ... the first sort algorithm junior programmers ... the "compiler" was really generating pseudo code which needed to ...
    (rec.photo.digital.slr-systems)
  • Re: Snowie - suspicious stuff
    ... "David C. Ullrich" wrote ... with any algorithm: Because you could do it as a ... roll is going to be totally irrelevant compared to the time it takes ...
    (rec.games.backgammon)
  • Re: TeX is broken? LaTeX is broken?
    ... David, providing the algorithm was a positive and helpful ... You could just reread the original sketch. ...
    (comp.text.tex)
  • Re: OT Camera Raw 5.2 and Photoshop CS4, not CS3
    ... standing at the front of the class saying "Don't diddle code, ... find out just /which/ sections of your program need tweaking. ... I'd agree with you here again, David. ... algorithm it is getting bogged down or what options the processor ...
    (rec.photo.digital.slr-systems)