1
$\begingroup$

Any r.e. subset of $A\subseteq\mathbb{N}$ which contains the set $$\mathrm{Tot}=\{i\mid i\ \mbox{is an index of a total function } f\}$$ must, by a standard argument (of Post?) contain some partial recursive function indices.

Given a partial function index (and every total function), it's pretty easy to construct many others, e.g. an index for the function which returns $0$ on prime inputs and is undefined otherwise.

But must $A$ contain all partial functions? This seems like a simple question, but I can't find an argument one way or the other.

Edit: I'm equally (more, actually) interested in the case where $A$ is recursive, e.g., represents the programs from some programing language.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ It can contain all but finitely many partial functions, so that's one example. $\endgroup$ – Ariel May 30 '17 at 14:23
  • $\begingroup$ When does a set contain a function? How are you encoding functions? $\endgroup$ – Yuval Filmus May 30 '17 at 14:36
  • $\begingroup$ It is very likely that there are some recursive sets which do not contain all partial recursive functions, for example an appropriate cofinite set. But the answer depends on the definitions of the terms that you use. $\endgroup$ – Yuval Filmus May 30 '17 at 14:37
  • $\begingroup$ "by a standard argument" -- because R is not recursively enumerable. That tells you something else: $A \setminus \mathrm{Tot}$ can't be decidable, for instance. In fact, it can't be co-r.e. either. $\endgroup$ – Raphael♦ May 30 '17 at 16:46
  • $\begingroup$ @YuvalFilmus I'm fixing some standard Gödel encoding $\phi$ of partial recursive functions. A function $f$ is in a set if there is some $i$ such that $\phi_i=f$ and $i$ is in the set. $\endgroup$ – cody May 30 '17 at 18:19
2
$\begingroup$

Take $A = \{i\ |\ \phi_i(0) \downarrow \}$. It is obviously r.e., and includes $\mathrm{Tot}$.

Yet, it does not contain any index of, say, the always-undefined function $u$. Nor indices for any recursive partial function which is undefined at $0$.

The Kleene set also works: $K = \{i\ |\ \phi_i(i) \downarrow \} \supset \mathrm{Tot}$, yet it does not contain any index for $u$. (And it is r.e.)

|cite|improve this answer
$\endgroup$
  • $\begingroup$ This answers the question as posed, and I'll very likely accept it (I'm going to wait a tiny bit for more potential answers). Unfortunately, it doesn't quite answer my "actual" question which was more along the lines of: "Are there any programing languages which contain all total functions but are not Turing Complete?". Obviously you aren't expected to answer a question I did not actually ask. $\endgroup$ – cody May 30 '17 at 18:27
  • $\begingroup$ @cody Unfortunately my crystal ball was out of service :-P Still, what about a programming language whose syntax is $(n,p)$ and whose semantics is: if the input is $0$ return $n$, otherwise run the (say, Java) program $p$ on the predecessor of the input. In this language, programs can never diverge at $0$. This is more-or-less a PL related to set $A$ above. $\endgroup$ – chi May 30 '17 at 18:32
  • $\begingroup$ @cody (By the way, feel free to wait a couple of days, I'm also curious about more elegant solutions) $\endgroup$ – chi May 30 '17 at 18:35
  • $\begingroup$ @cody See e.g. here. $\endgroup$ – Raphael♦ May 30 '17 at 18:50
  • 1
    $\begingroup$ @Raphael I'm pretty aware of total programing languages, my question is slightly different: can we get all total functions without being Turing complete (i.e. having all partial functions)? My intuition says no. $\endgroup$ – cody May 30 '17 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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