FANDOM


m (Blog post created or updated.)
m (Blog post created or updated.)
Line 1: Line 1:
 
This is a brief guideline on how to define a recursive notation without repeating [https://googology.wikia.org/wiki/User_blog:P%E9%80%B2%E5%A4%A7%E5%A5%BD%E3%81%8Dbot/List_of_Common_Failures_in_Googology the common failues].
 
This is a brief guideline on how to define a recursive notation without repeating [https://googology.wikia.org/wiki/User_blog:P%E9%80%B2%E5%A4%A7%E5%A5%BD%E3%81%8Dbot/List_of_Common_Failures_in_Googology the common failues].
   
What you should do is quite simple.
+
== 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.
  +
# Define the '''domain''' when it is a function or a relation.
  +
# Define the '''value''' only using the following objects:
  +
## Objects given as the '''inputs''' when it is a function or a relation.
  +
## Objects which have been '''already defined''' or are '''simultaneously defined'''.
  +
## 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 [https://googology.wikia.org/ja/wiki/%E3%83%A6%E3%83%BC%E3%82%B6%E3%83%BC%E3%83%96%E3%83%AD%E3%82%B0:P%E9%80%B2%E5%A4%A7%E5%A5%BD%E3%81%8Dbot/%E8%A8%88%E7%AE%97%E5%8F%AF%E8%83%BD%E9%96%A2%E6%95%B0%E3%81%AE%E5%AE%9A%E7%BE%A9%E3%81%AE%E6%9B%B8%E3%81%8D%E6%96%B9 here].
  +
  +
  +
== Recursive Notation ==
  +
  +
If you understand the previous section, what you should do is quite simple.
 
# Clarify the countable set \(\Sigma\) of all symbols which you want to use in the notation.
 
# Clarify the countable set \(\Sigma\) of all symbols which you want to use in the notation.
 
# Define the set \(OT\) of valid expressions as a subset of the set \(\Sigma^*\) of finite strings in \(\Sigma\).
 
# Define the set \(OT\) of valid expressions as a subset of the set \(\Sigma^*\) of finite strings in \(\Sigma\).
Line 12: Line 12:
   
 
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.
 
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.
 
In the definition of a new object such as a well-ordering, a fundamental sequence, and a computable map, you are only allowed to use the following:
 
* The inputs of the objects when they are functions or relations.
 
* Other objects which have already been defined or are simultaneously defined.
 
* Quantified objects.
 
Otherwise, the objects are just ill-defined, and hence meaningless. Listing finitely many examples without full definitions? 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 objects are just ill-defined. If you can read Japanese, more detailed proposals on how to avoid the ill-definedness are available [https://googology.wikia.org/ja/wiki/%E3%83%A6%E3%83%BC%E3%82%B6%E3%83%BC%E3%83%96%E3%83%AD%E3%82%B0:P%E9%80%B2%E5%A4%A7%E5%A5%BD%E3%81%8Dbot/%E8%A8%88%E7%AE%97%E5%8F%AF%E8%83%BD%E9%96%A2%E6%95%B0%E3%81%AE%E5%AE%9A%E7%BE%A9%E3%81%AE%E6%9B%B8%E3%81%8D%E6%96%B9 here].
 
   
 
[[ja:%E3%83%A6%E3%83%BC%E3%82%B6%E3%83%BC%E3%83%96%E3%83%AD%E3%82%B0:P%E9%80%B2%E5%A4%A7%E5%A5%BD%E3%81%8Dbot/%E8%A8%88%E7%AE%97%E5%8F%AF%E8%83%BD%E3%81%AA%E8%A1%A8%E8%A8%98%E3%81%AE%E6%9B%B8%E3%81%8D%E6%96%B9]]
 
[[ja:%E3%83%A6%E3%83%BC%E3%82%B6%E3%83%BC%E3%83%96%E3%83%AD%E3%82%B0:P%E9%80%B2%E5%A4%A7%E5%A5%BD%E3%81%8Dbot/%E8%A8%88%E7%AE%97%E5%8F%AF%E8%83%BD%E3%81%AA%E8%A1%A8%E8%A8%98%E3%81%AE%E6%9B%B8%E3%81%8D%E6%96%B9]]

Revision as of 22:36, March 26, 2020

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.