Re: An instance of Russell's paradox?

On Tue, 30 Aug 2005 10:53:34 +1200, Barb Knox <see@xxxxxxxxx> said:
> In article <43137D84.E77AF49E@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
> Jim Spriggs <jim.sprigs@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:
>
>>"A.T." wrote:
> [snip]
>
>>> 1. Can all algorithms be enumerated,
>>
>>Yes. An algorithm can be expressed in finite terms in a formal
>>language. Therefore there are no more than countably many of them.
>>
>>> or will that be another
>>> formulation of Russell's paradox
>>
>>Diagonalize out of your enumeration to prove that not all functions are
>>algorithmic.
>
> All *partial* ...

computable

> ...functions (or all Turing Machines, etc.) can be
> enumerated, and there is no diagonalisation problem with that.
>
> The set of just all *total* ...

computable

> ... functions (or always-halting TMs, etc.) can not be enumerated for
> the reason you give: the diagonalisation of any list of total
> functions will be another total function which is different from every
> one in the list.

.

Relevant Pages

  • Re: An instance of Russells paradox?
    ... > Prolog is seriously not a good choice for that. ... Can all algorithms be enumerated, ... > only if you can formulate the enumeration algorithmically. ... > upon these finite arities, ...
    (sci.logic)
  • Re: An instance of Russells paradox?
    ... Prolog is seriously not a good choice for that. ... Can all algorithms be enumerated, ... only if you can formulate the enumeration algorithmically. ... upon these finite arities, it might ...
    (sci.logic)
  • Re: An instance of Russells paradox?
    ... Can all algorithms be enumerated, ... >Diagonalize out of your enumeration to prove that not all functions are ... list of total functions will be another total function which is ...
    (sci.logic)
  • Re: An instance of Russells paradox?
    ... > difficulties which I seem to be unable to overcome on my own. ... Can all algorithms be enumerated, ... Diagonalize out of your enumeration to prove that not all functions are ... > another way of expressing the set of all sets)? ...
    (sci.logic)
  • Re: Cantors diagonal and describable sets
    ... Suppose you construct a set of all describable sets over the ... language and call them. ... Define the Cantor diagonal complement Ec = {n is an integer: ... Ec then should appear somewhere in the enumeration using f. ...
    (sci.math)