View source for Coordinatization

{{MSC|68P05}} 

{{TEX|done}}


A coordinatization is some kind of a representation of a [[Sigma-algebra (Computer Science)|$\Sigma$-algebra]] $A$ by a $\Sigma$-algebra consisting of natural numbers, i.e. by a $\Sigma$-number-algebra. Contrary to a usual representation, however, not the elements of $A$ are encoded by elements of $C$ — this would be a [[Gödelization]] —  but vice versa. Such kind of a representation is useful in situations, where preferably natural numbers are processed.

Formally, a <i>coordinatization</i> of a $\Sigma$-algebra $A$ is a pair $(C,\alpha)$ with $C$ as a $\Sigma$-number-algebra and $\alpha\colon C \longrightarrow A$ as a surjective $\Sigma$-algebra-morphism from $C$ onto $A$. Usually, $\alpha$ is chosen to be injective as well making $C$ and $A$ isomorphic. If $\alpha$ is not injective, $C/\equiv_\alpha$ can be considered instead. In such a case it holds $A\cong C/\equiv_\alpha$ whereby $n\equiv_\alpha m :\Longleftrightarrow \alpha(n)=\alpha(m)$ for $n,m\in C_s$, $s\in S$ {{Cite|W90}}.

Using a coordinatization $(C,\alpha)$, the notions of [[Computable function|computability]] (and other areas of theoretical computer science) can be transferred to $\Sigma$-algebras. Accordingly, a coordinatization is called <i>computable</i> resp. <i>semicomputable</i> resp. <i>co-semicomputable</i>, if $C$ (and $\equiv_s$ for all $s\in S$) is recursive resp. recursively enumerable resp. co-recursively enumerable. A $\Sigma$-algebra is <i>computable</i> resp. <i>semicomputable</i> resp. <i>co-semicomputable</i>, if it exists a computable resp. semicomputable resp. co-semicomputable coordinatization of $A$. An algebraic specification is called <i>computable</i> resp. <i>semicomputable</i> resp. <i>co-semicomputable</i>, if it exists a computable resp. semicomputable resp. co-semicomputable $\Sigma$-algebra {{Cite|W90}}.

The properties of a computable $\Sigma$-algebra are summarized in the following theorem: A computable $\Sigma$-algebra is isomorphic to a recursive $\Sigma$-number-algebra $C$ with carrier sets $C_s$, $s\in S$, equal to $\mathbb{N}$ or $\{1,\ldots,n_s\}\subseteq \mathbb{N}$ {{Cite|W90}}.  

Sometimes, one has to compare two coordinatizations $(C_1,\alpha_1)$, $(C_2,\alpha_2)$ of a $\Sigma$-algebra $A$. Then the following notion may be useful. $\alpha_1$ is said to <i>recursively reduce</i> to $\alpha_2$, if it exists a recursive mapping $f\colon C_1\longrightarrow C_2$ such that $\alpha_1 =\alpha_2 \circ f$ {{Cite|W90}}.

==References==

{|
|-
|valign="top"|{{Ref|W90}}||valign="top"| M. Wirsing: "Algebraic Specification", in J. van Leeuwen: "Handbook of Theoretical Computer Science", Elsevier 1990
|-
|}