How can we define the terms "computable" and "partially computable" for functions like $f:\mathbb N^k \to \mathbb N^m$

434 Views Asked by At

We say a function $f:\mathbb N \to \mathbb N$ is computable if it is defined for every $x\in \mathbb N$.

We call a function $f:\mathbb N \to \mathbb N$ partially computable if the domain of $f$ is not necessarily all of the natural numbers.

Also, We know that for every $k\in \mathbb N$, there exists a bijection from $\mathbb N^k$ to $\mathbb N$.

So, How can we define more general computable and partially computable functions?

To be more precise:

Assume that you are given a function $g:\mathbb N^k \to \mathbb N^m$ such that $n,m \in \mathbb N$. How can you tell if $g$ is computable? (or partially computable)

Note: I know that there are many definitions for this. But I want the definition which is based on the domain of $g$.

1

There are 1 best solutions below

5
On BEST ANSWER

The intuition is basically the same as functions from $\mathbb{N}$ to $\mathbb{N}$. Let $\vec{x}=(x_1,x_2,...,x_n)$ represent an $n$-tuple, then $g: \mathbb{N} ^n \rightarrow \mathbb{N}^m$ can be written:

$g(\vec{x}) = ( \phi_1(\vec{x}), \phi_2(\vec{x}),...,\phi_m(\vec{x}))$

where the $\phi_i$ represent some algorithm with $\phi_i(\vec{x}) \downarrow$ and $\phi_i(\vec{x}) \uparrow$ meaning the algorithm halts or doesnt halt respectively. Then:

$g$ is computable (any by implication partially computable )$ \Longleftrightarrow \forall \vec{x} \in \mathbb{N}^n: \phi_1(\vec{x})\downarrow, \phi_2(\vec{x})\downarrow,...,\phi_m(\vec{x})\downarrow$

and

$g$ is partially computable and not total$\Longleftrightarrow \exists \vec{x} \in \mathbb{N}^n \exists i \in \{1,2,...,m\}: \phi_i(\vec{x}) \uparrow$