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.

$\endgroup$
5
  • 2
    $\begingroup$ It can contain all but finitely many partial functions, so that's one example. $\endgroup$
    – Ariel
    May 30, 2017 at 14:23
  • $\begingroup$ When does a set contain a function? How are you encoding functions? $\endgroup$ May 30, 2017 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$ May 30, 2017 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, 2017 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, 2017 at 18:19

1 Answer 1

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.)

$\endgroup$
6
  • $\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, 2017 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, 2017 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, 2017 at 18:35
  • $\begingroup$ @cody See e.g. here. $\endgroup$
    – Raphael
    May 30, 2017 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, 2017 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.