🚀 go-pugleaf

In article <1992Nov19.193036.26711@rchland.ibm.com> lwloen@vnet.ibm.com writes:
>Surely, it can't be this easy.  I get squeamish whenever I see clocks and
>numbers on arguments of this kind.  Is the cardinality of the set of
>P algorithms == number of natural numbers?  Why doesn't Cantor's diagonal
>argument crop up somewhere and spoil everything?  (I don't necessarily mean
>the original, but an appropriate analog of it).
>Or, does the cardinality N (that is, of natural numbers)
>arise elsewhere in this problem?  I suppose some really smart people have
>already covered this ground; it is all very counter to my intuition.  Maybe
>it's time for me to take a class on all of this stuff. . .

The set of P-algorithms is a proper subset of the set of turing machines and
the set of turing machines is countable, because by definition both the state
set and the tape-symbol set for a turning machine are finite.

P-algorithms by definition halt with a known bound on running length.

--
Mark Biggar
mab@wdl1.wdl.loral.com