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

From: Aatu Koskensilta (aatu.koskensilta_at_xortec.fi)
Date: 01/18/05 

Date: Tue, 18 Jan 2005 13:26:48 +0200

Ajoy K Thamattoor wrote:

> Torkel Franzen wrote:
>>
>> 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).

Torkel has said nothing to indicate that this were his view. The point
of my post was not that the set of total recursive functions is
recursive, which it of course is not. Rather I wished to illustrate why
it was such a surprise that there is a mathematically precise and stable
definition of computability. This is why I spoke of an _apparent_
obstacle, the obstacle being that it was not clear how one could have a
definition of computability which would not cover all intuitively
mechanically computable functions due to the possibility of diagonalization. 

-- 
Aatu Koskensilta (aatu.koskensilta@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
  - Ludwig Wittgenstein, Tractatus Logico-Philosophicus

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. ...
    (comp.theory)
  • 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. ...
    (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. ...
    (sci.math)