## FANDOM

10,420 Pages

This is a brief guideline on how to define a recursive notation without repeating the common failues.

## General Setting

Before studying how to define a recursive notation, you need to understand how to define a new object such as a constant, a (possibly uncomputable) function, and a (possibly uncomputable) relation.

1. Define the domain when it is a function or a relation.
2. Define the value only using the following objects:
1. Objects given as the inputs when it is a function or a relation.
2. Objects which have been already defined or are simultaneously defined.
3. Objects which are quantified.

Otherwise, the new object is just ill-defined, and hence meaningless. Listing finitely many examples without a full definition? Intuition-based description? Ambiguous use of ellipses? Explanation including undefined objects? Computation using non-unique unquantified expressions? Multiple expansion rules applicable to a single common expression in non-unique ways? The resulting object is just ill-defined. If you can read Japanese, more detailed proposals on how to avoid the ill-definedness are available here.

## Recursive Notation

If you understand the previous section, what you should do is quite simple.

1. Clarify the countable set $$\Sigma$$ of all symbols which you want to use in the notation.
2. Define the set $$OT$$ of valid expressions as a subset of the set $$\Sigma^*$$ of finite strings in $$\Sigma$$.
3. If the recursiveness of $$OT$$ is not obvious with respect to a natural enumeration of $$\Sigma$$, clarify a precise algorithm to determine whether to determine $$t \in OT$$ for any $$t \in \Sigma^*$$.
4. Define the structures of $$OT$$.
1. If you want to define an ordinal notation, then define a well-ordering $$<$$ on $$OT$$, and clarify a precise algorithm to determine $$s < t$$ for any $$(s,t) \in OT^2$$.
2. If you want to define a recursive system of fundamental sequences, then define clarify a set of computable expansion rules such that precisely one rule is applicable to each $$t \in OT$$.
3. If you want to define a computable map $$f \colon OT \times \mathbb{N} \to \mathbb{N}$$, then clarify an algorithm to compute $$f(t,n)$$ for any $$(t,n) \in OT \times \mathbb{N}$$.

You can simultaneously define $$OT$$ and the structures by clarifying mutual recursion. In this case, please be careful not to confound mutual recursion and circular logic.

In an algorithm, you are not allowed to use set theoretic objects such as transfinite ordinals, because inputs and outputs of Turing machines are finite numbers by definition. You are only allowed to deal with methods on finite numbers and formal strings which can be imitated by a Turing complete computation model. Beginners should be very careful that googologists tend to comfound an ordinal and its expression, i.e. formal strings which they use to express an ordinal, and to state "This is an algorithm!" by just showing a transfinite induction on ordinals. No way, ordinals are not formal strings, and hence set theoretic operations directly referring to transfinite ordinals are not methods on finite numbers and formal strings.

Community content is available under CC-BY-SA unless otherwise noted.