MHB Propositions for recursive functions

[evinda]

Hello! (Wave)

I want to show the following two propositions:

• The domain of a recursive function is recursively enumerable.
• The range of a recursive function is recursively enumerable.

I have thought the following in order to prove the first proposition.

Suppose that we have a recursive function $f$. Then we know that there is an algorithm $A$ that computes $f$.
So if $m \in dom(f)$ then we know that the algorithm $A$ with input $m$ terminates, giving output "yes".
Since $m$ is arbitrary, we deduce that the domain of a recursive function is recursively enumerable.

Is my idea right? If so, can't we also deduce from that that the domain of a recursive function is recursive since the algorithm always terminates for the elements of the domain? (Thinking)

 

[Evgeny.Makarov]

• The domain of a recursive function is recursively enumerable.
• The range of a recursive function is recursively enumerable.

By "recursive function" do you mean partial recursive function?

Suppose that we have a recursive function $f$. Then we know that there is an algorithm $A$ that computes $f$.
So if $m \in dom(f)$ then we know that the algorithm $A$ with input $m$ terminates, giving output "yes".

Since $A$ computes $f$, it outputs whatever $f$ outputs and not necessarily "yes".

Since $m$ is arbitrary, we deduce that the domain of a recursive function is recursively enumerable.

I don't see how it follows, but it may depend on the definition you are using. Please remind the definition of a recursively enumerable set. Also please write the facts (similar to the statements from this problem) that you may use.

 

[evinda]

By "recursive function" do you mean partial recursive function?

I mean a total recursive function.

Since $A$ computes $f$, it outputs whatever $f$ outputs and not necessarily "yes".

I don't see how it follows, but it may depend on the definition you are using. Please remind the definition of a recursively enumerable set. Also please write the facts (similar to the statements from this problem) that you may use.

Yes, now I think so too that I am wrong.A subset $A$ of $\mathbb{N}^k$ is recursively enumerable iff there is a Turing machine $T$, such that $\forall x \in A$, $T$ with input $x$ halts , giving output $1$ and $\forall x \notin A$, $T$ does not halt, i.e. $T$ computes the function

