Formal definition of an algorithm that outputs the cardinality of a hereditarily finite set

56 Views Asked by At

Let our alphabet consist of three elements: the left brace {, the right brace }, and the comma $,$. Suppose we have already defined the language $L$ over that alphabet which represents the hereditarily finite sets. So, for instance, the string $\{\}$ would represent the empty set, and the string $\{\{\},\{\}\}$ would represent the singleton of the empty set. I want to define, formally, an algorithm or computer program that takes a string $s$ from $L$, and outputs a nonnegative integer which is the cardinality of the hereditarily finite set which is represented by $s$. So, for instance, the algorithm would output $0$ to the string $\{\}$, $1$ to the string $\{\{\}\}$, and also $1$ to the string $\{\{\},\{\}\}$. Can someone give me the definition of such an algorithm?