Re: Cantor For Dummies ...

In article <1175183785.561962.104910@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>, "georgie" <geo_cant@xxxxxxxxx> writes:
On Mar 29, 9:55 am, riderofgiraffes <mathforum.org...@xxxxxxxxxxxxxx>
wrote:
I never said that the list being fed in was
the output list. Never once did I say that
an output list was being used as input. I'd
be interested to see where you claim I said
that an output list was being used as input.
You said that your algorithm can use ANY input.

Yes. I said that if you provide a list of
committees, then my algorithm can and will
produce a committee that's not on your list.

No it can't. It can't use a list that
contains your algorithm's output.

Why not?

If you start with a list L1 of committees and
then apply my algorithm to that, we get a new
committee C1 that wasn't on the original list.

Now create a list L2 which is C1 prepended to L1.

Tell me why we can't now apply my algorithm
to L2.

Why would that change the fact that each Ln is the
output of an algorithm? Running some algorithm in
a loop n times is still an algorithm and therefore
is contained in the collection of all algorithms
that output a committee.

There is indeed a collection of all algorithms that output
a committee. That much is true. And that does mean
that for any algorithm you can generate and any algorithm
Rider can answer back with, there will be an algorithm in
that collection that produces a list containing his committee
tacked onto your list.

You're absolutely correct in that intuition.

[It turns out that this collection is countable. Which is an
immediate consequence of the convention that all "algorithms"
are finitely describable]

However, it turns out that is no algorithm that lists all and
only the algorithms in that collection. There are algorithms
that list all the algorithms in the collection. And there are algorithms
that list only algorithms in the collection. But none that do both.

[This is a well known result in computability theory and follows
from a simple diagonalization argument. But since Cantor
appears in the thread title, I don't expect that to carry any weight.
Maybe we should rename this to "Turing for dummies"]

Having a collection of algorithms isn't good enough to generate
a list of committees with. An actual algorithm is what we're
after. Any such algorithm can either generate a complete list
of committees or an error-free list of committees. It can't do
both.

Rider's algorithm depends on the implicit assumption that your
algorithm is error-free. If algorithm number 31,416 in your
list of algorithms doesn't actually produce an answer when asked
whether member 31,416 is in committee number 31,416 then Rider's
algorithm can't decide whether member 31,416 is or is not in the
committee that it produces.

On the assumption that your algorithm is error-free, Rider has already
succeeded in delivering a proof that your algorithm is incomplete.
.

Relevant Pages

  • Re: Cantor For Dummies ...
    ... If you have a real algorithm and it outputs a committee, ... If it is an actual algorithm and uses valid input. ... So we can only use any list other than lists ...
    (sci.math)
  • Re: Educated guesses for efficiency?
    ... it is comparatively rare for a program to run too slowly because an algorithm with the wrong big-O analysis was chosen. ... of things tended to be stored in lists). ... built-in sort function. ... Programmers *will* use algorithms with high complexities. ...
    (comp.lang.c)
  • Re: Cantor For Dummies ...
    ... algorithms that output a committee can be listed. ... committee output by my algorithm depends on its input. ... If it is an actual algorithm and uses valid input. ... other than lists made from the output. ...
    (sci.math)
  • Re: Comparing lists
    ... > of your faith that Big O is the be all and end all of algorithm planning. ... complexity measures, like Big-Oh. ... If experimental data and theory *disagree*: ... the conversion of lists to sets needs the insertion of N ...
    (comp.lang.python)
  • Re: coerce for arbitrary types
    ... the algorithm itself is essentially last-in first-out, ... via some sort of recursion? ... WaitStack <= new stack containing topnode ... As nested lists, there's only one number in a proper position. ...
    (comp.lang.lisp)