What differentiates FOM from other religions?

dennis.hamilton at acm.org dennis.hamilton at acm.org
Thu Feb 16 12:28:34 EST 2023

From: FOM <fom-bounces at cs.nyu.edu> On Behalf Of Vaughan Pratt
Sent: Sunday, February 12, 2023 23:40
To: fom at cs.nyu.edu
Subject: What differentiates FOM from other religions?
[orcmid] [ … ]
Common to all three is the ostensibly infinitary operation of Kleene star.
Although no numbers are mentioned, one imagines that a* is infinitary.  My question is whether the infinitary nature of a* should be considered potential or actual in each of these three logics of regular expressions.
Vaughan Pratt
[orcmid] I cannot address the question directly, but I do claim that a* is  to within potential infinity and we can look at it from the standpoint of regular (Chomsky type 3) languages.  We can view a* as an unlimited/inexhaustible number of consecutive a’s, each finite case constituting a sentence in the regular language.  Can’t we keep it that simple?
Using a finite alphabet, there are denumerable strings satisfying a*.
In a common notation, we can define
<a-star> ::= :
<a-star> ::= a <a-star>
Here, rather than posit a null string, ‘:’ signifies the end or exhaustion or no-more.
We know much about this language as the set of strings that satisfy the grammar.  That’s a subset of all the strings over a given alphabet. I suppose ‘:’ and ‘a’ in this case.  That set is denumerable and so is the set <a-star> spoken of as completed.  
The enumeration of <a-star> is easy of course.   We can identify the “:” string as 0, and each a <a-star> is the Peano successor of the number of the subsequent <a-star>.  We have an unlimited progression that captures those strings with no duplication and none left out.
Is this not a simple case for grounding denumerability in an unbounded progression  of finite entities?  
So long as we operate to within denumerability, it seems we are accepting potential infinity.  It strikes me that we can remain under that umbrella without much until it is important to address transfinite cardinalities, commencing with the acceptance of N as an aggregate totality.
What’s missing here?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20230216/ab351c77/attachment-0001.html>

More information about the FOM mailing list