Talk:Combination of Recursive Functions

In fact, the relation does not need to be computable for this theorem (a variant of it, at least) to hold. Specifically, if $f$ and $g$ take the same value when both are defined, all that matters is that at least one is defined for every input.

The intuitive reason behind this is that we can simulate machines computing each simultaneously; when one of them terminates, we have our result. And, by assumption, at least one will always halt.

This proof could be done, in principle, with just URMs and recursive functions, but it would be very inconvenient. It would be easiest to do this will actual Turing machines. Just run them simultaneously on a $2$-tape Turing machine. --CircuitCraft (talk) 00:22, 24 March 2023 (UTC)

All very well to do this proof using a Turing machine, but in order for the existing exposition to make sense in its completeness, I suggest it requires that we use the terminology as it is currently couched. --prime mover (talk) 06:09, 24 March 2023 (UTC)

In that case, we should require that $\RR$ is recursive. This theorem is then a generalization of Definition by Cases is Primitive Recursive. Perhaps it should be renamed to reflect that? The other form that I am proposing would be best named Recursively Enumerable Relation with Recursively Enumerable Complement is Recursive, but we haven't defined Recursively Enumerable yet. --CircuitCraft (talk) 18:14, 24 March 2023 (UTC)

Looking at it, I believe I may have missed some vital detail in the exposition of this. All my course notes are up in the attic, access to which must wait till my mass is below the physical speciifications of my ladder. {:-)