MHB Difference of two types of recursive functions

[evinda]

Hello! (Wave)

I want to show that the domain of any partially defined recursive function is equal to the range of some ( totally defined ) recursive function.

I haven't understood which is the difference between a partially defined recursive function and a totally defined recursive function? Could you explain it to me? (Thinking)

 

[HallsofIvy]

After looking it up on "Wikipedia", I would say that a "partially defined" function is a function that is only defined on a subset of the set on which we would like it to be defined. In particular, a "densely defined" function is one that is defined on a subset that is dense in the given set so that it can be extended to the entire set.

 

[Evgeny.Makarov]

I haven't understood which is the difference between a partially defined recursive function and a totally defined recursive function?

The recursivity (=computability) is not important here. A partial function means what it means in other areas of mathematics: such function is defined on a subset of some standard set, while a total function is defined on the whole set. One book calls the domains of algorithms "ensembles of constructive objects". The precise definition is probably impossible as it is for sets. Some standard examples of such ensembles are words in some alphabet and trees labeled by an alphabet. Then one considers computable functions that are represented by algorithms. As domains of computable functions we consider ensembles of constructive objects or sets that they represent. For example, the set of all words in a one-letter alphabet represents natural numbers. Most books consider just some fixed standard sets, like natural numbers or terms in some signature, as domains of total computable functions, and functions that are not defined on the whole set are called partial.

As for the showing that the domain of any partial recursive function is the range of some total recursive function, first note that we must stipulate additionally that the domain of the partial function is nonempty; otherwise the statement is false. Consider a partial recursive function $f$ and suppose $f(x_0)$ is defined. Fix some algorithm $A$ that computes $f$. Let $p:\mathbb{N}\to\mathbb{N}\times\mathbb{N}$ be a bijection (for example, the inverse of the Cantor pairing function). For an arbitrary $k\in\mathbb{N}$ let $(m,n)=p(k)$. Then define $g$ as follows.
\[
g(k)=
\begin{cases}
m,&A(m)\text{ terminates within }n\text{ steps}\\
x_0,&\text{otherwise}
\end{cases}
\]

 

[evinda]

Then one considers computable functions that are represented by algorithms.

Are all the computable functions represented by algorithms?

For example, the set of all words in a one-letter alphabet represents natural numbers.

Could you explain to me why the set of all words in a one-letter alphabet represents natural numbers?

terms in some signature

You mean restrictions of some set of words?

As for the showing that the domain of any partial recursive function is the range of some total recursive function, first note that we must stipulate additionally that the domain of the partial function is nonempty;

So this means that the empty set cannot be the range of a totally defined recursive function? If so, why?

Consider a partial recursive function $f$ and suppose $f(x_0)$ is defined. Fix some algorithm $A$ that computes $f$.

Do we know that there is such an $A$ since $f$ is recursive and so there is a Turing machine that computes it?

Let $p:\mathbb{N}\to\mathbb{N}\times\mathbb{N}$ be a bijection (for example, the inverse of the Cantor pairing function). For an arbitrary $k\in\mathbb{N}$ let $(m,n)=p(k)$. Then define $g$ as follows.
\[
g(k)=
\begin{cases}
m,&A(m)\text{ terminates within }n\text{ steps}\\
x_0,&\text{otherwise}
\end{cases}
\]

Could you explain to me further the definition of $g$ ? I haven't really understood it...

 

[Evgeny.Makarov]

Are all the computable functions represented by algorithms?

Yes, by definition.

Could you explain to me why the set of all words in a one-letter alphabet represents natural numbers?

People have always counted this way.

You mean restrictions of some set of words?

For terms of some signature, see Wikipedia. If you have never encountered these concepts in logic or universal algebra, you may skip this example.

So this means that the empty set cannot be the range of a totally defined recursive function? If so, why?

If, for example, the domain of $f$ is $\mathbb{N}$, then the range (i.e., image) contains $f(1)$.

Do we know that there is such an $A$ since $f$ is recursive and so there is a Turing machine that computes it?

Yes, by definition.

Could you explain to me further the definition of $g$ ?

First note that $\text{image}(g)\subseteq\text{dom}(f)$. For converse inclusion, suppose $m\in\text{dom}(f)$. Then $A(m)$ terminates in, say, $n$ steps. In this case, $g(p(m,n))=m$ and therefore $m\in\text{image}(g)$, which means that $\text{dom}(f)\subseteq\text{image}(g)$. The trick is that as $k$ ranges over the whole $\mathbb{N}$, the elements of pairs that $k$ encodes also range over the whole $\mathbb{N}$. So the first element will take all possible elements of the domain of $f$ and the second element will take all possible numbers of steps. If $A$ terminates on the some element of the domain, sooner or later this will be discovered. It is crucial that $g$ it total because it does not require running $A$ on any input until it terminates because this may not happen. It requires running $A$ for a given number of steps only.

 

[evinda]

People have always counted this way.

Interesting. (Smile)

If, for example, the domain of $f$ is $\mathbb{N}$, then the range (i.e., image) contains $f(1)$.

Ah, I see... And it wouldn't make sense if the domain of a total recursive function would be the empty set...

