Re: Problem demonstrating that the set of binary strings is uncountable.

From: Dave Seaman (dseaman_at_no.such.host)
Date: 08/07/04 

Date: Sat, 7 Aug 2004 15:44:51 +0000 (UTC)

On Sat, 7 Aug 2004 09:51:43 -0500, Poker Joker wrote:
> "Christian Bau" <christian.bau@cbau.freeserve.co.uk> wrote in message
> news:christian.bau-9CB343.01273107082004@slb-newsm1.svr.pol.co.uk...

>> ... he constructs a string as follows: One, Zero, 1 - third
>> digit of string 1, one, zero, 1 - digit 6 of string 2, one, zero, 1 -
>> digit 9 of string 3 and so on.

> Isn't that a non-computable number? Certainly your
> algorithm for computing it can't really exist? Maybe
> that one can?

Computability has nothing to do with the definition of uncountability.

> What about:

> List all strings that all algorithms can produce. The diagonal
> must be in the list and there is no algorithm for modifying it
> to show that there is a string not in the list.

Which demonstrates that there is no algorithm to produce a list of all
strings that all algorithms can produce. That is, the set of computable
strings is not recursively enumerable. 

-- 
Dave Seaman
Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling.
<http://www.commoncouragepress.com/index.cfm?action=book&bookid=228>

Relevant Pages

  • beta version of Victor Shoups book, "A Computational Introduction to Number Theory and Algebra&
    ... Computing with Large Integers ... The Basic Euclidean Algorithm ... Factoring and Computing Euler's phi-Function are Equivalent ... The Existence of Finite Fields ...
    (sci.crypt)
  • Re: Why does Cantor a target for cranks?
    ... and wildberger doesn't give this the recognition it deserves ... that if we have a computing process that generates a stream of ... then it's meaningful for such a specific process (algorithm) ... or conflating various groups of order 6 into the ...
    (sci.math)
  • Re: Correctness proving (Was: Clear and Unambiguous SOFTWARE requirements/specifications possible?)
    ... We come up with reasonable schemes that find "good" results (by some ... The bulk of OR techniques -- like linear programming, dynamic programming, Out Of Kilter, etc. -- all provide a deterministic solution for problems like Traveling Salesman that will always be the absolute optimum. ... Solving np-Complete problems requires both an algorithm and a representation of the problem that is appropriate for the algorithm. ... The issue here is proving correctness of programs that are well-formed within the constraints of the computing space. ...
    (comp.software.testing)
  • Re: The Indescribable Random Numbers
    ... exists that generates the sequence f. ... numbers must be uncountably infinite. ... Cantor's diagonalisation process is not an algorithm in the sense most ... I agree that computing pi to n decimal places is unbounded as n ...
    (sci.math)
  • Re: Penroses Computing Pi Description?
    ... > <snip penrose> ... > digit as output. ... > "computing Pi" on its own, ... is the algorithm the computation of one particular digit or is ...
    (sci.logic)