Tags: enumerable recursive

Front: [$$]A \subseteq \mathbb{N}^k \: recursive \: (decidable)[/$$]
Back: [$$]\Leftrightarrow cf_A : \mathbb{N}^k \rightarrow \mathbb{N} \: computable[/$$]
(Definition)
alt1: [$$]\Leftrightarrow \exists \: computable \: f \in R^{(k)} \: s.t. \: A=f^{-1}\{0\}[/$$]

Front: [$$]A \subseteq \mathbb{N}^k \: recursively \: enumerable[/$$]
Back: [$$]\Leftrightarrow \exists \: computable \: f : \subseteq \mathbb{N}^k \rightarrow \mathbb{N} \: s.t. \: A = Def(f)[/$$]
(Definition)
alt1: [$$]\Leftrightarrow \exists \: recursive \: B \subseteq \mathbb{N}^{k+1} \: s.t. \: A = \{x \in \mathbb{N}^k \: | \: (\exists t) \: (x, t) \in B\}[/$$]
(Projection Theorem)

Front: [$$]A \subseteq (\Sigma^*)^k \: recursive[/$$]
Back: [$$]\Leftrightarrow A = f^{-1}\{\epsilon\} \: for \: some \: total \: computable \: f : (\Sigma^*)^k \rightarrow \Sigma^*[/$$]
(Definition)

Front: [$$]A \subseteq (\Sigma^*)^k \: recursively \: enumerable[/$$]
Back: [$$]\Leftrightarrow A = Def(f) \: for \: some \: computable \: f : \subseteq (\Sigma^*)^k \rightarrow \Sigma^*[/$$]
(Definition)

Front: [latex]$(\delta_1, ...,\delta_k, \delta)-computable$ for representations[/latex]
Back: [latex]A function $f: \subseteq M_1 \times \cdots \times M_k \rightarrow M$ is called $(\delta_1, ...,\delta_k, \delta)-computable$, iff $\exists$ computable $g: {\Sigma^\omega}^k \rightarrow \Sigma^\omega$ s.t. $f(\delta_1(i_1), ..., \delta_k(i_k)) = \delta \circ g(i_1, ..., i_k)$.[/latex]
Other fields (not shown on cards):
alt2: [latex]
      \begin{tikzpicture}[>=stealth, ->, auto]
        \node (a) at (0, 0) { ${\Sigma^\omega}^k$ };
        \node (b) at (3, 0) { $\Sigma^\omega$ };
        \node (c) at (0,-3) { $M_1 \times \cdots \times M_k$ };
        \node (d) at (3,-3) { $M$ };
        \draw (a) -- (b) node [midway] {$g$};
        \draw (a) -- (c) node [midway, left] {$\delta_1,...,\delta_k$};
        \draw (c) -- (d) node [midway, below] {$f$};
        \draw (b) -- (d) node [midway] {$\delta$};
      \end{tikzpicture}
[/latex]

Front: [latex]$(\nu_1, ...,\nu_k, \nu)-computable$ for notations[/latex]
Back: [latex]A function $f: \subseteq M_1 \times \cdots \times M_k \rightarrow M$ is called $(\nu_1, ...,\nu_k, \nu)-computable$, iff $\exists$ computable $g: {\Sigma^*}^k \rightarrow \Sigma^*$ s.t. $f(\nu_1(i_1), ..., \nu_k(i_k)) = \nu \circ g(i_1, ..., i_k)$[/latex]
Other fields (not shown on cards):
alt2: [latex]\begin{tikzpicture}[>=stealth, ->, auto]
        \node (a) at (0, 0) { ${\Sigma^*}^k$ };
        \node (b) at (3, 0) { $\Sigma^*$ };
        \node (c) at (0,-3) { $M_1 \times \cdots \times M_k$ };
        \node (d) at (3,-3) { $M$ };
        \draw (a) -- (b) node [midway] {$g$};
        \draw (a) -- (c) node [midway, left] {$\nu_1,...,\nu_k$};
        \draw (c) -- (d) node [midway, below] {$f$};
        \draw (b) -- (d) node [midway] {$\nu$};
      \end{tikzpicture}[/latex]

Front: [latex]$(\nu_1, ...,\nu_k, \nu)-computable$ for numberings[/latex]
Back: [latex]A function $f: \subseteq M_1 \times \cdots \times M_k \rightarrow M$ is called $(\nu_1, ...,\nu_k, \nu)-computable$, iff $\exists$ computable $g: \mathbb{N}^k \rightarrow \mathbb{N}$ s.t. $f(\nu_1(i_1), ..., \nu_k(i_k)) = \nu \circ g(i_1, ..., i_k)$.[/latex]
Other fields (not shown on cards):
alt2: \begin{tikzpicture}[>=stealth, ->, auto]
        \node (a) at (0, 0) { $\mathbb{N}^k$ };
        \node (b) at (3, 0) { $\mathbb{N}$ };
        \node (c) at (0,-3) { $M_1 \times \cdots \times M_k$ };
        \node (d) at (3,-3) { $M$ };
        \draw (a) -- (b) node [midway] {$g$};
        \draw (a) -- (c) node [midway, left] {$\nu_1,...,\nu_k$};
        \draw (c) -- (d) node [midway, below] {$f$};
        \draw (b) -- (d) node [midway] {$\nu$};
      \end{tikzpicture}