0
$\begingroup$

Main topic is to decide if the problem that selected partial μ-recursive function is an injective function is decidable, undecidable or semi-decidable.

The function is injective when $\forall a,b\;f(a)=f(b) \Rightarrow a=b$

I feel like this problem is decidable. It seems to me that Turing machine will stop and accept or reject function. Am I right? Is it proven?

$\endgroup$

closed as off-topic by Carl Mummert, Shaun, Strants, Hans Engler, José Carlos Santos May 23 '18 at 18:36

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Carl Mummert, Shaun, Strants, Hans Engler, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.

1
$\begingroup$

You can't really have a computational problem that asks you to decide things about functions themselves, which are infinitary objects. At best you can attempt to decide things about descriptions of functions -- for example, you could let your input be a standard description of a Turing machine that computes the function you have in mind.

Here, however, you immediately run into Rice's theorem which states that the set of descriptions that correspond to a particular set of partial functions is always undecidable, assuming that the description scheme is complete and effective, and that the set of functions is neither empty nor contains all partial functions.

So "the set of Turing machines that compute injective functions" is undecidable.

On the other hand, the set of Turing machines that compute non-injective functions is at least semi-decidable, since you can just dovetail simulations of the the machine with all possible inputs in parallel, and halt if and when you have seen two of them terminate with the same result.

We can conclude that the set of Turing machines that compute injective functions cannot even be semi-decidable.

$\endgroup$
0
$\begingroup$

For $n\in\Bbb N$, let $$c(n)=\begin{cases}3n+1,&n\text{ odd}\\n/2,&n \text{even}\end{cases} $$ $$ h(n)=\begin{cases}1,&n<5\\0,&n\ge 5\end{cases}$$and $$ p(n)=\min\{\,k\mid c^{k}(n)=c^{2k}(n), k\ge 1\,\}$$ (which may be undefined for some $n$). Finally, let $$ f(n)=n\cdot h(c^{p(n)}(n)).$$ Clearly, $f$ is a partial $\mu$-recursive function. If you think you can decide whether $f$ is injective - congratulations: you solved an important part of the still very open Collatz conjecture, namely whether or not non-trivial cycles exist: We have $f(n)=n$ if $n$ ends in the trival cycle, $f(n)=0$ if $n$ ends in a different cycle (and $f(n)$ undefined if the Collatz sequence grows indefinitely).

In the light of this consequence, I suggest you revise your gut feeling based answer. (But note that "if true, this would solve a long-standing open problem" si also not really a proof of falseness)

$\endgroup$
  • $\begingroup$ What about $f(n) = n$ if a given Turing machine doesn't halt within $n$ steps, and $f(n) = 0$ if it does? (Not familiar with the definition used in the question so I don't know for sure whether this qualifies...) $\endgroup$ – Daniel Schepler May 22 '18 at 21:39
0
$\begingroup$

Let $A$ be any semi-decidable set that is not decidable (e.g., the halting problem, or the provability predicate for Peano arithmetic), and let, for each $n$, the partial recursive function $f_n$ be defined as follows. $f_n(0)=0$. $f_n(1)$ is defined and equal to $0$ if $n\in A$ and is undefined if $n\notin A$. Finally, $f_n(k)$ is undefined for all $k>1$. Notice that $f_n(x)$ is uniformly computable from $n$ and $x$: Given $n$ and $x$, first check whether $x=0$; if so, output $0$. Next check whether $x>1$; if so, go into an infinite loop and never output anything. Finally, if $x=1$, apply the semi-decision procedure for $A$ with input $n$; if and when it returns "yes", output $0$.

So there is a (primitive) recursive function $g$ such that $f_n$ has index $g(n)$ in a standard indexing of the partial recursive functions. (Technically, I'm using the s-m-n theorem here.)

Note that $f_n$ is injective if and only if $n\notin A$. So $g$ is a many-one reduction of the complement of $A$ to the set of indices of injective partial recursive functions. Since the complement of $A$ is not semi-decidable (because $A$ is semi-decidable and not decidable), it follows that the set of indices of injective partial recursive functions is not semi-decidable either.

$\endgroup$

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