Re: THIS STATEMENT HAS NO PROOF IN ANY SYSTEM = true or false?

From: Ajoy K Thamattoor (ajoyk_at_cs.stanford.edu)
Date: 01/18/05 

Date: Mon, 17 Jan 2005 20:23:44 -0800
To: Torkel Franzen <torkel@sm.luth.se>

Torkel Franzen wrote:

> Ajoy K Thamattoor <ajoyk@cs.stanford.edu> writes:
>
>
>>Isn't it possible to have a definition of computability that
>>creates a set of computable functions of aleph-1 cardinality (ie., a
>>set with uncountably infinite elements)?
>
>
> No doubt such a concept can be produced, but Turing, Gödel, Church
> etc were concerned with functions from N to N computable by an
> algorithm.

    Yes, each computable function is computable with an
algorithm (in other words, recursive), but the set of computable
functions would be uncountably infinite. How do we get from that
to ....

>There's an apparent obstacle to formulating an absolute notion of
>computability. To see this assume we have defined some notion of
>"computability". Arrange then the "computable" functions in a list

> F_1
> F_2
  .
  .
  .
> F_n

        In particular, how we can conclude that defining a notion
of computability would automatically enable us to arrange computable
functions in a list? Note that "defining" a set doesn't automatically
imply an effective procedure for checking membership in a set, at
least not in common parlance (and, as I mentioned, for comp.theory,
the word "definability" has no real formal meaning).

Ajoy.

Relevant Pages

  • Re: THIS STATEMENT HAS NO PROOF IN ANY SYSTEM = true or false?
    ... >>Isn't it possible to have a definition of computability that ... >>set with uncountably infinite elements)? ... algorithm, but the set of computable ... functions would be uncountably infinite. ...
    (sci.math)
  • Re: THIS STATEMENT HAS NO PROOF IN ANY SYSTEM = true or false?
    ... >>Isn't it possible to have a definition of computability that ... >>set with uncountably infinite elements)? ... algorithm, but the set of computable ... functions would be uncountably infinite. ...
    (sci.logic)
  • Re: PROOF that numbers are countable
    ... Consult an introductory book on computability theory. ... It essentially runs all programs and once some problem halts, ... whether it is a halting one) there exists an algorithm to say "yes" for ... report "no" in the case that the word does not belong in the set. ...
    (comp.theory)
  • Re: Problem demonstrating that the set of binary strings is uncountable.
    ... I doubt that the concept of recursive enumerability is part of CS-101. ... The Cantor proof still makes no use of computability. ... I have been claiming that it doesn't. ... > I keep trying to bring you to focus on the algorithm. ...
    (sci.math)
  • Re: Is a general purpose mechanism possible?
    ... AIXI based on Solomonoff's Algorithmic Probability is not computable ... computability means merely to assume that there exist laws governing ... will quarantee an algorithm which exploits every possible symmetry, ... invariant and pattern in the data. ...
    (comp.ai.philosophy)