1
$\begingroup$

Let C be a collection of two or more total recursive functions. Define ϕ(x) as the function which is undefined if any two members of C give different values for x as input, and whose output is the same as the output of a member of C, if all members agree. Call ϕ(x) the product of the members of C.

It seems obvious the product ϕ(x) is recursive if C has only a finite number of members. But I have two questions:

1) Is ϕ(x) recursive if C is countably infinite?

2) Is every partial recursive function the product of some collection C of total recursive functions?

We know that not every partial recursive function can be extended to a total recursive function. The second question above seems to be related to that result, but I haven't seen it answered anywhere.

1 Answers 1

2

The answer to question 1 is no. Notice that the issue of countable or uncountable infinite is moot, since there are only countably many total computable functions.

Claim. There is an infinite $C$ such that $\phi$ is not computable.

Proof. Fix any set $A\subset\mathbb{N}$ that is not c.e., and let $\varphi_n$ be the function that is $1$ everywhere, except possibly at $n$, where we define $\varphi_n(n)=1$ if $n\in A$ and otherwise $0$. Thus, each $\varphi_n$ is total computable, since it differs from the constant $1$ function at at most one point. But your function $\phi$ is exactly the constant $1$ function on domain $A$, which is computable if and only if $A$ is c.e.QED

Claim. There is an infinite $C$ such that $\phi$ is computable.

Proof. This time, let $C$ contain the contstant $1$ function and the constant $0$ function, and infinitely many other functions. So the function $\phi$ is the empty function, which is computable. QED

Theorem. The answer to the second question is no.

Proof. Let $A$ and $B$ be two computable inseparable c.e. sets. Thus, each of $A$ and $B$ is c.e.; they are disjoint, but there is no computable set containing $A$ and disjoint from $B$. Let $f$ be the function with constant value $1$ on domain $A$ and value $0$ on domain $B$, and this is partial computable. Suppose that $f$ is the product of total computable functions in your sense. In particular, there is some total computable $\varphi\in C$. If $f$ is the product of the functions in $C$, it follows that $\varphi$ is $1$ on $A$ and $0$ on $B$, and thus, the set $C$ of $k$ where $\varphi(k)=1$ would be a computable set containing $A$ and disjoint from $B$, a contradiction. QED

  • 0
    Note "recursive" = "computable", but I adopted my preferred terminology.2011-12-10