$\phi(x)=\left\{\begin{matrix}
1 & \text{ if } x \in A \\
\infty & \text{ if } x \notin A
\end{matrix}\right.$

A subset $A$ of $\mathbb{N}^k$ is recursive iff $A$ and $A^c$ are recursively enumerable.

 

[Evgeny.Makarov]

I mean a total recursive function.

So you are not sure how to show that $\mathbb{N}^k$ is r.e.? Since the domain of a total function is $\mathbb{N}^k$.

 

[evinda]

So you are not sure how to show that $\mathbb{N}^k$ is r.e.? Since the domain of a total function is $\mathbb{N}^k$.

Oh yes, that's true. Maybe we have to show the statement for both total and partial recursive functions. (Thinking)

Having $\mathbb{N}^k$ as the domain , we can write a program that checks if a vector contains only natural numbers and so $\mathbb{N}^k$ is recursively enumerable. Right?

 

[Evgeny.Makarov]

Maybe we have to show the statement for both total and partial recursive functions.

The domain of a partial recursive function is indeed r.e.

Having $\mathbb{N}^k$ as the domain , we can write a program that checks if a vector contains only natural numbers and so $\mathbb{N}^k$ is recursively enumerable. Right?

Yes.

 

[evinda]

The domain of a partial recursive function is indeed r.e.

Suppose that we have a partial recursive function $f$. Then there is a Turing machine $A$ that computes $f$.
We construct a Turing machine $M$ such that if $A(m)$ terminates for some $m \in \mathbb{N}$ then $M$ terminates giving output $1$ and otherwise $M$ does not terminate. Then $M$ computes the domain of $f$ and thus the domain of $f$ is recursively enumerable.

Is my idea right?

 

[Evgeny.Makarov]

I would not say "$M$ computes the domain of $f$". Usually one says "computes a function". Otherwise I agree.

 

[evinda]

I would not say "$M$ computes the domain of $f$". Usually one says "computes a function". Otherwise I agree.

Then $M$ computes the characteristic function of the domain of $f$ and thus the latter is recursively enumerable. Right?

 

[Evgeny.Makarov]

Then $M$ computes the characteristic function of the domain of $f$

No, a characteristic function is total.

 

[evinda]

No, a characteristic function is total.

A Turing machine can also compute a statement, right? So can we say that then $M$ computes the statement "is the element an element of the domain of $f$", deducing in this way that the domain of $f$ is recursively enumerable?

 

[Evgeny.Makarov]

A Turing machine can also compute a statement, right?

I don't remember seeing anything other than a function after the phrase "a Turing machine computes". And I don't really care about what you write with words. You can give whatever definitions you see fit. The important thing is that you can formulate precise statements and write them using formulas.

 

[evinda]

Writing this I was thinking about an answer of yours, at an other post of me, namely this one:

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.

So I think that I didn't formulate it correctly. Is it more clear as follows?

We construct a Turing machine $M$ such that if $A(m)$ terminates for some $m \in \mathbb{N}$ then $M$ halts giving output $1$, otherwise $M$ does not halt. So we see that the statement "$x$ is an element of the domain of $f$" is recursively enumerable and so the domain of $f$ is recursively enumerable.

 

[Evgeny.Makarov]

This is OK. Usually the term "r.e." is applied to sets, but it can be applied to predicates (as you are writing) if you explicitly define what it means. I would simply say after defining $M$ that the domain of $f$ is r.e. by definition.

 

[evinda]

Ok.

For the second proposition I have thought the following:
Suppose that $f$ is a recursive function. Let $y \in image (f)$. We construct $M$ like that:
We run $f$ on $0,1,2, \dots$ and if $f(n)=y$ for some $n \in \mathbb{N}$ then $M$ terminates giving input $1$, otherwise $M$ loops forever. So the range of a recursive function is recursively enumerable.

Am I right?

Does it also hold that if $A$ is recursively enumerable then $A$ is the range of some recursive function?
If so, how can we find a function whose range is $A$?

 

[Evgeny.Makarov]

Suppose that $f$ is a recursive function. Let $y \in image (f)$. We construct $M$ like that:
We run $f$ on $0,1,2, \dots$ and if $f(n)=y$ for some $n \in \mathbb{N}$ then $M$ terminates giving input $1$, otherwise $M$ loops forever.

If $y \in image (f)$, then the second option is impossible.

Does it also hold that if $A$ is recursively enumerable then $A$ is the range of some recursive function?

Or $A=\emptyset$.

If so, how can we find a function whose range is $A$?

It was discussed in https://driven2services.com/staging/mh/index.php?threads/19389/.

 

[evinda]

If $y \in image (f)$, then the second option is impossible.

Oh yes, that's right... It should be as follows, right?

Suppose that $f$ is a recursive function. We construct $M$ like that:
We run $f$ on $0,1,2, \dots$ and if $f(n)=y$ for some $n \in \mathbb{N}$ then $M$ terminates giving input $1$, otherwise $M$ loops forever. So the range of a recursive function is recursively enumerable.

Or $A=\emptyset$.

It was discussed in https://driven2services.com/staging/mh/index.php?threads/19389/.

I see.

 

[Evgeny.Makarov]

Suppose that $f$ is a recursive function. We construct $M$ like that:

Given input $y$, $M$ runs

$f$ on $0,1,2, \dots$ and if $f(n)=y$ for some $n \in \mathbb{N}$ then $M$ terminates giving input $1$, otherwise $M$ loops forever.

Thus, $M$ terminates on elements of the image of $f$ and only on them, i.e., the image of $f$ is r.e.

 

[evinda]

Given input $y$, $M$ runs
Thus, $M$ terminates on elements of the image of $f$ and only on them, i.e., the image of $f$ is r.e.

I see... Thanks a lot! (Smile)