First note that $\text{image}(g)\subseteq\text{dom}(f)$.

We have supposed that $f(x_0)$ is defined and that implies that $x_0 \in \text{dom}(f)$.
Do we deduce that $m \in \text{dom}(f)$ by taking into consideration that $A(m)$ terminates in $n$ steps and $A$ computes $f$ ?

For converse inclusion, suppose $m\in\text{dom}(f)$. Then $A(m)$ terminates in, say, $n$ steps. In this case, $g(p(m,n))=m$

We have supposed that $p$ is a function with domain the set of natural numbers. So is $g(p(m,n))=m$ a typo? (Thinking)

 

[Evgeny.Makarov]

Ah, I see... And it wouldn't make sense if the domain of a total recursive function would be the empty set...

You are right; this situation is not interesting.

Most books consider just some fixed standard sets, like natural numbers or terms in some signature, as domains of total computable functions, and functions that are not defined on the whole set are called partial.

We have supposed that $f(x_0)$ is defined and that implies that $x_0 \in \text{dom}(f)$.
Do we deduce that $m \in \text{dom}(f)$ by taking into consideration that $A(m)$ terminates in $n$ steps and $A$ computes $f$ ?

Yes.

We have supposed that $p$ is a function with domain the set of natural numbers. So is $g(p(m,n))=m$ a typo?

Yes, it should say $g(p^{-1}(m,n))=m$.

 

[evinda]

First note that $\text{image}(g)\subseteq\text{dom}(f)$. For converse inclusion, suppose $m\in\text{dom}(f)$. Then $A(m)$ terminates in, say, $n$ steps. In this case, $g(p^{-1}(m,n))=m$ and therefore $m\in\text{image}(g)$, which means that $\text{dom}(f)\subseteq\text{image}(g)$.

I understand...

The trick is that as $k$ ranges over the whole $\mathbb{N}$, the elements of pairs that $k$ encodes also range over the whole $\mathbb{N}$.

Because of the fact that we have supposed that $p$ is a bijection and so for $k_1 \neq k_2$ we have that $p(k_1) \neq p(k_2)$, right?

So the first element will take all possible elements of the domain of $f$ and the second element will take all possible numbers of steps.

We define the function $p$ such that $m$ represents an element of the domain of $f$ and $n$ the number of steps that the algorithm $A$ needs in order to terminate, right?

It is crucial that $g$ it total because it does not require running $A$ on any input until it terminates because this may not happen.

You mean because $n$ is known before running the algorithm and so the number of steps that we need in order to check if $A(m)$ terminates is therefore also known?

 

[Evgeny.Makarov]

Because of the fact that we have supposed that $p$ is a bijection and so for $k_1 \neq k_2$ we have that $p(k_1) \neq p(k_2)$, right?

What is important is that $p:\mathbb{N}\to\mathbb{N}\times\mathbb{N}$ is a surjection. Injectivity is not important.

We define the function $p$ such that $m$ represents an element of the domain of $f$ and $n$ the number of steps that the algorithm $A$ needs in order to terminate, right?

$p$ is defined in such a way that it is a surjection, but it is used in the way you describe (though this description is not very precise).

You mean because $n$ is known before running the algorithm and so the number of steps that we need in order to check if $A(m)$ terminates is therefore also known?

If you say "$n$ is known", but don't describe what meaning you ascribe to $n$, your description is somewhat vague. Given $n$, one can check whether a given algorithm terminates in $n$ steps. In general one cannot check whether an algorithm terminates if no upper bound on the number of steps is given.

 

[evinda]

What is important is that $p:\mathbb{N}\to\mathbb{N}\times\mathbb{N}$ is a surjection. Injectivity is not important.

From the surjection of $p$ we have that $\forall (m,n) \ \exists k$ such that $p(k)=(m,n)$.
How do we deduce from this that $m$ and $n$ range over the whole $\mathbb{N}$ ?

$p$ is defined in such a way that it is a surjection, but it is used in the way you describe (though this description is not very precise).

How could we describe it better?

If you say "$n$ is known", but don't describe what meaning you ascribe to $n$, your description is somewhat vague. Given $n$, one can check whether a given algorithm terminates in $n$ steps. In general one cannot check whether an algorithm terminates if no upper bound on the number of steps is given.

Yes, that's right...

It is crucial that $g$ it total because it does not require running $A$ on any input until it terminates because this may not happen. It requires running $A$ for a given number of steps only.

To check if a function is total we just look at its domain and since $k$ ranges over the whole $\mathbb{N}$ we deduce that $g$ is total, right?

In general, can a total function require from an algorithm $A$ to run without knowing any upper bound of steps ?

 

[Evgeny.Makarov]

From the surjection of $p$ we have that $\forall (m,n) \ \exists k$ such that $p(k)=(m,n)$.
How do we deduce from this that $m$ and $n$ range over the whole $\mathbb{N}$ ?

The statement that $m$ and $n$ where $(m,n)=p(k)$ range over the whole $\mathbb{N}$ when $k$ ranges over $\mathbb{N}$ literally means that $p$ is surjective: nothing more and nothing less.

How could we describe it better?

