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: Tue, 18 Jan 2005 10:51:48 -0800
To: Torkel Franzen <torkel@sm.luth.se>

Torkel Franzen wrote:
> Ajoy K Thamattoor <ajoyk@cs.stanford.edu> writes:
>
>
>>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.
>
>
> I take it you've set aside the idea of an uncountably infinite set
> of computable functions.

        My mistake - in the context of this discussion (computable
function === algorithms), yes, the set will have to be countable.
I was thinking of GPACs, but there the concept of an algorithm
doesn't exist.

> As for decidability, as pointed out by Aatu,
> that was the great thing: the partial computable functions are
> effectively enumerable, but we are saved from computably diagonalizing
> out of the the computable functions by undecidability.

        Well, I would look at it the other way. We presuppose what we
want to define (basically, define computable functions as
algorithmically computable ones), and making the definition consistent
requires the introduction of undecidability.

Ajoy.

Relevant Pages

  • Re: THIS STATEMENT HAS NO PROOF IN ANY SYSTEM = true or false?
    ... >>membership in the set. ... but there the concept of an algorithm ... > that was the great thing: the partial computable functions are ... > out of the the computable functions by undecidability. ...
    (sci.math)
  • Re: THIS STATEMENT HAS NO PROOF IN ANY SYSTEM = true or false?
    ... >>membership in the set. ... but there the concept of an algorithm ... > that was the great thing: the partial computable functions are ... > out of the the computable functions by undecidability. ...
    (sci.logic)
  • Re: THIS STATEMENT HAS NO PROOF IN ANY SYSTEM = true or false?
    ... > meaningful only if it is represented by a sound algorithm, then, well, ... of my post was not that the set of total recursive functions is ... obstacle, the obstacle being that it was not clear how one could have a ... mechanically computable functions due to the possibility of diagonalization. ...
    (comp.theory)
  • Re: THIS STATEMENT HAS NO PROOF IN ANY SYSTEM = true or false?
    ... > meaningful only if it is represented by a sound algorithm, then, well, ... of my post was not that the set of total recursive functions is ... obstacle, the obstacle being that it was not clear how one could have a ... mechanically computable functions due to the possibility of diagonalization. ...
    (sci.math)
  • Re: THIS STATEMENT HAS NO PROOF IN ANY SYSTEM = true or false?
    ... > meaningful only if it is represented by a sound algorithm, then, well, ... of my post was not that the set of total recursive functions is ... obstacle, the obstacle being that it was not clear how one could have a ... mechanically computable functions due to the possibility of diagonalization. ...
    (sci.logic)