Re: An instance of Russell's paradox?

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* functions (or all Turing Machines, etc.) can be
enumerated, and there is no diagonalisation problem with that.

The set of just all *total* 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.

[snip]

--
---------------------------
| BBB b \ Barbara at LivingHistory stop co stop uk
| B B aa rrr b |
| BBB a a r bbb | Quidquid latine dictum sit,
| B B a a r b b | altum viditur.
| BBB aa a r bbb |
-----------------------------
.

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, ... >>language. ... >>Diagonalize out of your enumeration to prove that not all functions are ... and there is no diagonalisation problem with that. ...
    (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: Identifying FriendlyName of USB COM port
    ... I don't get a "FriendlyName" value until I go into another enumeration ... I just used RegEdit and I have many entries under USB. ... problems seem to be due to folder and file virtual stores which is related ...
    (comp.lang.pascal.delphi.misc)