I am against repeatedly rewriting informal ideas ("We define the function $p$ such that $m$ represents...") over a period of many days. They become more and more convoluted and hard to remember. I am for writing precise statements that are true or false. The preferred type of questions about such statements is "Why does this hold?".

To check if a function is total we just look at its domain and since $k$ ranges over the whole $\mathbb{N}$ we deduce that $g$ is total, right?

No, a function is total if it maps every element of its domain. To check whether $g$ is total you must use its definition to see if it is defined for every natural number. The fact that $k$ ranges over $\mathbb{N}$ is not a definition of $g$ and is not enough. Showing that $g$ is total is important because the problem statement in post #1 requires it.

In general, can a total function require from an algorithm $A$ to run without knowing any upper bound of steps ?

What exactly is $A$ in your question? What does an arbitrary total function have to do with $A$? It is also not clear what you mean by saying that a function "requires $A$ to run without knowing any upper bound of steps". In post #5 I said that $g$ requires $A$ to run for $n$ steps to mean that the phrase "run $A$ for $n$ steps" is a part of the definition of $g$.

Now that the idea behind the definition $g$ in post #3 has been discussed, I recommend you go back to the definition and to the corresponding theorem and try to understand its proof given in post #5. Try to write precise statements as much as possible.

 

[evinda]

No, a function is total if it maps every element of its domain. To check whether $g$ is total you must use its definition to see if it is defined for every natural number. The fact that $k$ ranges over $\mathbb{N}$ is not a definition of $g$ and is not enough. Showing that $g$ is total is important because the problem statement in post #1 requires it.

We have that $k$ is an arbitrary natural number and $p(k)=(m,n)$. There are two possible cases:

• $A(m)$ terminates within $n$ steps. Then $g(k)=m$.
• $A(m)$ does not terminate within $n$ steps. Then $g(k)=x_0$.

These are the only possible cases and since $k \in \mathbb{N}$ is arbitrary, we deduce that the function $g$ is total. Is tis right?

It is crucial that $g$ it total because it does not require running $A$ on any input until it terminates because this may not happen.

I was trying to understand this proposition. I was wondering, whether we could deduce if the function $g$ is total if the number of steps needed, $n$, wouldn't be known, i.e. if we had this function$\left\{\begin{matrix}
m, & A(m) \text{ terminates}\\
x_0 ,& \text{ otherwise}
\end{matrix}\right.$

But I think that we could since we check if the function is defined for all elements of the domain in order to check if it is total. We don't look at its image. Right?

 

[Evgeny.Makarov]

We have that $k$ is an arbitrary natural number and $p(k)=(m,n)$. There are two possible cases:

• $A(m)$ terminates within $n$ steps. Then $g(k)=m$.
• $A(m)$ does not terminate within $n$ steps. Then $g(k)=x_0$.

These are the only possible cases and since $k \in \mathbb{N}$ is arbitrary, we deduce that the function $g$ is total. Is tis right?

Yes, either $A(m)$ terminates within $n$ steps or it does not. In both cases $g(k)$ is defined. Therefore, $g$ is total: it is defined for every $k$. But totality of $g$ is much weaker than what has to be shown. The problem asks to prove that $g$ is total and recursive (computable). It is very easy to come up with a not necessarily computable function whose image is the domain of $f$ ($f$ is the original partial recursive function). For example, if $\text{dom}(f)$ is finite, say, $\{m_0,m_1,\dots,m_{p-1}\}$, then define $g(k)=m_r$ where $r$ is the remainder when $k$ is divided by $p$. That is, $g$ is a periodic function taking values $m_0,\dots,m_{p-1}$ repeatedly. In this case, $g$ is recursive. If, on the other hand, $\text{dom}(f)$ is infinite, then, since $\text{dom}(f)\subseteq\mathbb{N}$, there is a bijection $g$ from $\mathbb{N}$ to $\text{dom}(f)$. However, there is no guarantee that such $g$ is recursive.

It is important that "$A(m)$ terminates within $n$ steps" is a decidable statement. That is, there is a Turing machine $M$ (or a Java method, C function, etc.) that for given $m$ and $n$ will always terminate and return "yes" or "no" depending on whether this statement is true or false. Here $A$ is a fixed Turing machine (algorithm) that computes $f$, so it can be incorporated into $M$. The informal description of $M$ is simple: run $A$ on $m$ for $n$ steps; if it terminates, return "yes"; otherwise, return "no". The finite number $n$ of steps is crucial. Therefore, $g(k)$, which has to decide statements in the first sentence of this paragraph, is computable.

I was trying to understand this proposition. I was wondering, whether we could deduce if the function $g$ is total if the number of steps needed, $n$, wouldn't be known, i.e. if we had this function$\left\{\begin{matrix}
m, & A(m) \text{ terminates}\\
x_0 ,& \text{ otherwise}
\end{matrix}\right.$

But I think that we could since we check if the function is defined for all elements of the domain in order to check if it is total. We don't look at its image. Right?

Such function is total, but it is not a priori computable because there is no obvious algorithm for deciding whether $A(m)$ terminates.

 

[evinda]

I understand. Thank you very much! (Smile)