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

From: Daryl McCullough (daryl_at_atc-nycorp.com)
Date: 01/18/05 

Date: 18 Jan 2005 03:58:15 -0800

Ajoy K Thamattoor says...
>
>Torkel Franzen wrote:
>> Ajoy K Thamattoor <ajoyk@cs.stanford.edu> writes:
>>
>>
>>>Yes, each computable function is computable with an
>>>algorithm (in other words, recursive), but the set of computable
>>>functions would be uncountably infinite.
>>
>>
>> There are only countably many algorithms.
>
> You have ignored the second part - there is no requirement
>that a definition of a set provide an algorithm for determining
>membership in the set. The set of computable functions is one such
>set (ie., one with a valid definition but no algorithmic way to
>validate membership). If your argument is that a "definition" is
>meaningful only if it is represented by a sound algorithm, then, well,
>that is a matter of perspective (it would, of course, rule out a lot
>of interesting definitions, though).

I think you are misunderstanding Torkel. According to the usual meaning of
"computable function", a function is computable if and only if there is
an algorithm for computing it. There are only countably many computable
functions, since there are only countably many different algorithms.

A broader notion of defining a function is to allow a formula Phi(x,y)
define a function, provided that for each possible value of x, there is
exactly one value of y making Phi(x,y) true. Since there are only
countably many formulas, there are only countably many definable
functions, as well.

The most general notion of function from a set A to a set B is a
set F of ordered pairs <x,y> such that for every x there is exactly
one y such that <x,y> is in F. F need not be defined by a formula.
If A and B are infinite sets, then (according to ZFC) there are
uncountably many such functions, but only countably many of them
are definable. 

--
Daryl McCullough

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: 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)
  • Re: qubits
    ... One cycle of the algorithm would collapse ... Most np-Complete problems have been ... Thus any Qubit ... Though Qubits has obvious potential for increasing computing power at ...
    (comp.object)