edom.web.id

Unary algebra

\((S,f)\) is a mono-unary algebra iff \(S\) is a type and \(f\) is an endofunction on \(S\). Other names of mono-unary algebra are ‘unar’ and ‘unary algebra’. We prefer unar. It’s short.

Literatures:

Related topics:

Computation: Let \(A = (S,f)\) be a unar. We define \(fun~A\) (the function \(A\) computes) as \(\newcommand\abs[1]{\lvert#1\rvert} fun~(S,f) = w~f\) where \(w~f\) is the infinite iteration of \(f\): \[ \begin{align*} w~f &= f \circ w~f \\ &= f \circ f \circ f \circ \ldots \\ &= f^{\aleph_0}. \end{align*} \]

We can think of \(w\) as a limit: \[ w~f~x = \lim_{n \to \infty} f^n~x. \]

Totality: A unar \((S,f)\) is total iff \(w~f\) is a total function; \(w~f\) is total iff for each \(x\) there exists natural number \(n\) such that \(f^n~x = f^{n+1}~x\). The function \(fun~A\) is total iff \(A\) is total.

Totality and iteration: If \(w~f~x = y\) then \(w~f~y = y\). If \(w~f\) is total, then \(w~(w~f)\) is also total. By induction, if \(w~f\) is total, then \(w^n~f\) will also be total for each natural number \(n\). If \((S,f)\) is total, then \((S,w~f)\) is also total.

Number of total unars: How many total unars can we make from a set \(S\)? Is it \(\abs{S}^{\abs{S}}\)?

Surjection: There is a surjection from the set of all total unars made from set \(S\) to the set of all endofunctions on \(S\). (Proof?) Conclusion: For each endofunction \(f\), there exists at least one total unar that computes \(f\). This implies that an endofunction can be implemented by a machine. It doesn’t say whether the machine can be realized.

Cycle: If we keep applying \(f\) to \(x\), we may enter a cycle. We say “\(x\) is the member of a cycle of size \(n\)” iff \(n\) is the smallest natural number such that \(f^n~x = x\), We say “\(x\) is the member of a cycle” if there exists such \(n\).

Transforming cycles: Each of \((S,f)\)’s cycle whose size divides \(n\) becomes a fixpoint in \((S,f^n)\).

Oracle: Let \(g : S\to S\). An oracle for \(g\) computes \(g\) in one unit time. There is a bijection between the set of all canonical oracles on \(S\) and the set of all endofunctions on \(S\). We say that \((\{0,1\} \times S, f)\) is the canonical oracle for \(g\) iff \[ \begin{align*} f~(0,x) &= (1,g~x) \\ f~(1,x) &= (1,x). \end{align*} \]

Termination and time complexity: We say that \(x\) terminates in \(n\) steps, or \(x\) is \(n\) steps away from termination, or \(x\) is \(n\) steps to termination, or \(n\) is the time-to-termination of \(x\), iff \(time~f~x = n\) where \(n\) is the smallest natural number such that \(f^n~x = f^{n+1}~x\). The type of \(time\) is \((S \to S) \to S \to \mathbb{N}\). Iff \(n\) is zero we say that \(x\) is terminal.

Worst-case time complexity: \(T~f~n\) is the worst-case number of steps \(f\) needs to reach terminal state from an input of size \(n\). The function \(size : S \to \mathbb{N}\) defines the input size. The size depends on the encoding. We can define \(T\) like this: \[ T~f~n = max~(map~(time~f)~(inputsWithSize~n)) \\ inputsWithSize~n = \{ x ~|~ x : S, ~size~x = n\}. \]

Input size: In unary encoding, a natural number is its own size. In binary encoding, the size of a natural number \(n\) is \(1 + \lceil \lg n \rceil\), or \(1\) if \(n=0\).

Notation: We can write complexity bounds like this: \[ \begin{align*} T~f &\in O~(\lambda n. n^2) \\ T~f &\in \Omega~(\lambda n. n^2) \\ T~f &\in \Theta~(\lambda n. n^2). \end{align*} \]

Example: In a lambda-calculus machine with Church numerals, the time complexity of adding two natural numbers \(m\) and \(n\) is in \(O(m+n)\).

Finite unars: A unar \((S,f)\) is finite iff \(S\) is finite. \(A = (N,f)\) is a canonical finite unar with size \(n\) iff \(N = \{ 0,1,2,\ldots,n-1 \}\) is the set of the first \(n\) natural numbers. There are \(n^n\) canonical finite unars with size \(n\). The set of all canonical finite unars is countable. Indeed the set of all finite subsets of a countable set is countable.

Number of unars: There are \(\abs{S}^{\abs{S}}\) unars on set \(S\).

Widening (superalgebra): Let \(A = (S,f)\) and \(B = (T_\bot,g)\) be unars where \(T_\bot = T \cup \{\bot\}\) and \(S \subseteq T\). We can widen \(A\) to \(B\): \[ g~x = \begin{cases} f~x &\text{if $x \in S$} \\ \bot &\text{otherwise} \end{cases} \] We can write in such case:

Universal unar over a family: Let \(F = \{ F_0, F_1, F_2, \ldots \} = \{ F_k \}_{k\in\mathbb{N}}\) be a family of all canonical finite unars. We can define an \(F\)-universal unar \(univ~F = (\mathbb{N} \times \mathbb{N}_\bot, f)\) with \[ f~(k,x) = (k, ~f_k'~x) \] where \((\mathbb{N}_\bot,f_k')\) is a widening of \(F_k\).

There is a bijection between \(\mathbb{N}\times\mathbb{N}_\bot\) and \(\mathbb{N}\). This implies the existence of \(\phi : \mathbb{N} \times \mathbb{N}_\bot \to \mathbb{N}\) and its inverse function. We can rewrite the above \(F\)-universal unar as \((\mathbb{N}, g)\) where \[ g~(\phi~(k,x)) = \phi~(k,~f_k'~x). \] We call \(k\) a program because \(k\) selects the machine (\(F_k\)) that the \(F\)-universal machine (\(univ~F\)) shall use.

Unar product: \(A_0 \times A_1\) represents a machine that runs \(A_0\) and \(A_1\) simultaneously. \[ A_0 \times A_1 = (S_0 \times S_1, f) \\ f~(x,y) = (f_0~x,f_1~y) \]

Mono-unary algebra of unars

\(S\) is a set of unars and \(f\) is an endofunction on unars.

Endofunction on unars: \[ t~(S,f) = (u~S,v~f) \]

This is transforming a machine into another machine.

Chaining of unars:

\[ chain~(S,f)~(S,g) = (S,f\circ g) \]

Unars and real numbers: There is a bijection between the unar \((\mathbb{N},f)\) and \(\mathbb{R}\).

Subalgebras (narrowings) and ordering: \((S',f')\) is a subalgebra (a narrowing) of \((S,f)\) iff \(S' \subseteq S\), and \(f' \subseteq f\), and \(f'\) is an endofunction on \(S'\). Subalgebra relation forms an ordering on unars.

Empty unar: \((\varnothing, \varnothing)\).

Magmas of unars: Binary operation on unars: \[ t~(S_0,f_0)~(S_1,f_1) = (u~S_0~S_1, v~f_0~f_1). \]

Union of two disjoint unars:

If \(S_0 \cap S_1 = \varnothing\), \[ A_0 \cup A_1 = (S_0 \cup S_1, f_0 \cup f_1). \]

Free unars: A free unar can be made from either a set or an endofunction. The free unar of set \(S\) is \((S,id)\). The free unar of endofunction \(f\) is \((domain~f,f)\).

Semigroups of unars

\((\Sigma,\cap)\) is a commutative semigroup of unars where \(\Sigma\) is the set of all unars and \[ \newcommand\leftunion{\sideset{_\bullet}{}{\cup}} A_0 \cap A_1 = (S_0 \cap S_1, f_0 \cap f_1). \]

Left-prioritized union gives rise to \((\Sigma,\leftunion)\), a non-commutative semigroup of unars: \[ \begin{align*} A_0 \leftunion A_1 &= (S_0 \leftunion S_1, f_0 \leftunion f_1). \\ S_0 \leftunion S_1 &= S_0 \cup S_1 \\ (f_0 \leftunion f_1)~x &= \begin{cases} f_0~x &\text{if $x \in domain~f_0$} \\ f_1~x &\text{otherwise.} \end{cases} \end{align*} \]

Others

Digital physics hypothesizes that the Universe is a unar.