Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
Note "recursive" = "computable", but I adopted my preferred terminology. –  JDH Dec 10 '11 at 1:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.