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:49:35 -0800
To: Torkel Franzen <torkel@sm.luth.se>

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).

Ajoy.

Relevant Pages